Проблема в следующем.
- Есть набор простых объектов E, к каждому из которых прикреплен набор тегов T. Каждый объект может иметь произвольное количество тегов. Общее количество объектов составляет около 100 миллионов, а общее количество тегов составляет около 5000.
Итак, исходные данные примерно такие:
E1 - T1, T2, T3, ... Tn
E2 - T1, T5, T100, ... Tk
..
Ez - T10, T12, ... Tl
Эти исходные данные довольно редко обновляются.
Каким-то образом мое приложение генерирует логическое выражение для таких тегов:
T1 & T2 & T3 | (T5 &! T6)
Что мне нужно, это рассчитать количество объектов, соответствующих данному выражению (примечание - не объекты, а просто число). Это может быть не совсем точно, конечно.
Теперь у меня есть простой просмотр таблицы в памяти, который дает мне 5-10 секунд времени выполнения в одном потоке.
Мне любопытно, есть ли эффективный способ справиться с этим? Какой подход вы бы порекомендовали? Существуют ли общие алгоритмы или структуры данных для этого?
Обновить
Немного разъяснений по запросу.
T
объекты на самом деле являются относительно короткими постоянными строками. Но на самом деле это не имеет значения - мы всегда можем присвоить некоторые идентификаторы и оперировать целыми числами.- Мы определенно можем их отсортировать.
T1
та же ссылка на объект дляE1
,E2
и т.д.?T2 < T3
это всегда было правдой?T1
либоtrue
илиfalse
для данногоE
, а не переменные на основе входных данных? (т.е.Model = "V5"
) ИлиT1
переменное выражение похожеModel = <input>
?Ответы:
Я хотел бы сделать это в SQL, имеющей таблицу ссылок
EntityCategory
междуeid
ссылочной сущностью иcid
ссылочной категорией с помощью самостоятельных соединений:источник
После написания этого ответа, я, вероятно, должен пометить вопрос как «слишком широкий» - мы можем целую вечность говорить о различных стратегиях, в конце необходимо будет провести эталон с вашими данными.
Каждый тег может быть эффективно представлен целым числом. У каждой сущности есть набор тегов. Важно выбрать правильную реализацию набора - возможны как B-деревья, так и отсортированные массивы. С этим набором мы будем проводить только тесты членства. Поскольку обе структуры делают это в O (log t) (с t тегами на объект), я бы предпочел массивы из-за их более плотного представления.
Теперь мы можем отфильтровать все сущности в операции O (n · log t · p) , где p - средняя длина пути в дереве решений предиката. Это дерево решений можно упорядочить, чтобы быстро принять решение. Без статистических данных можно выделить только общие подвыражения.
Порядок, в котором ищутся объекты, не очень важен. С другой стороны , это может быть выгодно , чтобы отсортировать его таким образом, что объекты с индексами
0
дляi
всех есть определенный тег, в то время как остальные не делает. Это уменьшает n при поиске этого конкретного тега (в дереве решений это должен быть первый тест). Это может быть расширено до нескольких уровней, но это усложняет вещи и занимает O (2 k ) памяти с kуровни. При наличии нескольких уровней сначала следует определить теги с наибольшим усилением, где усиление - это число объектов, которые не нужно искать, умноженное на вероятность их отбрасывания. Усиление становится максимальным для шансов 50:50 или когда 50% объектов имеют этот конкретный тег. Это позволит вам оптимизировать, даже если шаблоны доступа неизвестны.Вы также можете создавать наборы, которые индексируют объекты по каждому используемому тегу - один набор со всеми объектами для
T1
, другой дляT2
. Очевидная (пространственно-временная) оптимизация состоит в том, чтобы останавливаться, когда набор содержит более половины всех элементов, и сохранять те элементы, у которых нет этого тега - таким образом, создание индексов для всех тегов займет меньше½ · n · t
места (с т тегов всего). Обратите внимание, что сохранение дополнительных наборов может усложнить другие оптимизации. Опять я бы (отсортировал) массивы для наборов.Если вы также представляете свои сущности через целочисленный диапазон, вы можете сжать пространство, используемое для наборов индексов, сохранив только начальный и конечный член непрерывного диапазона. С точки зрения реализации это, вероятно, будет сделано с старшим битом, чтобы указать, является ли запись ограниченным диапазоном или обычной записью.
Если у нас теперь есть наборы индексов (и, следовательно, статистика по тегам), мы можем оптимизировать наши предикаты, чтобы сначала проверялись маловероятные свойства (стратегия быстрого отказа). Это означает, что если оно
T1
является общим иT2
редким, то предикатT1 & T2
должен оцениваться путем итерации всехT2
записей набора индексов и проверки каждого элементаT1
.Если мы используем отсортированные массивы для реализации наборов индексов, то многие этапы оценки могут быть реализованы как операции слияния.
T1 & T2
означает , что мы принятьT1
иT2
списки, выделить целевой массив размера больших входов и выполнить следующий алгоритм , пока оба вход не являются пустым: ЕслиT1[0] < T2[0]
, тоT1++
(отбрасывать голова). ЕслиT1[0] > T2[0]
тогдаT2++
. Если оба головки равны, то скопируйте этот номер в целевом массив, и увеличивают все три указателя (T1
,T2
, целевые). Если предикат естьT1 | T2
, то ни один элемент не отбрасывается, но копируется меньший элемент. Предикат формыT1 & ¬T2
также может быть реализован с использованием стратегии слияния, но¬T1
иT1 | ¬T2
не может.Это следует учитывать при упорядочении дерева предикатного решения: дополнения должны происходить либо в RHS
&
, либо в конце, когда определяется окончательное количество и фактические элементы не должны просматриваться.Без использования наборов индексов каждый поток может фильтровать свою часть сущностей и возвращать количество элементов, соответствующих предикату, которое можно суммировать. При использовании наборов индексов каждому потоку будет присвоен один узел в дереве решений. Он принимает два входных потока, которые соответствуют упорядоченным наборам, и возвращают объединенный поток. Обратите внимание, что каждый узел в дереве решений имеет соответствующий набор, который представляет все сущности, которые выполняют это подвыражение, и что из-за упорядочения наборов нет необходимости знать весь набор сразу, чтобы объединить их ,
Различные стратегии, такие как объединение индексированных наборов или фильтрация по списку объектов, могут быть в определенной степени объединены. Фильтрация имеет очень предсказуемую производительность. Если запрос очень специфичен, так что использование наборов индексов значительно сокращает пространство поиска, тогда операции слияния могут быть лучше. Важно отметить, что объединение множества больших входных наборов может привести к гораздо худшей производительности, чем поиск методом "грубой силы". Очень оптимизированный алгоритм подберет подходящую стратегию на основе размера ввода, структуры запроса и статистических показателей.
Кроме того, частичное кэширование результатов может быть полезным, если ожидается, что подобные запросы будут выполняться в будущем, даже если они не ускоряют начальный запуск.
источник