Warum sollte ich ein HashSet über ein Wörterbuch?

Ich versuche zu implementieren, die eine Liste von Cache-Pfade auf einer A* - Algorithmus. Derzeit ist die Cache-Pfade gespeichert sind, in einer Liste wie dieser:

readonly List<CachedPath> _cachedPaths = new List<CachedPath>();

Die Operationen, die über diese Liste sind:

FirstOrDefault zu bekommen, ein element, das erfüllt bestimmte Bedingungen

var cached = _cachedPaths.FirstOrDefault(p => p.From == from && p.To == target && p.Actor == self);

Entfernen und element

_cachedPaths.Remove(cached);

Ergänzungen

_cachedPaths.Add(new CachedPath {
                    From = from,
                    To = target,
                    Actor = self,
                    Result = pb,
                    Tick = _world.WorldTick
                });

HINWEIS: Die Klasse CachedPath hat GetHashCode und Equals überschrieben, indem Sie einfach die Aus, und die Schauspieler, also zwei Instanzen, die diese Attribute haben den gleichen hash und Gleichheit.

Gegeben, dass eine schnelle Suche (Enthält), Insertionen und Deletionen in eine 'HashSet' sind O(1) (wenn ich mich nicht Irre), als ich mit einem 'HashSet' für diese Operationen. Das problem ist nur das FirstOrDefault, musste ich aufzählen der ganzen Sammlung, um es zu bekommen.

Angesichts dieses Problems, als auch eine Wörterbuch-indiziert durch den hash Aus, und Schauspieler:

Dictionary<int, CachedPath> cachedPath

Wieder, wenn ich mich nicht Irre, Wörterbuch bietet auch O(1) bei Einfügungen, Löschungen, und auch der Abruf per Schlüssel. Dies führt mich zu glauben, dass ein Wörterbuch ist ein HashSet + O(1) element retrieval-Funktionen.

Bin ich etwas fehlt? Ist wirklich Wörterbuch besser als HashSet in dem Sinne, dass es unterstützt mehr Operationen?

Vielen Dank im Voraus.

stackoverflow.com/questions/2728500/...

InformationsquelleAutor David Jiménez Martínez | 2015-01-18

  1. 17

    Dictionary ist nicht besser als HashSet, es ist nur anders.

    • Sie eine HashSet wenn Sie speichern möchten, eine ungeordnete Sammlung von Elementen, und
    • Sie eine Dictionary wenn Sie möchten, ordnen Sie einen Satz von Elementen, genannt "Schlüssel", mit einer anderen Sammlung von Artikel, die als "Werte"

    Könnte man denken, ein HashSet als Dictionary ohne zugeordnete Werte (in der Tat HashSet ist manchmal umgesetzt mit einem Dictionary hinter der Szene), aber es ist nicht notwendig, darüber nachzudenken, es in dieser Weise: das denken der beiden als völlig unterschiedliche Dinge funktioniert ebenfalls sehr gut.

    In Ihrem Fall könnten Sie möglicherweise die Leistung verbessern, indem Sie ein Wörterbuch, um Schauspieler, wie diese:

    Dictionary<ActorType,List<CachedPath>> _cachedPathsByActor

    Diese Weise Ihre lineare Suche würde schnell wählen Sie eine sub-Liste basiert auf einer Schauspieler, und dann Suche Linear Zielgruppe:

    var cached = _cachedPathsByActor[self].FirstOrDefault(p => p.From == from && p.To == target);

    werden oder indem eine Gleichheit comparer Auffassung, dass alle drei Elemente, und mit einem Dictionary mit CachedPath wie beide Schlüssel und Werte, und das benutzerdefinierte , IEqualityComparer<T> als Schlüssel comparer:

    class CachedPathEqualityComparer : IEqualityComparer<CachedPath> {
    public bool Equals(CachedPath a, CachedPath b) {
        return a.Actor == b.Actor
            && a.From == b.From
            && a.To == b.To;
    }
    public int GetHashCode(CachedPath p) {
        return 31*31*p.Actor.GetHashCode()+31*p.From.GetHashCode()+p.To.GetHashCode();
    }
}
...
var _cachedPaths = new Dictionary<CachedPath,CachedPath>(new CachedPathEqualityComparer());
...
CachedPath cached;
if (_cachedPaths.TryGetValue(self, out cached)) {
    ...
}

    Jedoch, dieser Ansatz setzt Voraus, dass es höchstens ein Element in das Wörterbuch mit identischen From, To, und Actor.

    Und was ist mit Schauspieler.GetHashcode() + Aus.GetHashCode () +.GetHashCode() für diesen Fall als Schlüssel anstatt nur die Schauspieler? Wäre es nicht auch schneller?

    InformationsquelleAutor dasblinkenlight

  2. 9

    Einem hashset nicht eine exception werfen, wenn die Durchführung einer Beurteilung. Stattdessen gibt es eine bool spiegelt den Erfolg der add.

    Auch ein hashset nicht erforderlich, ein keyValue-pair-Mädchen.
    Ich benutze hashsets garantieren eine einzigartige Sammlung von Werten.

    InformationsquelleAutor Scott Nimrod

Schreibe einen Kommentar