Rápido algoritmo de hash para mapeamento/quantização uma coleção de carros alegóricos para um pequeno conjunto de classificados de carros alegóricos

Question

Na minha aplicação, eu tenho

• Coleção De X:milhares de números de ponto flutuante com o valor do intervalo [0, 1], não classificados.
• Coleção Y:11 carros alegóricos que varia de [0, 1], ordenados.
• O tamanho de X é conhecido.Deixe que ele seja L.

O objetivo é quantize X e mapeá-lo para Y, de modo que temos um hash matriz de índices de Y para X.Eventualmente, Y, vai ser quantizada, em seguida, em 10 de coisas discretas apontou para ele.

Um exemplo para torná-lo um pouco mais clara,

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

Eu quero que o algoritmo de saída para 0 baseado em índices como estes:

• 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

Tentativas

Ingenuamente, eu tentei linear e binária de busca para o posicionamento de cada elemento de X em Y de modo que o elemento é encontrado entre um par adjacente de elementos de Y.

No entanto, o desempenho não é bom o suficiente para a minha aplicação.Esta quantização acontece em uma thread de tempo real, que reduzem a computação é indesejável.

Pergunta

Qual é a melhor maneira de este tipo de hash/quantização?X não é ordenada.

Obrigado!

Answer 1

Tomar X, multiplicado por dizer 10.000 euros, arredondado para o número inteiro mais próximo.Simples, C, z = (int) (x vezes 10000.0).

Há 10.000 possíveis valores de z.Para a maioria dos valores de z, pode-se determinar o índice de z.Para criar uma tabela com 10.000 entradas.Na tabela, armazenar um índice i se você pode provar que x deve ser mapeado para eu, sabendo z, e armazenar -1 se você não pode provar isso.

Como resultado, você obtém o valor correto, provavelmente, em 9,980 de 10.000 valores e, em seguida, você use qualquer algoritmo lento que você tem para o restante 1 em 500 valores.

PS.A mesma tabela de tamanho seria usado para números de precisão dupla.Seja qual for o tamanho da tabela, haverá apenas alguns valores de X que não podem ser mapeados corretamente usando esse método, talvez 10 ou 20.Se você tomar uma tabela do tamanho de 10.000, em seguida, de 99,8% ou mais de 99,9% são mapeados corretamente, e de 0,1% ou 0,2% necessitam de um algoritmo lento.Exatamente a mesma coisa acontece com o casal.Você pode usar 1000 entradas, então os 10 ou 20 falhando seria de 1% ou 2%.

E uma coisa legal é que esse método funcionará no entanto os valores de Y são distribuídos.Somente se o número de valores de Y é maior, então você pode querer aumentar o tamanho da tabela.