Optimiser la recherche dans un dico de 25k/mots

**Ldoppea** · 03/08/2011, 17h10

Bonjour,

Je suis sur le projet avec Maf77. Merci pour vos réponses.

tomlev, la version améliorée, ne fonctionne pas sur WP7 qui ne gere pas les SortedDictionary

Du coup j'utilise la version normale, que j'arrive à faire fonctionner en partie.

En effet, si j'arrive à créer un TrieNode et à l'utiliser, les éléments instanciés n'ont pas de value. Par exemple :

Code C# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
Trie<string> TrieWords = new Trie<string>();
 
//debut boucle de remplissage
TrieWords.Add(txt, txt); //txt étant un mot d'une des 25000 lignes dico
//fin de la boucle

En deboggage quand je regarde l’état de TrieWords, j'ai bien :
-Values //rempli de tous les mots
-Keys //rempli de toutes les cles.
-_rootNode //existe et est rempli de tous les children comme il faut

Jusque là tout parait normal mais que ce soit pour _rootNode ou encore ses _children, la _partialKey contient la bonne clé, mais _value est null et _hasValue est à false.

Du coup impossible de requêter un mot avec Values. Le findNode() fonctionne, mais je dois récupérer la PartialKey plutôt que la Value (c'est une solution temporaire car pas vraiment propre) :

Code C# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
TrieNode node =FindNode(word, false);
 
List<string> list = new List<string>();
if (node != null)
{
    //list.AddRange(node.Children.Select(child => child.Value.ToString())); //Ne fonctionne pas.
    list.AddRange(node.Children.Select(child => child.PartialKey.ToString()));
}

Une idée d'où peut venir le problème?

PS : Impossible d'atteindre un point d’arrêt dans la fonction FindPrefix(), que ce soit directement pendant l’exécution ou avec un F11 quand j’atteins le point d’arrêt de l'appel de la fonction.

PPS : J'en profite pour dire que avec le PartialKey, les performance sont excellente et je ne percoit plus aucun lag. On est sur la bonne voit

**tomlev** · 03/08/2011, 17h27

Euh... j'ai pas bien compris le scénario qui marche pas. Tu peux montrer un extrait de code qui reproduit le problème, avec ce que tu attends et ce que tu obtiens ?

C'est normal que certains noeuds n'aient pas de valeur. Les noeuds intermédiaires sont forcément présents, mais ne correspondent pas forcément à un élément effectivement présent dans la collection. Par exemple si tu as dans le Trie les mots "a" et "abcd", tu auras un noeud racine (qui correspond à la chaine vide) sans valeur, puis un noeud "a" avec la valeur "a", puis un noeud "b" et un noeud "c" sans valeur ("ab" et "abc" ne sont pas dans le trie), puis un noeud "d" avec la valeur "abcd". Par contre normalement tu ne devrais jamais voir ces noeuds en dehors du code du Trie...

De toutes façons, dans ton cas les valeurs n'ont pas d'importance, vu que tu n'as pas besoin d'associer une valeur aux mots. Tu peux utiliser Byte comme type de valeur, ce sera plus économique en mémoire.

Envoyé par Ldoppea

[I]PS : Impossible d'atteindre un point d’arrêt dans la fonction FindPrefix(), que ce soit directement pendant l’exécution ou avec un F11 quand j’atteins le point d’arrêt de l'appel de la fonction.

Bizarre... tu compiles bien en debug ?

**Ldoppea** · 03/08/2011, 18h05

Ahh j'avais mal compris l’utilité du _value alors. Autant pour moi.

Envoyé par tomlev

Par contre normalement tu ne devrais jamais voir ces noeuds en dehors du code du Trie...

C'est bien le cas. Ma fonction se trouve dans le corps de la classe Trie pour que je puisse utiliser FindNode()

Envoyé par tomlev

De toutes façons, dans ton cas les valeurs n'ont pas d'importance, vu que tu n'as pas besoin d'associer une valeur aux mots. Tu peux utiliser Byte comme type de valeur, ce sera plus économique en mémoire.

Done

Du coup je cherche sur ma recherche par PartialKey. Mon but étant qu'a partir d'un prefix je trouve le bon noeud puis je récupère toutes les lettres qui peuvent suivre (juste la première qui suit, pas besoin des suivantes). Ça marche bien. Je pensais qu'il valais mieux passer par les values, mais si j'ai bien compris ce n'est pas leur fonction première.

Merci.

Envoyé par tomlev

Bizarre... tu compiles bien en debug ?

Oui, mes autres point d’arrêts fonctionnent. D'ailleurs j'en ai un au niveau de l'appel de la fonction qui arrêté bien l’exécution. Et celui qui se trouve sur la première ligne de code dans la fonction n'est jamais arrêté. Peut-être un bug. Je devrais essayer de redémarrer tout pour vérifier.

PS : Le tag [resolu] arrive des que mon maf77 pourra se connecter.

**tomlev** · 03/08/2011, 18h10

Je comprends pas trop pourquoi tu as besoin de modifier la classe... La méthode FindPrefix fait déjà ce que tu veux il me semble :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
string prefix = ...
 
// Tous les mots qui commencent par prefix
foreach(var kvp in trie.FindPrefix(prefix))
{
    string word = kvp.Key;
    ...
}

**SaumonAgile** · 03/08/2011, 20h16

Envoyé par tomlev

Sinon, SaumonAgile a mentionné l'utilisation d'un trie, c'est effectivement une bonne idée pour ce genre d'utilisation. Le temps d'accès à un noeud ne dépend que de la longueur du préfixe recherché, pas du nombre d'éléments dans le trie. Donc que tu aies un élément ou un million, ça ne change rien.

A moi les royalties

As tu essayé avec un HashSet à la place des List<> ? Cela devrait simplifier l'implémentation non ?

**tomlev** · 03/08/2011, 22h08

Envoyé par SaumonAgile

As tu essayé avec un HashSet à la place des List<> ? Cela devrait simplifier l'implémentation non ?

Euh, je vois pas trop comment tu comptes faire avec un HashSet ?...

**Ldoppea** · 04/08/2011, 12h53

Envoyé par tomlev

Je comprends pas trop pourquoi tu as besoin de modifier la classe... La méthode FindPrefix fait déjà ce que tu veux il me semble :

Bah je ne comprend pas. Elle ne me retourne que des objets vides. Par exemple je cherche le prefixe "sno", il devrait me trouver "snob", "snobs", "snoek", "snooker", "snoop" etc, qui sont dans le dictionnaire.

Pourtant j'ai le résultat suivant :
Nom : BreakPoint.png
Affichages : 73
Taille : 25,2 Ko

Nom : BreakPoint.png
Affichages : 73
Taille : 25,2 Ko

Et même après redémarrage, impossible d'atteindre le breakpoint "var node = FindNode(prefix, false);". Du coup je ne peux pas déboguer pour voir d'où vient le problème. Incompréhensible...

**tomlev** · 04/08/2011, 13h44

T'es sûr que t'as pas modifié des trucs dans le trie par rapport au code d'origine ? Je viens de retester le FindPrefix, ça marche sans problème...

**tomlev** · 04/08/2011, 13h47

Ah au fait, par rapport à ton screenshot, c'est normal que tu vois pas le résultat comme une liste dans le debugger. C'est un itérateur, donc ça s'exécute au fur et à mesure que tu énumères les données. Essaie ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

var test = t.TrieWords.FindPrefix("sno").ToList();

ToList va forcer l'énumération complète des résultats et les mettre dans une liste.

**Ldoppea** · 04/08/2011, 14h31

En fait tout vient du ToList();

Avec lui, maintenant le débogueur passe bien sur le point d’arrêt, et la liste est bien initialisée.

Tout rentre dans l'ordre et je viens d'apprendre quelque chose sur les itérateur

Merci pour toute ton aide!

**tomlev** · 04/08/2011, 15h16

Ouais, les itérateurs c'est un peu bizarre comme truc... ça se présente comme une bête méthode, mais derrière ça fait plein de trucs compliqués. En fait le compilateur transforme complètement le code, ce qui peut donner des effets bizarres lors du debug.

En fait, quand tu appelles FindPrefix, ça n'exécute pas tout de suite le code de la méthode : ça renvoie un objet IEnumerable qui a été généré par le compilateur. C'est seulement quand tu commences à énumérer cet objet que le code de FindPrefix est effectivement exécuté.

**Immobilis** · 04/08/2011, 15h40

Envoyé par Ldoppea

Merci pour toute ton aide!

Résolu? Tu peux nous faire part des nouvelles performances?

**Maf77** · 04/08/2011, 15h58

On est passé de 2.5seconde avec la liste et la recherche linéaire à 7ms :-)
Merci bcp!!!

