J'ai un tableau de flotteurs, triés du plus petit au plus grand, et je dois pouvoir choisir le flotteur le plus proche supérieur ou inférieur à une valeur d'entrée transmise. Cette valeur d'entrée n'est pas nécessairement présente en tant que valeur dans le tableau.
Une approche naïve serait de faire une simple recherche linéaire dans le tableau. Cela pourrait ressembler à ceci:
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];
}
}
}Mais évidemment, à mesure que le tableau s'agrandit, cela deviendra de plus en plus lent.
Quelqu'un at-il une idée d'un algorithme qui me permettrait de trouver ces données de manière plus optimale? Je suis déjà passé à une recherche binaire, ce qui a quelque peu amélioré les choses, mais c'est toujours beaucoup plus lent que je ne le souhaiterais, et comme je ne recherche pas réellement une valeur spécifique qui existe dans le tableau, elle ne peut jamais se terminer de bonne heure.
Plus d'informations: Les valeurs à virgule flottante dans le tableau ne sont pas nécessairement réparties uniformément (c'est-à-dire que le tableau peut être composé des valeurs "1.f, 2.f, 3.f, 4.f, 100.f, 1200.f , 1203.f, 1400.f ".
Je fais cette opération des centaines de milliers de fois, mais je peux faire n'importe quelle quantité de prétraitement sur le tableau de flottants, si cela améliore le temps de recherche. Je peux absolument changer pour utiliser autre chose qu'un vecteur pour les stocker, si cela peut aider.
la source
Réponses:
Le code dans la question (une recherche linéaire), comme vous le faites remarquer à juste titre, va ralentir pour les grands tableaux flottants. Techniquement, c'est O (n) où n est le nombre de valeurs flottantes dans votre tableau.
En général, le mieux que vous puissiez faire pour trouver une valeur dans un tableau ordonné est une recherche récursive dans un arbre (par exemple, une recherche binaire), auquel cas vous pouvez obtenir un temps de recherche O (log n) dans le nombre d'éléments dans votre tableau. O (log n) est bien meilleur que O (n) pour les grandes valeurs de n.
Mon approche suggérée serait donc une simple recherche binaire du tableau , c'est-à-dire:
Il s'agit d'un algorithme O (log n) qui devrait être assez rapide pour presque toutes les situations. Intuitivement, cela fonctionne en divisant par deux la plage à rechercher à chaque étape jusqu'à ce que vous trouviez la valeur correcte.
Il est vraiment difficile de lancer la recherche binaire simple, donc si vous l'avez déjà correctement implémentée, vous êtes peut-être déjà presque optimal. Cependant, si vous connaissez les distributions des données et / ou avez une plage limitée de valeurs de recherche (x), il existe encore d'autres astuces plus avancées que vous pouvez essayer:
Cependant, à moins que vous ne soyez dans une situation très spéciale, je recommanderais probablement de vous en tenir à la simple recherche binaire. Les raisons:
la source
Cela semble assez simple:
Effectuez une recherche binaire pour le flottant que vous souhaitez lier - heure O (log n).
Ensuite, l'élément à gauche de celui-ci est la limite inférieure, et l'élément à droite de celui-ci est la limite supérieure.
la source
La réponse évidente est de stocker les flotteurs dans un arbre . La prise en charge des opérations «précédente» et «suivante» est triviale dans un arbre. Il suffit donc de faire un «suivant» sur votre valeur, puis de faire un «précédent» sur la valeur que vous avez trouvée à la première étape.
la source
Cet article ("recherche sublogarithmique sans multiplications") pourrait être intéressant; il contient même du code source. Aux fins de comparaison, vous pouvez traiter un nombre flottant comme un entier avec le même motif binaire; c'était l'un des objectifs de conception de la norme à virgule flottante IEEE.
la source