Point de compromis entre Dictionary(hashtable) et List find

Question

Question courte : Combien d'éléments peuvent être dans une liste pour rendre une recherche linéaire comme List O(n) plus rapide que Dictionary qui est O(1) ?

Il me semble me rappeler à l'université (et au lycée) que lors de la comparaison des techniques de recherche (binaire vs linéaire) il y avait toujours un point où le linéaire était plus rapide. C'était O(n) vs O(log)

Je ne peux pas dessiner le graphique ici. Mais il doit y avoir des frais généraux pour la performance constante. Donc la question est si j'ai 10 éléments, est-ce que List.Find a plus de sens que

if (Dictionary.Contains(x))
    value = Directiory[x]

Ou une Hashtable où value = Hashtable[x] ne échouera pas mais nécessitera un boxing

Answer 1

Je me suis posé la même question, et j'ai effectué un test de performance pour le découvrir. J'ai constaté que la vitesse d'un dictionnaire surpasse déjà celle d'une liste lors de la recherche à environ 3-4 éléments.

Cela me semblait bien trop peu en fonction des coûts supplémentaires d'un dictionnaire, donc j'ai vérifié pour voir si quelqu'un d'autre était arrivé aux mêmes résultats, et il semble que d'autres aient également trouvé les mêmes résultats. http://dotnetperls.com/dictionary-time

Cela ne signifie pas qu'il faut ajouter des dizaines de dictionnaires dans votre code là où ce n'est pas pertinent - il y a aussi un surcoût en mémoire et en temps de construction à prendre en compte. Mais si vous avez un ensemble de données indexées de taille raisonnable, profitez de cette structure.

Answer 2

Testez les deux méthodes avec vos données et prenez une décision.

Avec seulement 10 éléments dans votre collection, il est probable que le coût constant du hachage l'emportera sur le coût de l'examen de chaque élément de votre liste (dans le pire des cas). Cependant, nous ne pouvons pas le confirmer avec certitude. Testez-le et découvrez-le.

Gardez à l'esprit que l'insertion dans un dictionnaire est également plus coûteuse que l'insertion dans une liste. En fonction de l'endroit et de la manière dont vous utilisez votre collection, un coût d'insertion supplémentaire peut être indésirable.

Answer 3

Après avoir effectué quelques tests de mon côté, il semble que Hash-Dictionary gagne toujours. Il s'agit d'un objet Dictionary avec un HashCode, int32, comme clé

10 éléments    500 000 itérations             
Nom du test                                           Première   Dernière   Non trouvé   Moyenne 
TrouverDansListe                                      104,26   255,29  254,63      204,73
TrouverDansTableau                                   51,28   192,23  182,91      142,14
TrouverDansHashDict                                  56,3    54,38   51,16       53,95
TrouverDansDict                                      105,75  101,38  52,02       86,38

100 éléments   500 000 itérations             
Nom du test                                           Première   Dernière   Non trouvé   Moyenne 
TrouverDansListe                                      102,83  1873,45 1820,85     1265,71
TrouverDansTableau                                   56,21   1313,61 1310,65     893,49
TrouverDansHashDict                                  91,01   53,31   60,46       68,26
TrouverDansDict                                      119,01  101,65  100,11      106,92

Voici mon code qui effectue l'opération de recherche. Mes objets sont des tâches hiérarchiques qui seraient recherchées par un nom unique. Je sais que c'est un long post mais au cas où quelqu'un voudrait contester les conclusions, il peut voir le code.

    private SearchResult TrouverDansDict()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "TrouverDansDict";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        if (dictStrBoundryTask.ContainsKey(NomDePremier))
        {
            TaskBase t = dictStrBoundryTask[NomDePremier];
        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictStrBoundryTask.ContainsKey(NomDeDernier))
        {
            TaskBase t = dictStrBoundryTask[NomDeDernier];
        }

        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictStrBoundryTask.ContainsKey(NomDeNonTrouvé))
        {
            TaskBase t = dictStrBoundryTask[NomDeNonTrouvé];
        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;

    }

    private SearchResult TrouverDansHashDict()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "TrouverDansHashDict";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        if (dictIntBoundryTask.ContainsKey(NomDePremier.GetHashCode()))
        {
            TaskBase t = dictIntBoundryTask[NomDePremier.GetHashCode()];
        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictIntBoundryTask.ContainsKey(NomDeDernier.GetHashCode()))
        {
            TaskBase t = dictIntBoundryTask[NomDeDernier.GetHashCode()];
        }

        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        if (dictIntBoundryTask.ContainsKey(NomDeNonTrouvé.GetHashCode()))
        {
            TaskBase t = dictIntBoundryTask[NomDeNonTrouvé.GetHashCode()];
        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;
    }

    private SearchResult TrouverDansTableau()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "TrouverDansTableau";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        foreach (TaskBase t in arrayBoundaryTask)
        {
            if (t.Name == NomDePremier)
            {
                break;
            }
        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        foreach (TaskBase t in arrayBoundaryTask)
        {
            if (t.Name == NomDeDernier)
            {
                break;
            }
        }
        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        foreach (TaskBase t in arrayBoundaryTask)
        {
            if (t.Name == NomDeNonTrouvé)
            {
                break;
            }
        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;
    }

    private SearchResult TrouverDansListe()
    {
        SearchResult result = new SearchResult();
        result.SeachType = "TrouverDansListe";
        result.itterations = 1;

        Stopwatch timer = new Stopwatch();

        timer.Start();
        TaskBase t = listBoundaryTask.Find(x => x.Name == NomDePremier);

        if (t!=null)
        {

        }

        timer.Stop();

        result.firstItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        t = listBoundaryTask.Find(x => x.Name == NomDeDernier);

        if (t != null)
        {

        }
        timer.Stop();

        result.lastItem = timer.Elapsed.TotalMilliseconds;

        timer.Reset();

        timer.Start();
        t = listBoundaryTask.Find(x => x.Name == NomDeNonTrouvé);

        if (t != null)
        {

        }

        timer.Stop();

        result.notFoundItem = timer.Elapsed.TotalMilliseconds;

        return result;
    }

Answer 4

Je ne pense pas qu'il existe une règle dure et rapide que vous pourriez appliquer pour obtenir une mesure infaillible. Vous pourriez toujours imaginer un cas dégénéré de Hashtable où vous finissez par avoir des recherches O(n) en raison de collisions, cependant, avec des données réalistes, les chances que cela se produise sont minuscules.

En général, si la recherche rapide est importante pour votre application, alors une structure de type Hashtable est toujours le meilleur choix.

(Les Hashtables ont leurs propres inconvénients - ce ne sont pas une solution magique. Wikipedia propose une bonne explication des cas où vous pourriez ne pas vouloir choisir un Hashtable : lien.)

Answer 5

La recherche dans le dictionnaire est toujours plus rapide que la recherche linéaire.