Algoritmo di hashing veloce per la mappatura / quantizzazione di una raccolta di galleggianti su un piccolo set di galleggianti ordinati

Question

Con la mia applicazione, ho

.
• Collezione x: migliaia di numeri a virgola mobile con il campo di valore [0, 1], non ordinato.
• Collezione Y: 11 Galleggianti che vanno da [0, 1], ordinate.
• è nota la dimensione di x. Lascia che sia l.

L'obiettivo è quello di quantizzare X e mapparlo su y, in modo che otteniamo una serie di indici di Ash per X. Alla fine y verrà quindi quantizzata su 10 cose discrete indicano.

Un esempio per renderlo un po 'più chiaro,

.
• 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]

Voglio che l'output dell'algoritmo sia da indici basati su 0 come queste:

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

tentativi

ingenuamente, ho provato la ricerca lineare e binaria per posizionare ciascun elemento di x in y in modo che l'elemento sia riscontrato tra una coppia adiacente di elementi in y.

Tuttavia, la performance non è abbastanza buona per la mia applicazione. Questa quantizzazione avviene in un thread in tempo reale che il calcolo lento è indesiderabile.

domanda

Qual è il modo migliore di questo tipo di hashing / quantizzazione? X non è ordinato.

Grazie!

Answer 1

Prendere X, moltiplicato per dire 10.000, arrotondato fino al numero intero più vicino. In normale c, z= (int) (x volte 10000.0).

Ci sono 10.000 possibili valori di z. Per la maggior parte dei valori della Z, è possibile determinare l'indice da z. Quindi crea un tavolo con 10.000 voci. Nella tabella, memorizza un indice I Se è possibile dimostrare che X dovrebbe essere mappato a I, conoscendo Z e Store -1 se non puoi dimostrarlo.

Di conseguenza, si ottiene il valore corretto probabilmente in 9.980 di 10.000 valori, quindi si utilizza qualsiasi algoritmo lento che hai per il restante 1 su 500 valori.

PS. La stessa dimensione della tabella sarebbe utilizzata per numeri di precisione doppia. Qualunque sia la dimensione della tabella, ci saranno solo pochi valori X che non possono essere mappati correttamente utilizzando questo metodo, forse 10 o 20. Se si prende una tabella di taglia 10.000, il 99,8% o il 99,9% sono mappati correttamente e 0,1% o 0,2% bisogno di un algoritmo lento. La stessa identica cosa accade con il doppio. Potresti usare 1000 voci, quindi i 10 o 20 fallimenti sarebbero dell'1% o del 2%.

E una bella cosa è che questo metodo funzionerà tuttavia i valori Y sono distribuiti. Solo se il numero di valori Y è maggiore, è possibile aumentare la dimensione della tabella.