**Immobilis** · 04/08/2011, 16h49

Pas mal du tout! Champion tomlev

Tu as pas fait un tuto à ce sujet?

**tomlev** · 04/08/2011, 16h59

Envoyé par Immobilis

Pas mal du tout! Champion tomlev

Tu as pas fait un tuto à ce sujet?

Euh, non... mais bon, j'ai rien inventé, j'ai juste implémenté une structure de donnée inventée il y a 50 ans

**Immobilis** · 04/08/2011, 17h52

Envoyé par tomlev

Euh, non... mais bon, j'ai rien inventé, j'ai juste implémenté une structure de donnée inventée il y a 50 ans

C'est un plagiat???

**Immobilis** · 04/08/2011, 18h04

Petit doute:
J'ai récupéré ton code et fait ce petit programme pour tester:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
private static void Main(string[] args)
{
    var w = new Stopwatch();
    var trie = new Trie<string>();
    var list = new List<string>();
    var words = new string[25000];
    const int loops = 1000;
 
    long sum1 = 0;
    long sum2 = 0;
 
    for (int i = 0; i < words.Length; i++)
    {
        words[i] = Immobilis.ToolsBox.Security.Encryption.GenerateRandomString(20);
        try
        {
            trie.Add(words[i], words[i]);
            list.Add(words[i]);
        }
        catch
        {
            i--;
        }
    }
 
    for (int i = 0; i < loops; i++)
    {
        string pref = words[rd.Next(0, words.Count() - 1)].Substring(0, 2);
        Console.WriteLine("{0} {1}", i, pref);
        //
        w.Restart();
        var test = trie.FindPrefix(pref);
        w.Stop();
        if (i > 0)
        {
            sum1 += w.ElapsedTicks;
        }
        //Console.WriteLine("\tCount: {0}, time: {1}", test.Count(), w.ElapsedTicks);
 
        w.Restart();
        var test2 = list.Where(x => x.StartsWith(pref)) as IEnumerable<string>;
        w.Stop();
        if (i > 0)
        {
            sum2 += w.ElapsedTicks;
        }
        //Console.WriteLine("\tCount: {0}, time: {1}", test2.Count(), w.ElapsedTicks);
    }
 
    Console.WriteLine("Trie: {0} - List: {1}", sum1 / loops, sum2 / loops);
    Console.ReadLine();
}

