Un buon modo per cancellare un vettore float?

Question

Sono ben consapevole di tutti i problemi relativi al confronto dei galleggianti. Questo è esattamente il motivo di questa domanda.
Sto cercando di creare una tabella hash veloce per valori che sono vettori 3D (3 float - x, y, z). Si può presumere che la lunghezza del vettore sia sempre 1.0 (sqrt(x*x+y*y+z*z) è 1.0)

In sostanza, ciò significa che sto cercando una funzione di hash che accetta valori quasi uguali allo stesso valore int non firmato e una corrispondente operatore di uguaglianza che è true se i valori di hash sono uguali (non non necessariamente solo se sono uguali)

Modifica -
falsi positivi (cioè vettori che sono diversi ma mappano lo stesso secchio) sono un dato di fatto in quanto questa è una tabella hash.
I falsi negativi (vale a dire i vettori che sono vicini ma mappati a diversi contenitori) non sono desiderabili ma sembra che non ci sia modo di evitarli. Nel mio caso, non causeranno la rottura totale, solo alcuni dati duplicati che è qualcosa con cui dovrò convivere.

Answer 1

mi piacerebbe convertire i valori decimali in numeri interi in questo modo:

unsigned int IntValue = (int)(floatValue * MULT) + MULT; 

in modo da ottenere alcune delle prime cifre e quindi utilizzare

const MULT1 = (MULT << 1) + 1; 
unsigned long long HashValue = (xIntValue * MULT1 * MULT1) + (yIntValue * MULT1) + zIntValue; 

come valore di hash (utilizzando (MULT * 2) + 1 perché gli IntValues ​​saranno compresi tra 0 e MULT * 2 inclusi).

La memoria necessaria dipenderà dal moltiplicatore MULT. Ad esempio, utilizzando 32 otterrai una tabella hash che utilizza 64 * 64 * 64 * (dimensione elemento hash) = 262144 * (dimensione elemento hash).

Answer 2

Penso che quello che stai cercando non sia direttamente possibile. Un'importante proprietà dell'eguaglianza è che è transitiva. (cioè se a == b eb == c, quindi a == c). Con una misura di distanza, però, davvero non vuoi questa proprietà. Esempio:

Prendere un singolo galleggiante (per semplicità). Supponiamo di voler eseguire l'hash di ogni float in modo che fluttuino a meno di 1e-3 di distanza abbiano lo stesso valore. Ora, supponiamo di aggiungere a questa tabella hash 1000 valori float tutti 1e-4 diversi. Qualsiasi valore confinante con 2 dovrebbe avere lo stesso valore di galleggiamento, poiché sono più vicini di 1e-3. Tuttavia, a causa della transitività, anche i vicini di tali valori devono avere lo stesso valore, i loro vicini e così via. Di conseguenza, tutti i 1000 valori, comprese le coppie più lontane di 1e-3, equivarrebbero allo stesso numero intero. Se si dovesse richiamare questi punti su una foto:

A B C D E F G H ... Y Z 

Supponiamo che tutte le lacune sono < 1e-3 a parte, ma A e Z sono> 1e-3 a parte (non in scala!). Questo non può essere soddisfatto perché se hash (A) == hash (B) e hash (B) == hash (C) e così via per tutte le coppie, (poiché sono < 1e-3 a parte) dell'hash (A) deve == hash (Z).

Una possibile opzione è quella di definire le regioni dello spazio vettoriale in cui tutti i vettori eseguiranno lo stesso valore (ad esempio arrotondandoli prima di eseguirne l'hashing), ma è comunque possibile ottenere 2 vettori sui bordi dei rispettivi spazi che sono vicini insieme ma hash ad un valore diverso. Puoi aggirare questo cercando tutti gli spazi vicini per un vettore. (cioè nel caso 1-d sopra, arrotolerai tutti i vettori al multiplo più vicino di 1e-3, e poi cercherà i vicini, quindi 5.3e-3 cercherà 5e-3, 4e-3 e 6-e3. Nei casi di dimensioni superiori, dovresti cercare i vicini in tutte le dimensioni.)

Answer 3

Alcune lingue (C, Java 5) consentono di accedere al valore binario dei float. In questo modo, puoi estrarre i primi N bit della mantissa (ignorando gli ultimi bit che causano il problema durante il confronto) e calcolare l'hash da quello.

Answer 4

Puoi collaborare al tuo problema?

Supponendo che si stia utilizzando una mappa di hash per mappare alcuni dati aggiuntivi su vettori specifici, si potrebbe semplicemente utilizzare lo XOR delle rappresentazioni binarie dei componenti (se ciò è possibile nella lingua scelta). Quindi usa tanti LSB (per ridurre le collisioni) di cui hai bisogno per la mappa hash. Questo ovviamente avrebbe la proprietà che due vettori uguali (per confronto a virgola mobile) potrebbero non avere lo stesso hash (ad es. Il punto mobile IEEE 0 è uguale a -0, ma hanno un bit di segno diverso).

Tuttavia, se si prevede di utilizzare i vettori risultati di calcoli diversi per eseguire la ricerca hash, ci si sta impostando sulla possibilità di non avere codici di hash corrispondenti a causa di errori di arrotondamento e si dovrebbe probabilmente utilizzare qualcos'altro Comunque.

Answer 5

non so quanto veloce possa essere, ma dato che hai i vettori unitari, tutti giacciono sulla superficie di una sfera. convertire in un http://en.wikipedia.org/wiki/Spherical_coordinate_system. quindi usa phi e theta per scegliere un secchio. non ci saranno falsi positivi. puoi guardare nelle celle vicine per falsi negativi.

Answer 6

Ti serve una tabella hash veloce o una struttura ad albero?

Mi sembra che sarebbe più facile cercare i galleggianti corrispondenti in un albero di ricerca di alcuni ordinamenti . A B-Tree minimizza il numero di errori di cache, assumendo che si scelga la giusta dimensione del nodo. Ciò dovrebbe essere abbastanza veloce nella pratica.

Answer 7

Penso che tu stia effettivamente cercando di risolvere il problema più vicino a K. Credo che quello che stai cercando è locality sensitive hashing. Inoltre è possibile utilizzare strutture ad albero quad per ottenere lo stesso risultato.