recherche booléenne sur un tableau

Question

J'ai plusieurs tableaux avec une centaine de valeurs possibles :

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

Je veux retourner RAPIDEMENT les tableaux qui contiennent (a || b) && (d || e).

dans cet exemple, 0 et 1

Je pensais à des opérations par bit... comme représenter "abcd" par "1111" ; "ad" par "1001", et ainsi de suite. Je pourrais alors résoudre le "OR" avec un simple OR par bit, puis vérifier que les deux sont différents de zéro.

quelqu'un peut-il penser à une meilleure solution ? celle-ci n'est pas très pratique puisqu'elle ne semble pas être très évolutive.

Existe-t-il un SGBD capable de faire cela rapidement ? J'ai essayé avec mongodb, mais il semble qu'ils n'aient pas encore ajouté la fonction "$and" (la doc dit que c'est la version 1.9.1, mais je ne peux télécharger que la 1.9.0, et ce n'est pas stable de toute façon).

Je suppose que c'est une "recherche booléenne", similaire à ce que google fait tout le temps... donc j'imagine qu'il y a une meilleure façon (peut-être moins rapide, mais plus évolutive) que ça.

Answer 1

Oui, une solution bit à bit fonctionne très bien pour cela. Oui, certaines bases de données incluent une telle capacité, généralement appelée colonne bitmap (ou index bitmap, selon le cas). Le conseil habituel est de l'appliquer à une colonne qui a une cardinalité relativement faible (c'est-à-dire un nombre assez restreint de valeurs possibles, comme le sexe).

Answer 2

Dans quel sens n'est-il pas évolutif ? 16 octets de données par tableau (de bits), ce n'est pas mal ! Je ne vois pas pourquoi vous avez besoin d'un SGBD pour cela ; vous pouvez y mettre des données binaires si nécessaire (en espérant que ce soit des blocs de tableaux), et les extraire pour les interroger. A moins que vous ne prévoyiez d'avoir des milliards de tableaux.

Pour un petit nombre d'éléments, la logique binaire est la plus rapide. Mais si vous commencez à dépasser les 100 valeurs, le tri des tableaux et la recherche binaire (ou même linéaire !) seront plus rapides. Vous devrez faire un test sur votre système pour trouver le seuil exact, mais si vos tableaux ont ~4 éléments chacun, je trouve généralement que la recherche linéaire est plus rapide (en comptant les occurrences des éléments que vous recherchez dans la logique booléenne au fur et à mesure), et qu'elle bat les mathématiques binaires à peu près au moment où les représentations binaires deviennent aussi plus grandes.

Answer 3

Stockez vos tableaux comme une trie, par exemple,

a
 b
  c
   d
 e
d
 f
  g

Créez également une trie à partir de l'expression, par exemple,

a
 b
  d
  e
 d
 e
b
 d
 e

Vous pouvez faire correspondre le dernier trie avec le premier (en ignorant toutes les valeurs qui ne sont pas dans l'expression, c'est-à-dire 'c', 'f' et 'g') pour obtenir les solutions. Je vous laisse le soin de régler les détails de la représentation du trie et de l'algorithme de correspondance.

Answer 4

Comme vous l'avez dit, les valeurs possibles sont d'environ 100, mais vous avez beaucoup de tableaux, je pense qu'une table de hachage est plus efficace que les opérations au niveau du bit.
Eg.
avoir une table de hachage définie avec les valeurs de l'expression, c'est-à-dire a, b définis à 1 et d, e définis à 2.

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

(ce qui précède n'est pas valable pour les doublons !)
la première boucle for peut être parallélisée, probablement avec un framework map-reduce ou même openMP.
(en fait, le deuxième pour peut aussi être parallélisé !)
Cela devrait être plus rapide que de construire une représentation binaire de tous les éléments du tableau et de faire un ET ou un OU. Vous bénéficiez essentiellement du meilleur cas (par exemple, a et d sont les deux premiers éléments !) et du pire cas, qui est le même pour les deux méthodes (il se peut que le traitement de chaque élément soit surchargé).