floating point - recorte - ¿Una buena forma de cortar un vector flotante?

herramienta cuchilla illustrator

Question

Estoy al tanto 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 los valores que son vectores 3D (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 tome valores que sean casi iguales al mismo valor int sin firmar y un operador de igualdad correspondiente que sea verdadero si los valores hash son iguales (no necesariamente solo si son iguales)

Editar -
Los falsos positivos (es decir, vectores que son diferentes pero se asignan al mismo cubo) son un dato dado que 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

¿Necesita 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. Un B-Tree minimiza el número de errores de caché, suponiendo que elija el tamaño de nodo correcto. Eso debería hacerlo bastante rápido en la práctica.

Answer 2

¿Puedes colaborar en tu 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 usar vectores que son el resultado de diferentes cálculos para realizar la búsqueda hash, se está configurando a sí mismo la posibilidad de no tener códigos hash coincidentes debido a errores de redondeo y probablemente debería estar usando otra cosa de todos modos.

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

Convertiría los valores float en enteros como este:

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

entonces obtienes algunos de los primeros dígitos y luego usas

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

como 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 5

Creo que efectivamente estás tratando de resolver el problema más cercano a K. Creo que lo que estás buscando es hash sensible a la localidad . También puede usar estructuras de árbol cuádruple para lograr el mismo resultado.

Answer 6

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 fueras a dibujar estos puntos en una imagen:

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

Supongamos que todas las brechas están separadas <1e-3, pero A y Z están separadas> 1e-3 (¡no a escala!). Esto no se puede satisfacer porque si hash (A) == hash (B) y hash (B) == hash (C) y así sucesivamente para todos los pares, (ya que están <1e-3 separados) 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 mezclarlos), pero aún podría obtener 2 vectores en los bordes de sus respectivos espacios que están 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 7

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 un 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.