¿Una buena forma de cortar un vector flotante?

Question

Soy muy consciente de todos los problemas involucrados en la comparación de flotadores. Esta es exactamente la razón de esta pregunta.
Estoy buscando crear una tabla hash rápida para valores que son vectores tridimensionales (3 flotantes - x, y, z). Se puede suponer que la longitud del vector es siempre 1.0 (sqrt(x*x+y*y+z*z) es 1.0)

Esencialmente esto significa que estoy buscando una función hash que toma valores que son casi iguales al mismo valor int sin firmar y un correspondiente operador de igualdad que es cierto si los valores de hash son iguales (no no necesariamente sólo si son iguales)

Editar -
los falsos positivos (es decir, vectores que son diferentes pero se correlacionan con el mismo cubo) son un dado desde esta es una tabla hash.
Los negativos falsos (es decir, los vectores que están cerca pero se asignan a diferentes cubos) son indeseables, pero parece que no hay forma de evitarlos. En mi caso, no causarán una rotura total, solo una duplicación de datos que es algo con lo que tendré que vivir.

Answer 1

me gustaría convertir los valores de coma flotante en enteros como esto:

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

así que tienes algunos de los primeros dígitos y después usa

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

como un valor hash (usando (MULT * 2) + 1 porque los valores int estarán entre 0 y MULT * 2 inclusive).

La memoria necesaria dependerá del multiplicador MULT. Por ejemplo, al usar 32 obtendrás una tabla hash usando 64 * 64 * 64 * (tamaño de elemento hash) = 262144 * (tamaño de elemento hash).

Answer 2

Creo que lo que estás buscando no es directamente posible. Una propiedad importante de la igualdad es que es transitiva. (es decir, si a == b y b == c, entonces a == c). Sin embargo, con una medida de distancia, realmente no quieres esta propiedad. Ejemplo:

Tome un solo flotador (por simplicidad). Supongamos que queremos agrupar cada flotador para que flote a menos de 1e-3 de distancia tenga el mismo valor. Ahora, supongamos que agregamos a esta tabla hash 1000 valores flotantes separados por 1e-4. Cualquier valor 2 vecino debe hash al mismo flotante, ya que están más cerca de 1e-3. Sin embargo, debido a la transitividad, los vecinos de esos valores también deberían tener el mismo valor, y sus vecinos, etc. Como resultado, todos los 1000 valores, incluidos los pares más allá de 1e-3 aparte, harían hash al mismo número entero. Si se va a elaborar estos puntos en una imagen:

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

Supongamos que todos los huecos son < 1e-3 pedazos, pero A y Z son> 1e-3 aparte (no a escala). Esto no puede cumplirse porque si hash (A) == hash (B) y hash (B) == hash (C) y así sucesivamente para todos los pares, (ya que son < 1e-3 aparte) que hash (A) debe == hash (Z).

Una opción posible es definir regiones de su espacio vectorial en las que todos los vectores harían hash con el mismo valor (es decir, redondearlos antes de hash), pero aún podría obtener 2 vectores en los bordes de sus respectivos espacios que son muy juntos, pero hash a un valor diferente. Podrías solucionarlo buscando en todos los espacios vecinos un vector. (es decir, en el caso 1-d anterior, redondearía todos los vectores al múltiplo más cercano de 1e-3, y luego buscaría los vecinos, por lo que 5.3e-3 buscaría 5e-3, 4e-3 y 6-e3. En casos de dimensiones superiores, tendría que buscar vecinos en todas las dimensiones.)

Answer 3

Algunos idiomas (C, Java 5) le permiten acceder al valor binario de sus flotadores. De esta forma, puedes extraer los primeros N bits de la mantisa (ignorando los últimos bits que causan el problema durante la comparación) y calcular el hash a partir de eso.

Answer 4

¿Puede colaborar en su problema?

Suponiendo que está utilizando un hashmap para mapear algunos datos adicionales a vectores específicos, puede usar el XOR de las representaciones binarias de los componentes (si esto es posible en el idioma de su elección). Luego use tantos LSB (para reducir colisiones) como necesite para el mapa de hash. Por supuesto, esto tendría la propiedad de que dos vectores iguales (por comparación en coma flotante) podrían no tener el mismo hash (por ejemplo, el punto flotante IEEE 0 es igual a -0, pero tienen un bit de signo diferente).

Sin embargo, si está planeando utilizar vectores que son el resultado de diferentes cálculos para hacer búsqueda hash, se está configurando la posibilidad de no tener códigos hash coincidentes debido a errores de redondeo y probablemente debería estar utilizando otra cosa de todas formas.

Answer 5

no sé qué tan rápido podría ser esto, pero ya que tiene vectores unitarios, todos se encuentran en la superficie de una esfera. convertir a http://en.wikipedia.org/wiki/Spherical_coordinate_system. luego usa phi y theta para elegir un cubo. no habrá falsos positivos. puede buscar en las celdas vecinas para obtener falsos negativos.

Answer 6

¿Es necesario que sea una tabla hash rápida o una estructura de árbol?

Me parece que sería más fácil buscar flotantes coincidentes en un árbol de búsqueda de algún tipo de . Un B-Tree minimiza la cantidad de errores de caché, suponiendo que elige el tamaño de nodo correcto. Eso debería hacerlo bastante rápido en la práctica.

Answer 7

Creo que está tratando efectivamente de resolver el problema K más cercano. Creo que lo que estás buscando es locality sensitive hashing. También puede usar estructuras de árbol cuádruple para lograr el mismo resultado.