none
Optimisation & SortedDictionary RRS feed

  • Question

  • Hello,

    Je dois créer un dictionnaire de mots clefs à partir des mots stockés dans un champ d'une table, à laquelle j'accède via ODBC.
    Ce dictionnaire doit bien sûr être trié. Le nombre de lignes de la table n'excédera pas 20 à 30 000 lignes.
    Sachant que je le reconstruis intégralement à chaque recherche, il faut que le processus soit le + rapide possible.

    Juste par curiosité, voyez-vous une ou plusieurs pistes pour accélérer le code suivant ?

    J'ai bien sûr essayé avec SortedList, ArrayList puis Sort, etc... et les expressions régulières sur le Split() qui permet
    de découper une phrase en mots clets selon une liste de séparateurs.

    J'ai même fait un essai avec VStudio 2010 Beta 2 et un Parallel.For mais je perds dés le début 200 ms :-(

    Pré-requis : accès via ODBC et FileDSN, 3.5 SP1, C#

    D'avance merci de vos suggestions.

                Stopwatch timePerParse = Stopwatch.StartNew();
                string connectionString = @"FILEDSN=C:\Dev\myCompany\DataSources\BaseTest.dsn";
                string queryString = "SELECT Resume FROM UD";
    
                SortedDictionary<string, string> sortedDictionary = new SortedDictionary<string, string>();
                using (OdbcConnection connection = new OdbcConnection(connectionString))
                {
                    OdbcCommand command = new OdbcCommand(queryString, connection);
                    connection.Open();
                    OdbcDataReader reader = command.ExecuteReader();
    
                    char[] delimiterChars = { ' ', ',', '.', ':', '\t', '/' };
                    string[] words = null;
                    // on découpe la phrase en mots clefs
                    while (reader.Read())
                    {
                        words = (reader.GetString(0)).Split(delimiterChars);
                        foreach (string s in words)
                        {
                            if (!sortedDictionary.ContainsKey(s))
                                sortedDictionary.Add(s, s);
                        }
                    }
                    reader.Close();
                }
                timePerParse.Stop();
                Console.WriteLine(String.Format("Nombre d'éléments dans le dictionnaire : {0} - Temps écoulé via SortedDictionary : {1} ms", sortedDictionaryDico.Count.ToString(), timePerParse.ElapsedMilliseconds.ToString()));
                sortedDictionary.Clear();
    


    lundi 7 décembre 2009 14:54

Réponses

  • Bonjour,

    Normalement vous n'avez pas besoin d'utiliser un SortedDictionary.
    Utilisez dans votre cas une List<string>.
    Utilisez la méthode BinarySearch() qui permet de rechercher par dichotomie (donc en log(n)) dans la liste si un élément existe ou pas. Si l'élément est inexistant, BinarySearch() retourne le complément bits de la position de l'élément suivant. Il suffit donc d'insérer votre nouveau mot à cet emplacement.
    Lors de la création de la List<string>, spécifiez dans le constructeur une capacité intiale pouvant contenir en moyenne (approximativement) tous les mots que vous obtiendrez à la fin (faites à la fin un TrimExcess() si nécessaire...).

    Les optimisations supplémentaires possibles sont :
    - D'utiliser le driver natif su SGBD au lieu de passer par ODBC.
    - De faire le traitement côté serveur à l'aide d'une fonction (ou procédure stockée) programmée si votre SGBD le permet.

    Cordialement
    Gilles TOURREAU - MVP C# - Architecte .NET/Consultant/Formateur
    mercredi 16 décembre 2009 21:52
    Modérateur

