Recherche d'un élément dans une liste triée (vitesse)

**Rodrigue** · 17/05/2006, 16h16

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

**Nadine** · 17/05/2006, 16h26

Le plus rapide que je connaisse est la recherche dichotomique puisque ta liste est triée

bon courage

**Hephaistos007** · 17/05/2006, 16h42

Je confirme.

**Charlemagne** · 17/05/2006, 16h54

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.

**Nadine** · 17/05/2006, 16h59

Envoyé par Charlemagne

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.

**Charlemagne** · 17/05/2006, 17h01

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

**Graffito** · 17/05/2006, 18h08

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.

**ToTo13** · 18/05/2006, 08h51

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

**Rodrigue** · 18/05/2006, 08h56

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) ?

**Rodrigue** · 18/05/2006, 09h23

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)

Recherche d'un élément dans une liste triée (vitesse)

Algorithmes et structures de données

Discussions similaires

Partager

Partager