algorithme d'indexation de contacts

bonsoir,

j'ai une BD qui contient une liste de contacts que je veux charger en mémoire pour la trier et y faire des traitements d'insertion, recherche (avec partial matching string) et suppression tout en la maintenant triée par ordre alphabétique
lors de ma recherche j'ai trouvé un certains nombre d'algo tel que HacheTable, Trie, PATRICIA, Judy,Ternary search tree...
J'aimerais bien que vous m'aider à choisir le bon algorithme en terme de complexité, temps de réponse, charge mémoire et s'il y en a d'autre criètes de choix ils seront les bienvenus!

Il faudrait en savoir un peu plus pour définir une structure de données optimale.

Pour maintenir un structure triée, les structures de liste chainées sont très pratiques. Pour avoir un accès direct aux éléments, une hashtable est ce qu'il y a de mieux. On peut combiner les deux, soit en favorisant les accès directs(SortedSet/SortedMap, B+Tree, ...).

Pour les recherches partielles, la table de suffixes est très pratique.

Si le nombre de contacts est inférieur à quelques milliers, aucun problème de perfomance en perspective même avec les techniques les moins élaborées (tant qu'on n'enchaîne pas plusieurs centaines de modifications chaque seconde).

en fait je m'explique encore plus,
mon algo doit être à la fois très performant et permettre la recherche des noms de contact (qui doivent être à leur tour stockés dans une structure de données optimisée) ayant un prefixe commun .
exemple: lorsque je tape "j" il doit me renvoier les noms qui commence par "j" comme "jean", "jannette",...

Citation:

---

Envoyé par tasnim86

en fait je m'explique encore plus,
mon algo doit être à la fois très performant et permettre la recherche des noms de contact (qui doivent être à leur tour stockés dans une structure de données optimisée) ayant un prefixe commun .
exemple: lorsque je tape "j" il doit me renvoier les noms qui commence par "j" comme "jean", "jannette",...

---

Si c'est juste une liste indexée est suffisante :
- Une liste chainée contenant les contacts dans l'ordre alphabétique.
- Un index des préfixes pointant vers le premier contact possible dans la liste chainée.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Index1 Index2 Liste --------------------------- ... I ----> Ir -----> Irène Irina J ----> Ja -----> Jacques Jannette Jasmine Je -----> Jean Jennifer K ----> Ka -----> Kael Karim Ke -----> Kerwan Kevin ...

---

Citation:

---

Envoyé par pseudocode

- Un index des préfixes pointant vers le premier contact possible dans la liste chainée.

---

merci mais c'est quoi la structure de données de l'index?
et puis combien d'index dans ce cas?

Citation:

---

Envoyé par tasnim86

merci mais c'est quoi la structure de données de l'index?

---

Le plus naturel semble être un arbre des préfixes possibles, ou chaque noeud pointe vers le premier contact de la liste. Si en plus tu maintiens l'ordre lexicographique pour chaque niveau (frère précédant/suivant), ca permet d'optimiser le parcours final de la liste de contact

Code:

---

1 2 3 4 5 6 7 8

______________ | | | I J K | | | | _|_ _|_ | | | | | Ir Ja Je Ka Ke

---

Citation:

---

et puis combien d'index dans ce cas?

---

Tu peux faire autant de niveau de profondeur que tu veux pour chaque branche. Le mieux étant de créer un nouveau niveau s'il y a trop de contacts pour le préfixe.

une liste chainée pour les contacts et un arbre pour les index, ça ne consomme pas trop de mémoire? :roll:
y a pas une structure qui combine les deux ?

Citation:

---

Envoyé par tasnim86

une liste chainée pour les contacts et un arbre pour les index, ça ne consomme pas trop de mémoire? :roll:

---

La liste chainée, c'est uniquement pour optimiser les insertions/suppressions. Si ces opérations sont marginales, un tableau (ou plusieurs tableaux) est suffisant.

Un arbre de préfixes, ca ne coute pas très cher, meme si tu le fais sur 3 ou 4 niveaux.

Citation:

---

y a pas une structure qui combine les deux ?

---

Le B+Tree

Citation:

---

Envoyé par pseudocode

Un arbre de préfixes, ca ne coute pas très cher, meme si tu le fais sur 3 ou 4 niveaux.
]

---

et si c'est pour 1000 contacts?:?

Citation:

---

Envoyé par tasnim86

et si c'est pour 1000 contacts?:?

---

8O ??

Bah pour 1000 contacts une simple liste triée avec un index pour la 1ere lettre c'est largement suffisant. Ca fait en moyenne 40 contacts par lettre, une broutille.

Citation:

---

Envoyé par pseudocode

Bah pour 1000 contacts une simple liste triée avec un index pour la 1ere lettre c'est largement suffisant. Ca fait en moyenne 40 contacts par lettre, une broutille.

---

mais là, comme si tu considére que le prefixe ne peut être que la 1ère lettre du nom donc seulement le 1er caractère

Citation:

---

Envoyé par tasnim86

mais là, comme si tu considére que le prefixe ne peut être que la 1ère lettre du nom donc seulement le 1er caractère

---

L'index te donne juste le pointeur de début et le pointeur de fin de la zone de recherche (= tous les contacts qui commencent par la lettre indiquée).

A chaque fois que tu ajoutes une lettre, il faut avancer le le pointeur de début pour réduire la zone de recherche, en comparant le préfixe du contact avec le préfixe que tu as commencé à taper. C'est assez rapide car tu as peu de contacts à gérer.

Merci pour ton aide,
mais y a-t-il un tuto qui exlique encore plus la structure de données à utiliser selon ton approche?

Citation:

---

Envoyé par tasnim86

Merci pour ton aide,
mais y a-t-il un tuto qui exlique encore plus la structure de données à utiliser selon ton approche?

---

Pour cette structure particulière, non je ne crois pas. :D