Soll ich TreeSet oder HashSet verwenden?

Ich habe eine große Anzahl von Zeichenfolgen, ich muss eindeutige Zeichenfolgen in sortierter Reihenfolge drucken. TreeSet speichert sie in sortierter Reihenfolge, aber die Einfügezeit ist O (Logn) für jede Einfügung. HashSet braucht O (1) Zeit, um hinzuzufügen, aber dann muss ich eine Liste der Menge und dann sortieren mit Collections.sort(), die O (nLogn) nimmt (ich nehme an, es gibt keinen Speicheraufwand hier seit nur die Referenzen von Strings wird in die neue Sammlung kopiert, dh Liste). Ist es fair zu sagen, dass alle Entscheidungen gleich sind, da am Ende die Gesamtzeit gleich bleibt?Soll ich TreeSet oder HashSet verwenden?

Quelle

2016-04-20 noobCoder

Wichtige Frage: Welcher Teil der Strings sind Duplikate? – Bohemian

@Nevado Ich könnte genau das gleiche fragen: Warum die * upvote *? Laut dem Tooltip auf dem Downvote, geht downvote für die Frage entweder unklar, nutzlos für andere Menschen, schlecht angegeben (unzureichende Informationen etc.) oder für den Mangel an OP Forschungsanstrengungen. Als Nebenbemerkung: OP hat eine Frage zur Optimierung gestellt, aber a) das Profiling und Testen nicht selbst gemacht, b) genügend Kontext bereitgestellt. In 99% der Situationen, die Neulinge stellen, ist der Unterschied zwischen "TreeSet" und "HashSet" vernachlässigbar. Auch die Antwort auf die Frage ist in fast jedem Buch über Algorithmen enthalten. – vaxquis

Mögliches Duplikat von [Hashset gegen Treeset] (http://stackoverflow.com/questions/1463284/hashset-vs-treeset) – vaxquis

Messen ist der Weg zu gehen, aber wenn man rein theoretisch zu reden und von nach dem Sortieren lesen ignorierend, dann für die Anzahl der x-Strings = betrachten:

HashSet: x * O(1) Operationen + 1 O(n log n) hinzufügen (wobei n x) = etwa Sortieroperation O(n + n log n) (ok, das ist eine grobe Vereinfachung, aber ..)

TreeSet: x * O(log n) (wobei n erhöht sich von 1 bis x) + O(0) so RT Operation = ungefähr O(n log (n/2)) (auch eine grobe Übervereinfachung, aber ..)

Und weiter in der Vereinfachung Vene, O(n + n log n) > O(n log (n/2)). Vielleicht TreeSet ist der Weg zu gehen?

Quelle

2016-04-20 22:45:12

Die Einfügung in die Baummenge ist 'x * O (log n)', nicht 'x * O (n log n)'. Es läuft auf Implementierungsdetails hinaus, wie schnell die Hash-Funktion des Hash-Sets ist und wie schnell der Sortieralgorithmus von 'Collection.sort()' ist (was auch von der Verteilung der Daten abhängt). – Philipp

Ah, das hat das OP nicht gesagt. Das verdreht meine Induktionen :) –

eigentlich genau das, was der OP sagte ... – Philipp

Das hängt davon ab, wie nahe Sie aussehen. Ja, die asymptotische Zeitkomplexität ist in beiden Fällen O (n log n), aber die konstanten Faktoren unterscheiden sich. Es ist also nicht so, dass eine Methode 100-mal schneller als die andere sein kann, aber es ist sicherlich möglich, dass eine Methode doppelt so schnell ist wie die andere. Für die meisten Teile eines Programms ist ein Faktor 2 völlig irrelevant, aber wenn Ihr Programm tatsächlich einen beträchtlichen Teil seiner Laufzeit in diesem Algorithmus verbringt, wäre es eine gute Idee, beide Ansätze zu implementieren und ihre zu messen Performance.

Quelle

2016-04-20 22:54:24 meriton

-1

Sie sollten berücksichtigen, welche Methoden häufiger ausgeführt werden und Ihre Entscheidung darauf basieren.

Neben HashSet und TreeSet können Sie LinkedHashSet verwenden, die eine bessere Leistung für sortierte Sätze bietet. Wenn Sie mehr über die Unterschiede in der Leistung lernen wollen schlage ich Ihre 6 Differences between TreeSet HashSet and LinkedHashSet in Java

Quelle

2016-04-20 23:06:25 Nevado

LinkedHashSet bietet keine bessere Leistung für sortierte Sätze. Es behält nur den Anzeigenauftrag bei (zu einem Speicheraufwand). –

Ja es tut, in Bezug auf die Zeit zu seinen Elementen als das 'TreeSet'. Natürlich ist seine Leistung nicht besser als das 'HashSet', aber Sie können keine Reihenfolge in diesem letzten sichern – Nevado

lesen Wenn Sie die Gesamtanzahl der Strings (n) und Anzahl der einzelnen Strings (m) zu unterscheiden, Sie detailliertere Ergebnisse für beide Ansätze erhalten:

Hash-Set + Sortieren: O (n) + O (m log m)

TreeSet: O (n m log)

wenn also n ist viel größer als m ist, eine Hash-Set unter Verwendung von und Sortieren Das Ergebnis sollte etwas besser sein.

Quelle

2016-04-21 00:15:33

Antwort

Verwandte Themen