Ich habe Bäume schon immer geliebt, so schön O(n*log(n)) und ihre Sauberkeit. Allerdings hat mich jeder Software-Ingenieur, den ich kenne, gefragt, warum ich eine TreeSet . Mit einem CS-Hintergrund glaube ich nicht, dass es so wichtig ist, was Sie verwenden, und ich habe keine Lust, mit Hash-Funktionen und Buckets herumzuspielen (im Fall von Java ).
In welchen Fällen sollte ich eine HashSet über eine TreeSet ?
Der Grund, warum die meisten HashSet ist, dass die Operationen (im Durchschnitt) O(1) statt O(log n) sind. Wenn die Menge Standardelemente enthält, müssen Sie sich nicht mit Hash-Funktionen herumschlagen, da dies bereits für Sie erledigt wurde. Wenn die Menge benutzerdefinierte Klassen enthält, müssen Sie Folgendes implementieren hashCode zu verwenden HashSet (obwohl Effective Java zeigt wie), aber wenn Sie eine TreeSet Sie müssen es schaffen Comparable oder liefern eine Comparator . Dies kann ein Problem darstellen, wenn die Klasse keine bestimmte Reihenfolge hat.
Ich habe manchmal verwendet TreeSet (oder eigentlich TreeMap ) für sehr kleine Mengen/Karten (< 10 Elemente), obwohl ich nicht überprüft habe, ob dies wirklich einen Vorteil bringt. Bei großen Mengen kann der Unterschied beträchtlich sein.
Wenn Sie nun das Sortierte brauchen, dann TreeSet ist angemessen, obwohl selbst dann, wenn Aktualisierungen häufig sind und der Bedarf an einem sortierten Ergebnis selten ist, kann es manchmal schneller sein, den Inhalt in eine Liste oder ein Array zu kopieren und sie zu sortieren.
Wenn Sie nicht so viele Elemente einfügen, dass es zu häufigen Rehashes kommt (oder zu Kollisionen, wenn Ihr HashSet die Größe nicht ändern kann), bietet Ihnen ein HashSet sicherlich den Vorteil eines konstanten Zeitzugriffs. Aber bei Mengen, die stark wachsen oder schrumpfen, können Sie je nach Implementierung mit Treesets tatsächlich eine bessere Leistung erzielen.
Die Amortisationszeit kann mit einem funktionalen Rot-Schwarz-Baum nahe bei O(1) liegen, wenn ich mich recht erinnere. In Okasakis Buch gibt es eine bessere Erklärung, als ich sie geben kann. (Oder siehe seine Publikationsliste )
HashSet-Implementierungen sind natürlich viel schneller - weniger Overhead, weil es keine Reihenfolge gibt. Eine gute Analyse der verschiedenen Set-Implementierungen in Java finden Sie unter http://java.sun.com/docs/books/tutorial/collections/implementations/set.html .
Die Diskussion dort zeigt auch einen interessanten "Mittelweg" in der Frage Baum vs. Hash auf. Java bietet ein LinkedHashSet, das ein HashSet mit einer "einfügeorientierten" verknüpften Liste ist, d.h. das letzte Element in der verknüpften Liste ist auch das zuletzt in das Hash eingefügte. Auf diese Weise können Sie die Unregelmäßigkeiten eines ungeordneten Hash vermeiden, ohne die höheren Kosten eines TreeSet in Kauf nehmen zu müssen.
El TreeSet ist eine von zwei sortierten Sammlungen (die andere ist TreeMap). Sie verwendet eine Rot-Schwarz-Baumstruktur (aber das wussten Sie ja) und garantiert dass die Elemente in aufsteigender Reihenfolge angeordnet sind, entsprechend der natürlichen Reihenfolge. Wahlweise, kann ein TreeSet mit einem Konstruktor konstruiert werden, mit dem man der Sammlung seine (anstatt sich auf die von der Klasse der Elemente definierte Reihenfolge zu verlassen) durch die Klasse der Elemente definiert ist), indem man einen Comparable oder Comparator
und A LinkedHashSet ist eine geordnete Version von HashSet, die eine doppelt verknüpfte Liste über alle Elemente hinweg unterhält. Verwenden Sie diese Klasse anstelle von HashSet wenn Sie sich um die Iterationsreihenfolge kümmern. Wenn Sie durch ein HashSet iterieren, ist die HashSet durchlaufen, ist die Reihenfolge unvorhersehbar, während Sie mit einem LinkedHashSet durch die Elemente in der Reihenfolge, in der sie eingefügt wurden
Warum Äpfel essen, wenn man auch Orangen essen kann?
Im Ernst, Jungs und Mädels - wenn Ihre Sammlung groß ist, millionenfach gelesen und beschrieben wird und Sie für CPU-Zyklen bezahlen, dann ist die Wahl der Sammlung NUR dann relevant, wenn Sie sie für eine bessere Leistung benötigen. In den meisten Fällen spielt dies jedoch keine Rolle - ein paar Millisekunden hier und da werden von Menschen nicht bemerkt. Wenn es wirklich so wichtig wäre, warum schreiben Sie dann keinen Code in Assembler oder C? (Stichwort: weitere Diskussion). Der Punkt ist also, wenn Sie mit der von Ihnen gewählten Sammlung zufrieden sind und sie Ihr Problem löst [auch wenn es nicht gerade die beste Art von Sammlung für die Aufgabe ist], können Sie sich glücklich schätzen. Die Software ist anpassungsfähig. Optimieren Sie Ihren Code wo nötig. Onkel Bob sagt, dass verfrühte Optimierung die Wurzel allen Übels ist. Onkel Bob sagt es
CodeJaeger ist eine Gemeinschaft für Programmierer, die täglich Hilfe erhalten..
Wir haben viele Inhalte, und Sie können auch Ihre eigenen Fragen stellen oder die Fragen anderer Leute lösen.
