Каков наиболее эффективный способ хранения этих данных?

9

Я отвечаю за переписывание старого кода VB. Я понимаю, как это работает, но я чувствую, что есть гораздо более эффективный способ сделать то, что они сделали. Я просто не могу понять, что это такое. Вот надуманный пример, который с точки зрения требований к данным действительно похож на то, что мне нужно сделать.

Пользователь должен выбрать производителя, марку, модель и цвет своего автомобиля в графическом интерфейсе. У меня большой текстовый файл, который выглядит примерно так:

Ford Truck F150 red
Ford Truck F150 blue
Ford Truck F150 black
Ford Truck F150 silver
Ford Truck F250 red
Ford Truck F250 green
Ford Sedan Taurus red
Ford Sedan Taurus green
Ford Sedan Taurus white
Ford...
...

Subaru SUV Forester blue
Subaru SUV Forester red
Subaru SUV Outback Black
Subaru SUV Outback Green
Subaru SUV Outback Blue
Subaru SUV Outback Red
Subaru...
...

etc.

Таким образом, если первый выбор - Subaru, во втором поле (make) не должно быть возможности выбрать Truck, поскольку ни один из Subarus не является грузовиком. Точно так же, если они выбирают Ford, Sedan и Taurus, то в последнем поле (цвет) не должна отображаться опция для выбора синего цвета. Или черный. Или что-нибудь кроме красного, зеленого или белого.

Люди, которые написали код до меня, придумали это (в python-y psuedocode):

def getValidOptions():
    items = []
    for i from 0 to numRows:
        options = getLine().split()
        if selectingManufacturer:
            if options[0] not in items:
                items.append(options[0])
        else if selectingMake:
            if selectedManufacturer == options[0] and options[1] not in items:
               items.append(options[1])
        else if selectingModel:
            if selectedManufacturer == options[0] and selectedMake == options[1] and options[2] not in items:
                items.append(options[2])
        else if selectingColor:
            if selectedManufacturer == options[0] and selectedMake == options[1] and selectedModel == options[2] and options[3] not in items:
                items.append(options[3])
    return items

Я думаю, что это просто отвратительно, как на уровне алгоритма, так и на уровне синтаксиса. С одной стороны, он анализирует весь файл, когда ему нужно только прочитать пару строк, если все сделано правильно. Чтобы сделать это еще более неэффективным, мои реальные данные имеют 6 вариантов выбора, а не только 4. Это также хранит больше данных, чем необходимо, учитывая количество дублирующихся данных.

Я ищу другой способ хранения данных в файле или другой способ их анализа, чтобы сделать getValidOptionsфункцию более привлекательной и эффективной. Есть ли способы, которыми я мог бы сделать это?

Джеймс
источник
2
почему бы не использовать базу данных?
Тулаинс Кордова

Ответы:

6

Все остальные ответы, которые я читаю, похоже, игнорируют два основных правила разработки программного обеспечения:

  • сначала уточнить требования (особенно требования к производительности и хранению)

  • Сохраняй это простым, глупым (см. ПОЦЕЛУЙ )

Вы написали «текстовый файл большой», но не написали слишком большой, поэтому я предполагаю, что на самом деле в его размере нет ничего плохого, кроме вашего интуиции. Поэтому, если загрузка файла на самом деле не занимает много времени, и ваш ИТ-отдел или кто-то другой не жалуется на неиспользуемое дисковое пространство, и никто не жалуется на проблемы с сохранением файла, пусть формат файла такой, какой он есть - не стоит недооценивать ценность простоты.

Вы также жалуетесь на эффективность алгоритма, который на самом деле не так эффективен, как мог бы быть, но у него есть одно очень большое преимущество: он просто умопомрачительный и работает. Поэтому, пока он достаточно эффективен, не применяйте преждевременную оптимизацию.

Итак, давайте предположим, что программа работает достаточно быстро. Сначала вы должны спросить, как можно улучшить код с точки зрения простоты и принципа СУХОЙ? И это действительно то, что нужно улучшить, поскольку текущий код не СУХОЙ. В вашем примере, в четыре раза появляется почти одинаковое тестирование блока кода, если параметры на «верхних уровнях» соответствуют текущей строке, что приводит к четырехкратному вызову «добавления» того же типа (в вашем реальном коде повторение происходит). как минимум шесть раз, как вы написали). Вы можете легко избежать этого, вводя числовой уровень выбора или передавая уже выбранные параметры в упорядоченном списке. Используя ваш псевдокод, это приводит к чему-то вроде

