Si j'ai un tableau de clés M et un tableau de cibles N, comment puis-je vérifier que M [i] existe dans N avant de le rechercher?

Question

Comme le titre l'indique, j'essaie de trouver des éléments de M qui existent dans le grand tableau constant N. La plupart du temps, aucun élément de M n'existera dans N, donc la grande majorité des recherches effectuées sur M sont un perte de temps.

Je cherche un moyen de créer un index à vérifier avant de faire une recherche à grande échelle de M. Un projet similaire au mien crée un tableau de bits à partir des premiers octets de chaque élément de M, et de quoi Je comprends, exploite le parallélisme au niveau des bits pour le rechercher rapidement. Je ne comprends pas entièrement comment cela fonctionne.

Alors, quelles astuces puis-je utiliser pour réduire les chances de chercher M inutilement?

Ceci est une question principalement indépendante de la langue, mais pour être aussi complète que possible, j'utilise C++.

Answer 1

Vous pourriez penser à Bloom filters, qui sont utilisés exactement dans ce cas. Ils peuvent vous donner des faux positifs, auquel cas vous devez chercher dans la vraie table, mais dans la plupart des cas, vous serez informé dès le début si vous n'avez pas stocké l'objet.

Les tables de hachage sont généralement la meilleure option pour le stockage; mais si votre espace clé est considérablement plus grand que le nombre de cibles, vous aurez un nombre important de collisions de hachage où vous devrez vérifier si la cible stockée là est vraiment la clé que vous cherchez. Si la comparaison des clés est coûteuse, elle peut rapidement devenir un facteur.

Answer 2

Vous pouvez créer une table de hachage avec les valeurs de N sous forme de clés.

Ensuite, vous essayez d'accéder à hachage [M [i]], si elle retourne une valeur, alors il existe, qui est O (1) (collisions sans tenir compte.)

Answer 3

Puisque N est vous statique peut-être envisager la création d'un Perfect Hash fonction pour N. Cela va faire votre recherche garanti O (1) temps.

Le livre CLR sur les algorithmes comporte un chapitre sur ce sujet et la page wiki ci-dessus contient des liens que vous pourriez trouver utiles. Il pourrait être trop compliqué, bien que et vous pourriez avoir du mal à trouver une implémentation utile. . Regardez Gperf pour une implémentation.

Vous pouvez toujours utiliser une table de hachage généralement disponible avec O (1) attendu.

Je suppose que vous stockez des informations supplémentaires que vous souhaitez récupérer sachant qu'il est là? Comment les stockez-vous?

Vous pourriez trouver un B-Tree utile dans ce cas (les bases de données standard de l'industrie en utilisent généralement une variante), qui pourraient même servir d'index! Donc, vous recherchez, et si vous le trouvez, vous avez les données/pointeur vers lui. Vous trouverez de nombreuses implémentations pour ceux-ci sur le web.