Структура данных для быстрой фильтрации (Delphi)?

Question

Я оптимизирую часть приложения Delphi, где списки объектов часто фильтруются по разным критериям. Объекты хранятся в структурах TObjectList, и каждый фильтр обычно выбирает очень маленький процент (например, 1%) от всего набора. Общее количество объектов может быть в диапазоне 100 КБ, и во время вычислений основной набор не изменяется. Хотя фильтры применяются только для нескольких свойств, списки не могут быть отсортированы таким образом, чтобы оптимизировать все возможные критерии.

Я ищу предложения о том, как организовать объекты (структуры данных) или алгоритм, который можно использовать для решения этой проблемы. Спасибо!

Пример фильтра:

  ((Object.A between 5 and 15) AND
  (Object.B < 20) AND
  (Object.C(AParam) > 0)) OR
  (Object.IsRoot(...))

Answer 1

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

Обращаясь к вашему примеру выше: создайте список, отсортированный по A, найдите индексы 5 и 15, и вы получите (намного) меньший список (все индексы между ними), где вы должны проверить другие поля (B, C и IsRoot).

Delphi (2009+) реализация отсортированного списка: DeHL.Collections.SortedList

Answer 2

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

Это устройство хорошее начало, но я думаю, что проще скачать полный исходный код и просмотреть файлы: http://tiopf.svn.sourceforge.net/viewvc/tiopf/tiOPF2/Trunk/Core/tiFilteredObjectList.pas?revision=1469&view=markup

В этом решении, вероятно, используется много RTTI: просто создайте список с фильтрами (именами и значениями свойств) и зацикливайте объекты. Это обеспечит вам максимальную гибкость, но за счет некоторой скорости. Если вам нужна скорость, думаю, решение от Ulrichb будет лучше.

Answer 3

Идея № 1

Запустите ваш код в профилировщике. Узнайте, есть ли медленные пятна.

Идея № 2

Возможно, вы сможете воспользоваться эффектами кэша, последовательно сохраняя свои объекты в памяти. (Я предполагаю, что вы просматриваете список последовательно от начала до конца.)

Одним из способов сделать это может быть использование массива записей вместо списка объектов. Если это возможно в вашем случае. Помните, что записи в Delphi 2006 могут иметь методы (но не виртуальные).

Другая идея может состоять в том, чтобы написать собственный распределитель классов. Я никогда не пробовал, , но вот статью, которую я нашел. Может быть, попробуйте пройтись по объектам, используя указатель вместо TObjectList.

Answer 4

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

Я уверен, что вы не хотите реализовывать полноценный оптимизатор запросов, поэтому вот несколько советов о том, как сделать ваши запросы достаточно быстрыми:

(1) Выберите некоторые поля, которые часто используются в ваших запросах, и настройте для них индексы. Эти поля должны обеспечивать хорошую селективность: не индексируйте по «логическому» значению, вы просто потеряете время на обход сложных структур двоичного поиска, когда вы можете так же быстро (или быстрее) просмотреть весь список!

(2) Для каждого данного запроса выберите ONE отдельный индекс, чтобы предварительно отфильтровать данные и применить все остальные фильтры по одному (без оптимизации).

В вашем примере: создайте индексы в полях "A" и "B". Кажется, что «C» - это функция, которую невозможно проиндексировать. «IsRoot», похоже, возвращает логическое значение, индексирование не стоит.

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

Answer 5

Если количество атрибутов для фильтрации мало и их можно отсортировать, почему бы не иметь несколько списков, каждый из которых отсортирован по другому атрибуту? Каждый список стоит 4 байта на объект для ссылки, плюс небольшие накладные расходы для самого списка. Конечно, все зависит от того, могут ли быть выполнены требования к памяти. 2 ГБ не так много, если вы имеете дело с большим количеством объектов ...

Answer 6

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

Если количество объектов велико, я бы подумал об использовании базы данных в памяти и использовании SQL для выполнения запроса. Затем база данных может использовать индексы, чтобы найти вещи как можно быстрее, и вы перекладываете бремя на проверенный инструмент. Лично я использую DBISAM или ElevateDB, но другие тоже будут делать базы данных в памяти. Используя реальный инструмент базы данных, вы можете легко перемещать данные на диск, если они становятся действительно большими.