# selectedOptions is a list, containing either nothing, or "selectedManufacturer"
# or [selectedManufacturer, selectedMake], ..., and so on
def getValidOptions(selectedOptions):
    items = []
    level = selectedOptions.size()
    for i from 0 to numRows:
        options = getLine().split()
        if selectedOptions == options[0:level-1] and options[level] not in item:
            items.append(options[level])
    return items

Так что это по сути тот же алгоритм без повторяющегося кода.

Поскольку очевидно, getValidOptionsчто его нужно вызывать более одного раза (хотя бы один раз на уровень), я предлагаю применить только одну оптимизацию (если это не так): убедитесь, что getLineфункция извлекает свои данные из основной памяти, и не читать файл с диска снова и снова.

Док Браун
источник
Вы хотите переместить "level = selectedOptions.size ()" перед циклом numRows.
AI Breveleri
6

Итак, ваши данные имеют древовидную структуру, где для каждого производителя у вас есть дерево моделей, а для каждой модели у вас есть цвет (и т. Д.).

Таким образом, вы можете разделить процесс этих данных в два этапа:

  1. После любого обновления текстового файла вы должны обработать этот файл и преобразовать его в древовидную структуру.
  2. При загрузке приложения вы загружаете только древовидную структуру.

Древовидная структура может быть реализована с помощью так называемого хеша , ассоциативного массива или словаря в таких языках, как Java, PHP, Javascript или Python. С этой структурой у вас есть:

  • Первые ключи - производители.
  • Их значения - это просто еще один хеш или словарь, где каждый ключ является моделью.
  • Их значения - это цвета. Или другая структура, хранящая в своих ключах третий уровень и в качестве значения четвертый уровень.
  • И так далее...

В зависимости от вашего языка программирования это может быть реализовано быстрее или медленнее. Например:

  • C # : вы можете реализовать древовидную структуру 1 , а затем пометить ее как сериализуемую.
  • VB.Net : вы можете создать древовидную структуру в одном приложении и сериализовать ее в файл.
    • Для этого Runtime.Serialization.Formatters.Binary.BinaryFormatterможет пригодиться что-то подобное , но я не специалист по сериализации с VB.Net.
  • Javascript : вы можете сгенерировать древовидную структуру в файле JSON, который должен загружаться при каждой загрузке приложения.
  • PHP : вы можете сгенерировать сериализованную версию древовидной структуры данных или также можете загрузить JSON.
  • Java : вы можете сериализовать эту структуру данных, создавая Classинтерфейс, реализующий интерфейс java.io.Serializable.

Рекомендации :

1: https://dvanderboom.wordpress.com/2008/03/15/treet-implementing-a-non-binary-tree-in-c/
- Полное объяснение реализации дерева в C #.
- Ищите комментарий, где кто-то спрашивает о сериализации этого объекта, и ответ на этот комментарий.

Николас
источник
1
Да, я думал об использовании дерева, но я не знаю, является ли это лучшей идеей, потому что в C # нет встроенной древовидной структуры (о которой я знаю), и проект довольно маленький, поэтому я не знаю, стоило бы потратить очень много времени, работая над tree with an arbitrary number of nodesреализацией.
Джеймс
Пока я не специалист по C #, но, по крайней мере, в других языках, таких как Java и PHP, у вас могут быть какие-то словари, где каждый ключ может иметь значение другого словаря.
Николас
Я обновил свой ответ. Посмотрите, что вы думаете об альтернативе хэша или словаря. Я также добавил ссылку с интересной статьей.
Николас
3

Один из простых способов хранения данных - просто поместить их в базу данных SQLite. SQLite, в отличие от большинства баз данных SQL, хорошо подходит для использования в качестве формата файла приложения. Этот подход имеет несколько преимуществ:

  1. Нет необходимости кодировать сериализатор или десериализатор.
  2. Файл редактируемый и запрашиваемый многочисленными существующими программами.
  3. Условная неразбериха, о которой вы упоминаете в вопросе, исключается. Чтобы ограничить выпадающие списки, создайте простое предложение where для каждого столбца (например, select distinct model where manufacturer='ford' and color = 'red').

Это заставляет вас изучать SQL, но избавляет от необходимости изучать пользовательский формат файла.

Брайан
источник
1

Я предполагаю, что вы можете получить произвольный доступ к строкам в файле и, таким образом, можете рассматривать файл как массив записей. Если вы не можете получить произвольный доступ к линиям, то ваш алгоритм - лучший из возможных.

Для более быстрого доступа храните данные в 6 файлах, где каждый файл является указателем на следующий.

Существует множество способов создания индексов плоских файлов. Я обычно использую диапазон индекса. Когда пользователь делает каждый выбор, используйте диапазон, чтобы ограничить чтение следующего файла.

Вот как я бы создал индексы для предоставленных вами образцов данных.

