Meilleure structure de données pour la recherche?

Question

J'ai une liste avec des éléments où chacun a un certain nombre de propriétés (A, B, C, D) que je voudrais filtrer en utilisant un modèle contenant les mêmes attributs (A, B, C, D). Lorsque j'utilise un modèle, je voudrais filtrer tous les éléments correspondant à ce modèle. La correspondance est supposée si l'élément est égal au modèle ou si sa sous-séquence est plus petite (0 correspond à n'importe quel élément).

Exemple de données

A B C D 
1 0 1 0 
2 0 0 0 
0 0 2 3 
2 0 2 1 
2 0 2 0 
0 0 0 0 

Exemple Modèles

[2 0 0 0] will filter {[0 0 0 0], [2 0 0 0]} 
[2 0 2 0] will filter {[0 0 0 0], [2 0 0 0], [2 0 2 0]} 
[2 0 2 1] will filter {[0 0 0 0], [2 0 2 1]} 
[3 4 5 6] will filter {[0 0 0 0]} 
[0 0 2 0] will filter {[0 0 0 0], [0 0 2 3], [2 0 2 1], [2 0 2 0]} 

Le problème est que nombre de comparaisons peut facilement atteindre 300k et peut obtenir parfois lent. Quelles astuces ou quelle structure pourrais-je utiliser pour accélérer les choses? Des idées?

Answer 1

En supposant 4 propriétés, Plaçons tous les éléments en 16 seaux.

Le premier compartiment correspond à l'absence de valeurs nulles pour les propriétés. Sélection d'ici - simple recherche basée sur la clé ABCD.

Le deuxième compartiment correspond à la propriété A == 0. La sélection d'ici est une recherche sur le modèle avec la valeur de BCD.

Le troisième compartiment est où B == 0. La sélection d'ici est une recherche sur le modèle avec la valeur de ACD.

Quatrième est où A == 0 et B == 0. La sélection d'ici est une recherche sur le modèle avec la valeur de CD.

....

Quinzième est où A, B, C == 0. la recherche est sur D.

Seizième est où A, B, C, D == 0. Cela peut être une variable booléenne ;-)

Puisque tous les 16 compartiments sont 'correspondance exacte' - vous pouvez utiliser des méthodes comme des tables de hachage pour la recherche à l'intérieur.

(cette proposition est basée sur l'hypothèse que c'est 0 dans la valeur prop qui compte comme 'correspondre à' et non dans le modèle.) - parce que 2000 a sélectionné une seule valeur dans votre exemple. il sera évidemment incorrect si la sémantique est 'any' aux deux endroits.

-

mise à jour: Corollaire: vous pouvez avoir plus de 2^nPropriétés correspond.

Exemple:

Supposons que nous avons 3 propriétés A, B, C et les quatre éléments suivants:

itemX[A=1, B=0, C=1] ---> B is a wildcard, so bucketAC[11] = itemX 
itemY[A=2, B=0, C=0] ---> B and C are wildcards, so bucketA[2] = itemY 
itemZ[A=2, B=1, C=0] ---> C is a wildcard, so bucketAB[21] = itemZ 

maintenant, la recherche d'un serait comme 'abc' clé suivante (I comprennent également le droit des contenu des seaux pour faciliter la lecture, et « < < » « accumulate » signifie dans ce contexte)

1.results << bucketA[a]  | '2' => itemY[A=2, B=0, C=0] 
2.results << bucketB[b]  
3.results << bucketAB[ab]  | '21' => itemZ[A=2, B=1, C=0] 
4.results << bucketC[c] 
5.results << bucketAC[ac]  | '11' => itemX[A=1, B=0, C=1] 
6.results << bucketBC[bc] 
7.results << bucketABC[abc] 
8.results << bucket_item_all_wildcards 

Donc, si nous utilisons le modèle [2 0 0], nous obtenons les résultats de la clé étant A = 2 dans bucketA seulement. Si nous utilisons le gabarit [2 1 0], alors nous obtenons les résultats de la clé étant A = 2 dans le seauA, et de la clé étant AB = 21 dans le seauBAB - deux résultats. NB: Bien sûr, la notation ci-dessus pour les clés est plutôt frivole, elle suppose simplement "un accès de type hashtable avec la concaténation desdites propriétés étant la clé".

Si vous êtes autorisé à avoir plusieurs fois les éléments avec les mêmes propriétés, vous aurez besoin de plusieurs éléments dans certains emplacements - et alors, évidemment, vous pouvez avoir plus de résultats de recherche que 2^Nproperties, néanmoins vous pouvez suivre le nombre maximum de doublons et donc toujours prédire le nombre maximum d'éléments dans le cas le plus défavorable. Notamment, si le nombre de propriétés augmente, le nombre total possible de godets va rapidement exploser (par exemple, 32 propriétés signifieraient plus de 4 milliards de godets maximum), donc cette idée ne sera plus applicable directement, et serait besoin d'autres optimisations autour de la traversée/allocation des compartiments

Answer 2

Qu'en est-il des cartes de hachage imbriquées? Par exemple, un élément "il" sera stocké comme:

map(it.A)(it.B)(it.C).(it.D) = it 

So [2 0 2 0] pourrait être recherché comme:

map(2).keys.(2).keys