Hashmap langsamer als compareTo?

[jabaduu]

Hi, ich muss grosse Dateien lesen, Zeile für Zeile.
Jede Zeile muss ich mit Strings vergleichen. Wenn ich Zeile für Zeile ein string1.compareTo(string2) ausführe, ist es sehr langsam.
Ich habe dann versucht das mit einer hashmap zu lösen, aber das ist noch langsamer.
ich bin jetzt etwas verloren. Was gibt es denn für schnellere Datenstrukturen?
Danke!

 

[jabaduu]

Ich habe einen 2 Core Prozessor, also könnte ich die zeit schon mal halbieren, indem ich die Aufgabe auf 2 Threads
aufteile oder?
Aber das wäre dann immer noch nicht schnell genug.

 

[mihe7]

ich muss grosse Dateien lesen, Zeile für Zeile.

Was heißt groß?

Jede Zeile muss ich mit Strings vergleichen. Wenn ich Zeile für Zeile ein string1.compareTo(string2) ausführe, ist es sehr langsam.

Mit wie vielen Strings musst Du sie vergleichen?

Was gibt es denn für schnellere Datenstrukturen?

Schneller als O(1) geht kaum.

Ich habe einen 2 Core Prozessor, also könnte ich die zeit schon mal halbieren, indem ich die Aufgabe auf 2 Threads
aufteile oder?

Halbieren? Schön wär's.

 

[jabaduu]

Ok, nicht halbieren , aber trotzdem beschleunigen, oder?

 

[jabaduu]

Und sind mehr als zwei threads in diesem Fall sinnvoll?

 

[mihe7]

Sinnvoll wäre, wenn Du etwas mehr zu den Daten schreiben würdest. Wie viele, was Du machen musst usw.

 

[jabaduu]

Jede Zeile besteht aus 1 bis 3 Strings,die jeweils mit ca 30 String verglichen werden müssen. Zeilen Anzahl ist nicht fest, kann von 100 bis 20K sein.

 

[jabaduu]

Was aber die Kenntnis der Anzahl hier bringen soll, erschliesst sich mir nicht. Eine schnelle Datenstruktur ist nun mal schneller als eine langsamere, egal wieviele Zeilen lol

 

[mihe7]

Was aber die Kenntnis der Anzahl hier bringen soll,

Naja, Du schreibst sehr wenig und sehr wage: "groß" liegt nunmal im Auge des Betrachters. 20.000 Zeilen sind ja jetzt nun nicht die Menge. Wie lange sind denn die Strings? Was heißt "dauert zu lange"? Wie lange dauert es denn?

Eine schnelle Datenstruktur ist nun mal schneller als eine langsamere, egal wieviele Zeilen

Ein langsamer Ansatz wird durch eine schnellere Datenstruktur auch nicht besser.

 

[jabaduu]

equals() scheint das scnellste zu sein. Aber warum ist das so?

 

[jabaduu]

Hä?? natürlich wird es schneller.

 

[httpdigest]

Ein Algorithmus ist nicht notwendigerweise für alle Eingabegrößen schneller als ein anderer Algorithmus. Erst einmal: Datenstrukturen sind immer an konkrete Algorithmen gekoppelt. Eine Datenstruktur bzw. ein Algorithmus hat gemäß seiner Laufzeit eigentlich immer einen konstanten Faktor und dann zusätzlich noch einen linearen, quadratischen etc. Faktor, die von der Eingabegröße/Problemgröße abhängen. Ein Algorithmus bzw. eine Datenstruktur kann mal eine exakte Laufzeit von f1(n) = 100*n haben und einmal f2(n) = 100 + 10*n, gemessen an der Anzahl der Schritte/Operationen. Der konstante Faktor ergibt sich meist durch Aufbereitung der Daten, damit anschließende Schritte des Algorithmus effizienter ausgeführt werden.
In diesem Fall wäre z.B. für 10 Elemente f1(10) = 10*10 schneller als f2(10) = 100 + 10*10, aber für 100 Elemente langsamer.
Zusätzlich sei eigentlich nur noch gesagt, dass man die Komplexität eines Algorithmus meist nur asymptotisch ermittelt bzw. ermitteln kann.

 