Конечно файл должен быть отсортирован. Я пронумеровал линии для иллюстрации; номера строк не должны появляться в файле.

--| file3.dat |--
 0 Ford Truck F150 red
 1 Ford Truck F150 blue
 2 Ford Truck F150 black
 3 Ford Truck F150 silver
 4 Ford Truck F250 red
 5 Ford Truck F250 green
 6 Ford Sedan Taurus red
 7 Ford Sedan Taurus green
 8 Ford Sedan Taurus white
 9 Subaru SUV Forester blue
10 Subaru SUV Forester red
11 Subaru SUV Outback Black
12 Subaru SUV Outback Green
13 Subaru SUV Outback Blue
14 Subaru SUV Outback Red

Чтобы создать первый индекс, сделайте запись для каждой уникальной комбинации первых трех полей в файле. В каждой записи сохраните номера первой и последней строки, в которых появляется эта комбинация.

--| file2.dat |--
 0 Ford Truck F150       0   3
 1 Ford Truck F250       4   5
 2 Ford Sedan Taurus     6   8
 3 Subaru SUV Forester   9  10
 4 Subaru SUV Outback   11  14

Второй индекс строится аналогично, используя первые два поля первого индекса.

--| file1.dat |--
 0 Ford Truck        0   1
 1 Ford Sedan        2   2
 2 Subaru SUV        3   4

И третий, верхний уровень в данном случае, индекс.

--| file0.dat |--
 0 Ford          0   1
 1 Subaru        2   2

Я думаю, что я переобъясняю концепцию, но в целом вы создаете индекс, удаляя последнее поле и удаляя дубликаты записей.

Вы можете еще больше сократить требования к хранилищу файлов, исключив некоторые избыточные данные.

Например, «первый» индекс в каждой индексной записи всегда на единицу больше, чем «последний» индекс предыдущей записи, или ноль, если предыдущей записи нет. Таким образом, вам не нужно хранить «первые» подписки. Я оставляю их на месте ниже для иллюстрации.

Кроме того, поскольку вы будете использовать только последнее поле в каждой записи для заполнения списка выбора, вам не нужно сохранять другие поля.

Минимальное воспроизведение каскада индексов в конечном итоге выглядит следующим образом, где отметка 'указывает число, которое на самом деле не хранится в файле.

--| file0.dat |--
 0' Ford         0'   1
 1' Subaru       2'   2

--| file1.dat |--
 0' Truck        0'   1
 1' Sedan        2'   2
 2' SUV          3'   4

--| file2.dat |--
 0' F150         0'   3
 1' F250         4'   5
 2' Taurus       6'   8
 3' Forester     9'  10
 4' Outback     11'  14

--| file3.dat |--
 0' red
 1' blue
 2' black
 3' silver
 4' red
 5' green
 6' red
 7' green
 8' white
 9' blue
10' red
11' Black
12' Green
13' Blue
14' Red

Когда вы заполняете список выбора из индекса, вы используете «первый» и «последний» индексы из выбора пользователя в предыдущем индексе, чтобы ограничить количество прочитанных строк.

Пример:

Вы заполняете первый список выбора из всех file0.dat. (Форд, Субару)

Пользователь выбирает «Форд». Соответствующие индексы 0 и 1.

Вы заполняете второй список выбора из строк с 0 по 1 из file1.dat. (Грузовик, Седан)

Пользователь выбирает «Седан». Соответствующие подписки 2 и 2.

Как вы можете видеть, к тому времени, когда пользователь выбрал, например, «Форд», «Седан», «Телец», вы обнаружите, что вам нужны строки только для чтения с 6 по 8, file3.datчтобы заполнить четвертый список выбора.

Я прошу прощения за довольно длинное описание, но здесь очень поздно, и у меня нет времени, чтобы написать короткое.

ДОБАВЛЕНО: Если подумать, файлы могут быть объединены в один.

--| file.dat |--
 0' -            1'   2
 1' Ford         3'   4
 2' Subaru       5'   5
 3' Truck        6'   7
 4' Sedan        8'   8
 5' SUV          9'  10
 6' F150        11'  14
 7' F250        15'  16
 8' Taurus      17'  19
 9' Forester    20'  21
10' Outback     22'  25
11' red          -'   -
12' blue         -'   -
13' black        -'   -
14' silver       -'   -
15' red          -'   -
16' green        -'   -
17' red          -'   -
18' green        -'   -
19' white        -'   -
20' blue         -'   -
21' red          -'   -
22' Black        -'   -
23' Green        -'   -
24' Blue         -'   -
25' Red          -'   -

Это используется точно так же, как версия с несколькими файлами, за исключением того, что в первой строке необходимо указать первый диапазон индекса.

А.И. Бревелери
источник