Algorithme de hachage rapide pour la cartographie / quantification d'une collection de flotteurs sur un petit ensemble de flotteurs triés

Question

avec ma demande, j'ai

• Collection X: Des milliers de nombres à virgule flottante avec la plage de valeurs [0, 1], non triés.
• Collection Y: 11 Flotts allant de [0, 1], triés.
• La taille de x est connue. Laissez-le être l.

L'objectif est de quantifier x et de la cartographier sur Y, de sorte que nous obtenons une gamme de hachage d'indices de y pour X. Finalement, y sera ensuite quantifié sur 10 choses discrètes pointées sur 10.

Un exemple pour le rendre un peu plus clair,

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

Je veux que la sortie d'algorithme soit des indices à base de 0:

• 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

tentatives

naïvement, j'ai essayé la recherche linéaire et binaire de positionner chaque élément de x dans Y de sorte que l'élément se trouve entre une paire d'éléments adjacents dans Y.

Cependant, la performance n'est pas assez bonne pour ma demande. Cette quantification se produit dans un fil de temps réel que le calcul lent est indésirable.

Question

Quel est le meilleur moyen de ce genre de hachage / quantification? X n'est pas trié.

merci!

Answer 1

Prendre x, multiplié par dire 10 000, arrondi à l'entier le plus proche. Dans ordinaire c, z= (int) (x fois 10000.0).

Il y a 10 000 valeurs possibles de z. Pour la plupart des valeurs de Z, vous pouvez déterminer l'index de z. Donc, créez une table avec 10 000 entrées. Dans le tableau, stockez un index i si vous pouvez prouver que X doit être mappé sur I, en connectant Z et Store -1 si vous ne pouvez pas prouver cela.

En conséquence, vous obtenez la valeur correcte probablement dans 9 980 sur 10 000 valeurs, puis vous utilisez tout ce que vous avez lent que vous avez pour les 1 valeurs restantes en 500.

ps. La même taille de table serait utilisée pour les numéros de double précision. Quelle que soit la taille de la table, il n'y aura que peu de valeurs X qui ne peuvent pas être cartographiées correctement à l'aide de cette méthode, peut-être 10 ou 20. Si vous prenez une table de taille 10 000, puis de 99,8% ou 99,9% sont cartographiées correctement et 0,1% ou 0,2% besoin d'un algorithme lent. La même chose est exacte avec le double. Vous pouvez utiliser 1000 entrées, puis les 10 ou 20 défaillances seraient 1% ou 2%.

Et une bonne chose est que cette méthode fonctionnera toutefois que les valeurs Y sont distribuées. Seulement si le nombre de valeurs Y est plus grand, vous voudrez peut-être augmenter la taille de la table.