Bonjour,
Je dois trouver un élément dans une énorme liste triée. Pourriez-vous me conseiller sur le choix de l'algorithme à utiliser? Je souhaiterais qu'il soit le plus rapide possible...
Cordialement,
Rodrigue
Bonjour,
Je dois trouver un élément dans une énorme liste triée. Pourriez-vous me conseiller sur le choix de l'algorithme à utiliser? Je souhaiterais qu'il soit le plus rapide possible...
Cordialement,
Rodrigue
Le plus rapide que je connaisse est la recherche dichotomique puisque ta liste est triée![]()
bon courage![]()
Il y a encore moyen de faire mieux que la dichotomie O(n log n) en utilisant le principe des tables de hachage, mais il faut bien voir si les données triées autorisent un tel principe.
Il existe de nombreuses implémentations de tables de hachage.
La recherche dichotomique est de O(log n) puisque tu divises toujours par deux la longueur du tableau par (environ) deux à chaque traitement.Envoyé par Charlemagne
![]()
Sorry, j'ai écris trop vite, j'ai confondu avec la FFT ;-)
O(n log n) aurait éte encore plus lent qu'une recherche sur tous les éléments !!
Effectivement c'est O(log n)
Avec un peu de chance c'est O(1) avec une bonne table de hachage
Bonjour,
Je confirme aussi ce qui a été suggéré : Dichotomie + hashage.
Ce qui donnera la meilleure performance est de pouvoir détérminer via une fonction "ElementToHashTableIndex" qui pourra associer à un élement une valeur entiére (par exemle comprise entre 1 et 2**16) qui constituera un point d'entrée dans une table de hash qui donnera l'intervalle de la liste triée dans la quelle doit se faire la recherche.
Tout le problème consiste à créér cette fonction "ElementToHashTableIndex" qui devra être croissante et qui assure une bonne répartition des éléments afin de minimiser autant que possible la largeur des intervalles.
Bonjour,
je suis tout à fait d'accord avec la dichotomie qui est super efficace.
La table de hashage marche aussi bien que vite, mais il faut voir le type de donnée triée. Si c'est des entiers, c'est un peu lourd à décomposer.
Mais je pense que tu as là les deux meilleures méthodes
Merci à tous pour vos réponses! Je vais essayer de coder ça ... vous n'auriez pas un exemple de code en C++ (sur la dichotomie) ?
C'est bon, c'est codé et ça fonctionne! (Je n'ai pas fait la table de hashage, je ne comprends pas bien le principe)
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Partager