логический поиск по массиву

Question

У меня есть несколько массивов с около 100 возможных значений, например:

a[0] = (a, b, c, d)
a[1] = (a, e)
a[2] = (d, f, g)

Я хочу БЫСТРО возвратить, какие массивы содержат (a || b) && (d || e)

в этом примере 0 и 1

Я думал о побитовых операциях ... как представление "abcd" как "1111";"объявление" на "1001" и так далее.Тогда я мог бы решить «ИЛИ» с помощью только побитового ИЛИ, а затем проверить, не являются ли оба ненулевыми

Кто-нибудь может подумать о лучшем решении?этот не очень практичный, так как кажется, что он не очень расширяемый

есть ли СУБД, способные сделать это быстро?Я пытался с mongodb, но, похоже, они еще не добавили функцию "$ and" (док говорит, что она на версии 1.9.1, но я могу загрузить только 1.9.0, и она все равно не стабильна)

Я полагаю, что это "логический поиск", похожий на то, что делает Google все время ... поэтому я предполагаю, что есть лучший способ (возможно, не такой быстрый, но более расширяемый), чем этот

Answer 1

Да, побитовое решение прекрасно работает для этого.Да, некоторые базы данных включают такую ​​возможность, обычно называемую растровым столбцом (или растровым индексом, в зависимости).Обычный совет - применять его к столбцу с относительно низким количеством элементов (т. Е. С довольно небольшим числом возможных значений, таких как пол).

Answer 2

Как вы сказали, возможные значения около 100, но у вас много массивов, я думаю, что хеш-таблица работает лучше, чем операции на битовом уровне.
Например,
имеет хеш-таблицу, установленную с помощьюзначения в выражении, т. е. a, b установлены в 1 и d, e установлены в 2.

for each array a in arrays      
  for each value v in array
    sum+= ht[v]
    if sum == 3
      print found
      break

(хотя выше не будет с дубликатами!)
первый цикл for может быть распараллелен, вероятнос каркасом сокращения карты или даже openMP.
(кстати, второе для также может быть распараллелено!)
Это должно быть быстрее, чем создание битового представления целых элементов в массиве и выполнение И или ИЛИ.Вы в основном выигрываете в лучшем случае (например, a и d - первые 2 элемента!), Худший случай одинаков для обоих методов (может быть, если выполняется для каждого элемента издержки)

Answer 3

Храните ваши массивы как три, например,

a
 b
  c
   d
 e
d
 f
  g

Создайте также три из выражения, например,

a
 b
  d
  e
 d
 e
b
 d
 e

Вы можете сопоставить последнее дерево с первым (игнорируя любые значения, которых нет в выражении, то есть 'c', 'f' и 'g'), чтобы получить решения. Я оставляю детали представления три и алгоритм сопоставления на ваше усмотрение.

Answer 4

В каком смысле это не масштабируется?16 байтов данных на один (бит) массив - это неплохо!Я не уверен, почему вы хотите СУБД для этого;вы можете поместить туда двоичные данные, если вам нужно (надеюсь, блоки массивов), и вытащить все это для запроса.Если вы не планируете иметь миллиарды массивов.

Для небольшого числа элементов битовая логика является самой быстрой.Но если вы начнете превышать 100 значений, сохранение массивов и выполнение двоичного (или даже линейного!) Поиска будет быстрее.Вам нужно будет провести эталонный тест в вашей системе, чтобы найти точную точку отсечения, но если в ваших массивах по ~ 4 элемента каждый, я обычно нахожу линейный поиск быстрее (подсчитывая вхождения элементов, которые вы ищете в булевой логике, каквы идете), и что он бьет двоичную математику примерно в той же точке, что двоичные представления также становятся больше.