Sur une instance de Trie et de List de 25000 éléments, sur 1000 itérations, je trouve quasiment les mêmes moyennes.

Pourquoi?

A+

EDIT Quand le nombre de résultats est faible la différence n'est pas super significative. Par contre, plus le nombre de résultats augmente plus Trie est rapide.

**tomlev** · 04/08/2011, 18h31

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
        w.Restart();
        var test = trie.FindPrefix(pref);
        w.Stop();
 
...
 
        w.Restart();
        var test2 = list.Where(x => x.StartsWith(pref)) as IEnumerable<string>;
        w.Stop();

Ouais mais là il est foireux ton test... FindPrefix, tout comme Where, n'exécutent aucun vrai traitement, ils sont "lazy". C'est seulement quand tu énumères le résultat que c'est exécuté. Tu peux ajouter un .Count() pour le forcer à tout énumérer.

**Immobilis** · 04/08/2011, 18h38

Envoyé par tomlev

Ouais mais là il est foireux ton test...

Sympa

En mettant un count, sur un tableau de:

1000 éléments et 1000 itérations, trie met en moyenne 24 ElapsedTicks et list 29;
25000 éléments et 1000 itérations, trie met en moyenne 61 ElapsedTicks et list 194;
En testant avec un Dictionary<string, string>() en plus, trie met en moyenne 108 ElapsedTicks, list 305 et le dictionnaire 182;

Optimiser la recherche dans un dico de 25k/mots

Windows Phone .NET

Discussions similaires

Partager

Partager