Toutes les réponses

  • Bonjour,

    Normalement vous n'avez pas besoin d'utiliser un SortedDictionary.
    Utilisez dans votre cas une List<string>.
    Utilisez la méthode BinarySearch() qui permet de rechercher par dichotomie (donc en log(n)) dans la liste si un élément existe ou pas. Si l'élément est inexistant, BinarySearch() retourne le complément bits de la position de l'élément suivant. Il suffit donc d'insérer votre nouveau mot à cet emplacement.
    Lors de la création de la List<string>, spécifiez dans le constructeur une capacité intiale pouvant contenir en moyenne (approximativement) tous les mots que vous obtiendrez à la fin (faites à la fin un TrimExcess() si nécessaire...).

    Les optimisations supplémentaires possibles sont :
    - D'utiliser le driver natif su SGBD au lieu de passer par ODBC.
    - De faire le traitement côté serveur à l'aide d'une fonction (ou procédure stockée) programmée si votre SGBD le permet.

    Cordialement
    Gilles TOURREAU - MVP C# - Architecte .NET/Consultant/Formateur
    mercredi 16 décembre 2009 21:52
    Modérateur
  • Bonjour, et merci pour votre réponse.

    J'ai essayé votre méthode, mais elle ne l'emporte pas sur un SortedDictionary, en tout cas à l'issue de mes tests.
    D'ailleurs, le + rapide est un Dictionary<string,string> dont on triera les éléments avec une requête Linq.
    Le nombre d'éléments ramené dans le dictionnaire est d'environ 18 000.

    On a : Dictionary<string,string>  >  SortedDictionary<string,string>  >  List<string>.
    Pour info, ce dictionnaire trié alimentera une ComboBox pour faire office de liste de suggestions.

    Voici le code d'initialisation de la liste avec un Dictionary<string,string>

    Stopwatch timePerParse = Stopwatch.StartNew();
    allkeywords = Datas.GetDictionary();
    var query = from keyword in allkeywords
                      orderby keyword.Key ascending
                      select keyword.Key;
    CB1.Items.AddRange(query.ToArray<string>());
    timePerParse.Stop();
    
    
    // avec une partie du code de Datas.GetDictionary
    
    while (reader.Read())
    {
         words = (reader.GetString(0)).Split(delimiterChars);
         foreach (string s in words)
         {
              if (!dic.ContainsKey(s.Trim().ToLower()))
                   dic.Add(s.Trim().ToLower(), s);
         }
    }
    

    Voici le code avec une simple List<string> que j'ai testé :

    private const string connectionString = "FILEDSN=C:\Dev\myCompany\DataSources\BaseTest.dsn";
    static char[] delimiterChars = { ' ', '#', ';', '*', '+', '?', '-', ',', '.', ':', '\t', '/', '\\', '(', ')', '\r', '\n', '"' };
    
    public static List<string> GetDictionaryToList()
    {
        Stopwatch timePerParse = Stopwatch.StartNew();
        string queryString = "SELECT Resume FROM UD";
        List<string> dic = new List<string>(20000);
        using (OdbcConnection connection = new OdbcConnection(connectionString))
        {
            OdbcCommand command = new OdbcCommand(queryString, connection);
            connection.Open();
            OdbcDataReader reader = command.ExecuteReader();
            string[] words = null;
            while (reader.Read())
            {
                words = (reader.GetString(0)).Split(delimiterChars);
                foreach (string s in words)
                {
                    int index = dic.BinarySearch(s.Trim().ToLower());
                    if (index < 0) { dic.Insert(~index, s.Trim().ToLower()); }
                }
            }
            reader.Close();
        }
        dic.TrimExcess();
        timePerParse.Stop();
        Console.WriteLine(String.Format("Temps écoulé via GetDictionaryToList : {0} ms", timePerParse.ElapsedMilliseconds.ToString()));
        return dic;
    }
    
    // puis le chargement de la combo, sans passer par une requête Linq
    
    List<string> allkeywords2 = Datas.GetDictionaryToList();
    CB1.Items.AddRange(allkeywords2.OfType<string>().ToArray<string>());
    


    Cordialement

    Damien




    mercredi 23 décembre 2009 10:43
  • Tu peux aussi accélérer ta recherche en initialisant ton dictionnaire à l'ouverture de ton application, mais cela va consommer un peu plus de mémoire, tout dépend de tes besoins.

    Es-ce que tu as essayé de faire la même chose avec une simple list<>

                List<string> dic = new List<string>();
                while (reader.Read())
                {
                    words = (reader.GetString(0)).Split(delimiterChars);
                    foreach (string s in words)
                    {
                        if (!dic.Contains(s))
                            dic.Add( s);
                    }
                }

    Microsoft MVP C# :: mongeon.devrpm.ca
    mercredi 23 décembre 2009 12:59
    Modérateur

  • var query = from keyword in allkeywords

                      orderby keyword.Key ascending

                      select keyword.Key;

    CB1.Items.AddRange(query.ToArray<string>());






    Tu peux directement typé ta query :+

                string[] query = (from keyword in allkeywords
                                      orderby keyword.Key ascending
                            select keyword.Key).ToArray();

    Microsoft MVP C# :: mongeon.devrpm.ca
    mercredi 23 décembre 2009 13:04
    Modérateur
  • Oui,

    Les performances ne sont vraiment pas bonnes. C'est environ 10X plus long qu'avec un BinarySearch.

    Voilà et merci pour ta réponse.

    @+
    Damien
    mercredi 23 décembre 2009 14:55
  • Bonjour,

    Dans le resultat de la liste de suggestions, tu ne peux pas afficher 20000 lignes.
    Il serait donc plus interessant de ne charger en mémoire que ce dont tu as besoin.

    select top 100 distinct motcle from matable order by motce where mot cle like @debut

    serait tres performant

    l'utilisation de @debut provoque la mise en cache de la requete pour qu'elle s'execute encore plus vite la 2eme fois.

    Si tu as des questions...
    ptournay
    jeudi 14 janvier 2010 19:55