Rápido algoritmo de hash para la asignación/cuantización de una colección de carrozas en un pequeño conjunto de ordenadas de carrozas

Question

Con mi solicitud, me han

• De La Colección De X:miles de números de punto flotante con el valor del intervalo [0, 1], no clasificados.
• Colección Y:11 carros que van desde [0, 1], ordenados.
• El tamaño de X es conocido.Vamos a ser L.

El objetivo es cuantizar X y mapa en marcha, por lo que conseguimos un hash de la matriz de índices de Y en X.Finalmente Y luego será cuantificada en 10 cosas discretas señaló a ella.

Un ejemplo para que quede un poco más claro,

• Y = [0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 1.0]
• X = [0.678, 0.124, ..., 1.0, ., 0.013, 0.475]

Quiero que el algoritmo de la salida de 0 basado en índices como estos:

• H(Y[0]) = H(0.678) = 6
• H(Y[1]) = H(0.124) = 1
• H(Y[n-2]) = H(0.013) = 0
• H(Y[n-1]) = H(0.475) = 4

Los intentos de

Ingenuamente, he intentado lineal y binario de búsqueda para el posicionamiento de cada elemento de X en Y, de modo que el elemento se encuentra entre un par adyacente de los elementos de Y.

Sin embargo, el rendimiento no es lo suficientemente bueno para mi aplicación.Esta cuantización sucede en tiempo real de hilo que lento cálculo es indeseable.

Pregunta

¿Cuál es la mejor manera de este tipo de hash/cuantización?X no está ordenada.

Gracias!

Answer 1

TOMAR X, multiplicado por 10,000, redondeado hasta el entero más cercano. En plena c, z= (int) (x veces 10000.0).

Hay 10,000 valores posibles de Z. Para la mayoría de los valores de Z, puede determinar el índice de Z. Así que crea una tabla con 10,000 entradas. En la tabla, almacene un índice I si puede probar que X debe ser asignado a I, saber z, y almacenar -1 si no puede probar esto.

Como resultado, obtiene el valor correcto probablemente en 9.980 de 10,000 valores, y luego usa el algoritmo lento que tenga para los valores restantes 1 en 500.

ps. El mismo tamaño de tabla se utilizaría para números de doble precisión. Cualquiera que sea el tamaño de la tabla, solo habrá pocos valores x que no se pueden asignar correctamente con este método, quizás 10 o 20. Si toma una tabla de tamaño 10,000, 99.8% o 99.9% se asignan correctamente y al 0,1% o 0.2% Necesito un algoritmo lento. Exactamente lo mismo sucede con el doble. Puede usar 1000 entradas, luego los 10 o 20 fallectemente serían del 1% o 2%.

y una cosa agradable es que este método funcionará, sin embargo, se distribuyen los valores y. Solo si el número de valores y es mayor, es posible que desee aumentar el tamaño de la tabla.