[jabaduu]

ich versuche hier das Problem kurz zu präsentieren, ich kann hier nicht 2000 Zeilen Code reinkopieren oder ? Ich dachte, ich habe genug Infos gegeben. ich verstehe nicht, wie ich es genauer erklären soll. Das Programm selbst soll ja nicht geändert werden, nur diese Vergleiche (und daran anschliessende Berechnungen) dauert im Moment 6 Minuten.

 

[httpdigest]

Naja, du hast eigentlich aktuell noch ziemlich überhaupt nichts zu dem eigentlichen Problem gesagt. Strings vergleichen. Wonach vergleichen? Nur nach exakter Gleichheit oder, da du anscheinend compareTo() verwendest, nach einer Ordnung (also größer/kleiner als)? Versuche doch mal gaaaaanz genau und explizit und präzise dein Problem zu formulieren und nicht einfach nur: Ich habe eine Datei mit Strings und muss sie mit anderen Strings vergleichen. Was soll letztlich das Ergebnis der ganzen Operation sein? Eine Ausgabe "Ja" oder "Nein"? Gibt es eventuell Möglichkeiten, für ein "early out" also nicht _alle_ Strings vergleichen zu müssen - sowohl in der Datei als auch in den 30 anderen Strings? Was soll bei jedem Vergleich passieren?

 

[jabaduu]

Ok. Ich versuche es später noch mal zu erklären, ich muss jetzt erst mal weg.

 

[mihe7]

nur diese Vergleiche (und daran anschliessende Berechnungen) dauert im Moment 6 Minuten.

Suchst Du nach Permutationen?!?

Ich habe das jetzt mal auf einer uralten Maschine mit rotierender Platte getestet: die JVM zu starten, eine Liste von 30 Wörter aus einer Datei in ein Set zu lesen und 466.544 Wörter aus einer Datei gegen die 30 Wörter abzugleichen, dauert

real    0m0.650s
user    0m0.764s
sys    0m0.176s

Also, wo liegt jetzt das Problem?

 

[jabaduu]

Nein, keine Permuationen. Moment ich schreibe es gleich. Ich muss den Code etwas minimieren und auf das Problem reduzieren.

 

[jabaduu]

Mh ich brauch Hilfe. sollte der Code direkt ausführbar sein, oder reicht die kritische Methode? Ich muss sonst mehrere Klassen und die Datei die eingelesen wird hier reinkopieren, das wird doch zuviel oder?

 

[mrBrown]

Für den Anfang würde vermutlich schon eine Erklärung des Problems völlig ohne Code reichen.


Wenn du aktuell zwischen HashMap, compare und equals schwankst, stell ich mir Code zur Erklärung eher hinderlich vor...

 

[jabaduu]

Problem nun gelöst. Ich habe noch mal intensiv benchmarking betrieben. HashMap, compare und equals
haben nur minimale Unterschiede gehabt. Das Problem lag an einer langsamen Methode, die ich nun
umgeschrieben habe, und nun ist das Programm blitzschnell. Check.

 

[Xyz1]

Ein Programm wird durch Benchmarks nicht schneller. 🙁

 

[mrBrown]

HashMap, compare und equals
haben nur minimale Unterschiede gehabt.

Auto, Rad und Motor haben bekanntlich auch nur minimale Unterschiede 😉

 

[Xyz1]

Auto, Rad und Motor haben bekanntlich auch nur minimale Unterschiede

Eine Hand ist auch fast wie ein Fuß. 🙂

Bearbeitung: Dein Beitrag trägt nicht viel zum Thema bei

 

[jabaduu]

ich wollte damit sagen, ich habe einfach noch mal das ganze Programm durchgmessen, Lauzeittechnisch,
jewels mit compareTo, equals, und hashmap, aber der Zeitunterschied betrug einfach nur wenige millisekunden.
Das Problem war ein Methodenaufruf, eine Methode die zu langsam war, die habe ich umgeschieben und nun ist das Projekt fertig. 😉