Recherche d'un vecteur 3D dans un tableau

Question

J'ai un grand nombre (> 1 million) de points tridimensionnels, un 3-tuple (x, y, z) qui prend des valeurs flottantes. Les points sont liés entre (0,0,0) et (Nx, Ny, Nz). Je suis intéressé à trouver l'indice d'un point provenant de certains calculs, disons R, qui est présent quelque part dans ce tableau. Quel est le moyen le plus rapide de le faire? Y at-il un O (1) algorithme pour rechercher R à travers le tableau? La bonne chose est que la distance entre deux points est toujours supérieure à 0,005.

J'ai pensé à la création d'une table de hachage pour stocker l'index de tous les points du tableau, mais je besoin d'une bonne fonction de hachage qui peut convertir (x, y, z) à un hachage unique, -clé. Y at-il une fonction de hachage simple qui peut faire cela? Y at-il une bibliothèque basée sur C qui va aider?

Une simple fonction de hachage qui je pense pourrait générer une clé de hachage unique est:

h(x,y,z) = 1000*x + 1000000*y + 1000000000*z 

Ceci est suivi par la création d'un autre tableau d'entiers P de taille = max (h), et mémoriser le indice de (x, y, z) à P [h (x, y, z)] (d'arrondi doit être pris en charge). L'inquiétude est la taille du tableau P - cette approche est-elle assez bonne pour ce problème?

Une alternative au hachage utiliserait k -d arbre. En termes de temps d'exécution, qui fonctionne mieux, approche de hachage-clé ou d'arbre?

(J'utilise C pour ce travail).

Answer 1

Je ne suis pas sûr si je comprends la question correcte, mais je ne peux pas laisser de commentaires. Juste un conseil pour trouver des valeurs dans les grands tableaux est min (tableau - la valeur que vous recherchez). Je trouve cela assez rapide, mais je ne suis pas sûr de la manière la plus rapide. Mais avec trouver votre valeur vous n'obtenez jamais O (1) au moins O (n);)