Eu tenho uma matriz de flutuadores, classificados do menor para o maior, e preciso poder escolher o flutuador mais próximo maior ou menor que um valor de entrada passado. Este valor de entrada não está necessariamente presente como um valor na matriz.
Uma abordagem ingênua seria fazer uma pesquisa linear simples através da matriz. Isso pode ser assim:
void FindClosestFloatsInArray( float input, std::vector<float> array,
float *min_out, float *max_out )
{
assert( input >= array[0] && input < array[ array.size()-1 ] );
for( int i = 1; i < array.size(); i++ )
{
if ( array[i] >= input )
{
*min = array[i-1];
*max = array[i];
}
}
}Mas, obviamente, à medida que a matriz aumenta, isso se torna cada vez mais lento.
Alguém tem uma idéia sobre um algoritmo que me permita encontrar esses dados de maneira ideal? Eu já mudei para uma pesquisa binária, que melhorou um pouco as coisas, mas ainda é muito mais lenta do que gostaria, e como não estou procurando um valor específico que exista na matriz, ele nunca pode terminar cedo.
Mais informações: Os valores de ponto flutuante na matriz não são necessariamente distribuídos uniformemente (ou seja, a matriz pode consistir nos valores "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f 1203.f, 1400.f ".
Estou fazendo essa operação centenas de milhares de vezes, mas posso realizar qualquer quantidade de pré-processamento na matriz de flutuadores, se isso melhorar o tempo de pesquisa. Eu absolutamente posso mudar para usar algo diferente de um vetor para armazená-los, se isso ajudar.
fonte
Respostas:
O código da pergunta (uma pesquisa linear), como você aponta corretamente, ficará lento para grandes matrizes flutuantes. Tecnicamente, é O (n) onde n é o número de valores flutuantes em sua matriz.
Em geral, o melhor que você pode fazer para encontrar um valor em uma matriz ordenada é algum tipo de pesquisa em árvore recursiva (por exemplo, pesquisa binária); nesse caso, você pode obter um tempo de pesquisa O (log n) no número de elementos na sua matriz. O (log n) é muito melhor que O (n) para grandes valores de n.
Minha abordagem sugerida seria, portanto, uma simples busca binária da matriz , ou seja:
Este é um algoritmo O (log n) que deve ser rápido o suficiente para quase todas as situações. Intuitivamente, ele funciona pela metade do intervalo a ser pesquisado em cada etapa até encontrar o valor correto.
É realmente difícil definir a pesquisa binária simples; portanto, se você já a implementou corretamente, pode estar bem próximo do ideal. No entanto, se você conhece as distribuições dos dados e / ou possui um intervalo limitado de valores de pesquisa (x), ainda existem outros truques mais avançados que você pode tentar:
No entanto, a menos que você esteja em uma situação muito especial, provavelmente recomendo continuar com a pesquisa binária simples. Razões:
fonte
Isso parece bastante simples:
Faça uma pesquisa binária do flutuador que você deseja limitar - tempo O (log n).
Então o elemento à esquerda é o limite inferior e o elemento à direita é o limite superior.
fonte
A resposta óbvia é armazenar os carros alegóricos em uma árvore . O suporte às operações 'previous' e 'next' são triviais em uma árvore. Portanto, basta fazer um 'próximo' no seu valor e, em seguida, um 'anterior' no valor que você encontrar na primeira etapa.
fonte
Este artigo ("pesquisa sublogarítmica sem multiplicações") pode ser interessante; ele ainda contém algum código fonte. Para fins de comparação, você pode tratar um número flutuante como um número inteiro com o mesmo padrão de bits; esse era um dos objetivos de design do padrão de ponto flutuante IEEE.
fonte