Hashmap langsamer als compareTo?

jabaduu

Bekanntes Mitglied
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

Bekanntes Mitglied
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

Top Contributor
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

Bekanntes Mitglied
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

Top Contributor
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.
 

httpdigest

Top Contributor
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

Bekanntes Mitglied
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

Top Contributor
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?
 

mihe7

Top Contributor
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

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

Also, wo liegt jetzt das Problem?
 

jabaduu

Bekanntes Mitglied
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

Super-Moderator
Mitarbeiter
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

Bekanntes Mitglied
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.
 

jabaduu

Bekanntes Mitglied
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. ;)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
S HashMap mehrere Keys zu einem Value Java Basics - Anfänger-Themen 3
A Daten aus einer HashMap aus einer DB speichern und mit neuen Werten vergleichen Java Basics - Anfänger-Themen 8
T HashMap Lsite gibt die sachen nicht aus wie gewollt. Java Basics - Anfänger-Themen 3
krgewb HashMap Java Basics - Anfänger-Themen 2
B Hashmap richtig bauen, die Tripel auf Zahl abbildet? Java Basics - Anfänger-Themen 10
"java.util.HashMap.get(Object)" is null Java Basics - Anfänger-Themen 10
berserkerdq2 Hashmap, wie prüfe ich ob ein Key schon existiert Java Basics - Anfänger-Themen 19
S Durch HashMap iterieren Java Basics - Anfänger-Themen 8
rafi072001 Sortieren einer HashMap nach Values Java Basics - Anfänger-Themen 2
F gson mit einer Hashmap Java Basics - Anfänger-Themen 2
J JSON-HashMap Java Basics - Anfänger-Themen 3
J Hashmap Java Basics - Anfänger-Themen 13
C Hashmap zickt Java Basics - Anfänger-Themen 9
S HashMap contains() Methode Java Basics - Anfänger-Themen 1
Z Satz aufteilen und die Wörter zählen (HashMap) Java Basics - Anfänger-Themen 15
N enum Attribut von Objekten einer Hashmap ausgeben Java Basics - Anfänger-Themen 6
P Verschachtelte Hashmap Java Basics - Anfänger-Themen 6
I Sortiert eine HashMap nicht gleich wie eine ArrayList? Java Basics - Anfänger-Themen 1
B HashMap alphabetisch sortieren Java Basics - Anfänger-Themen 2
J HashMap Java Basics - Anfänger-Themen 6
M Enum-Variable HashMap zuweisen Java Basics - Anfänger-Themen 5
U Hashmap Iterator selbst implementieren Java Basics - Anfänger-Themen 10
N HashMap in List good practice? Java Basics - Anfänger-Themen 2
K Value eines HashMaps in einer HashMap wiedergeben. Java Basics - Anfänger-Themen 5
O Hashmap, ArrayList, LinkedList Java Basics - Anfänger-Themen 7
O HashMap - ArrayList Java Basics - Anfänger-Themen 29
E HashMap+Vererbung Java Basics - Anfänger-Themen 11
J Erhöhen eines Values als Integer bei gleichen Keys in HashMap Java Basics - Anfänger-Themen 12
N Methoden HashMap interne Werte miteinander vergleichen Java Basics - Anfänger-Themen 7
W The type Long is not visible HashMap Java Basics - Anfänger-Themen 4
M Objekt mit Hashmap vergleichen Java Basics - Anfänger-Themen 22
S Gibt es für die Klasse HashMap Generic Implementierungen? Java Basics - Anfänger-Themen 11
C HashMap - alle keys haben values der letzten put-Anweisung Java Basics - Anfänger-Themen 3
J Hashmap auslesen Java Basics - Anfänger-Themen 7
F HashMap sortieren <String, Long> Java Basics - Anfänger-Themen 3
GreenTeaYT HashMap dupliziert meine Elemente? Java Basics - Anfänger-Themen 2
shiroX Methoden Morse-Code Übersetzer mit HashMap Java Basics - Anfänger-Themen 5
E HashMap Problem Java Basics - Anfänger-Themen 5
P Hashmap anstatt LinkedList? Java Basics - Anfänger-Themen 6
T HashMap und die Methoden Java Basics - Anfänger-Themen 13
N Methoden Interaktives PDF mit HashMap befüllen Java Basics - Anfänger-Themen 0
Z Hashmap auseinandernehmen und analysieren Java Basics - Anfänger-Themen 7
B Durchlaufen von Hashmap und Arraylist Java Basics - Anfänger-Themen 8
F HashMap oder welches Array? Java Basics - Anfänger-Themen 4
T HashMap Java Basics - Anfänger-Themen 24
L Hashmap mit variablem Key Java Basics - Anfänger-Themen 9
M Collections Probleme mit Hashmap Java Basics - Anfänger-Themen 4
N Collections String in HashMap umwandeln Java Basics - Anfänger-Themen 3
Z HashMap richtig benutzen Java Basics - Anfänger-Themen 2
lgund HashMap // TS3 Query Java Basics - Anfänger-Themen 7
Z Hashmap Iterator löscht nicht Java Basics - Anfänger-Themen 8
E Hashmap Wert auslesen Java Basics - Anfänger-Themen 2
S Printstream für einen Hashmap Loop Java Basics - Anfänger-Themen 1
dat_vin OOP Hashmap und Attribute Java Basics - Anfänger-Themen 7
C Check ob eine HashMap schon existiert Java Basics - Anfänger-Themen 16
P Vererbung Eigene HashMap Variante Java Basics - Anfänger-Themen 2
R Hashmap in anderer Klasse nicht benutzbar Java Basics - Anfänger-Themen 1
T Java Hashmap Java Basics - Anfänger-Themen 3
L Gibt es etwas wie "HashMap <String, String, String> Java Basics - Anfänger-Themen 9
K HashMap mit Daten aus ArrayList befüllen Java Basics - Anfänger-Themen 14
S OOP Klasse mit static-Eigenschaften - HashMap füllen Java Basics - Anfänger-Themen 6
O HashMap Fragen Java Basics - Anfänger-Themen 8
T HashMap Werte einfügen, durchsuchen und auslesen Java Basics - Anfänger-Themen 17
M Semantisches Problem HashMap/Netzwerk Java Basics - Anfänger-Themen 4
D HashMap Keys durchlaufen Java Basics - Anfänger-Themen 2
B Zugriff auf csv-Datei per hashmap Java Basics - Anfänger-Themen 5
M HashMap keys ausgeben Java Basics - Anfänger-Themen 2
S In einer Hashmap Klassen regestrieren Java Basics - Anfänger-Themen 2
H Collections Was ist schneller - HashMap + Sort v TreeMap? Java Basics - Anfänger-Themen 75
F HashMap nach kleinstem Value durchsuchen Java Basics - Anfänger-Themen 11
G HashMap Java Basics - Anfänger-Themen 6
F Wortpaare - HashMap - ArrayList Java Basics - Anfänger-Themen 6
M HashMap Frage Java Basics - Anfänger-Themen 3
M HashMap - put() reagiert nicht? Java Basics - Anfänger-Themen 8
N Cast eines Objektes in eine Hashmap Java Basics - Anfänger-Themen 13
A CSV Zeilenweise einlesen und in einer HashMap speichern Java Basics - Anfänger-Themen 12
A Input/Output Hashmap in einem JPanel via JList anzeigen Java Basics - Anfänger-Themen 8
K HashMap auf leere Key-Value-Paare prüfen Java Basics - Anfänger-Themen 14
F Hilfe bei der HashMap. Java Basics - Anfänger-Themen 3
F HashMap vs. TreeMap Java Basics - Anfänger-Themen 5
B HashMap Java Basics - Anfänger-Themen 9
C Collections String[] als value in HashMap Java Basics - Anfänger-Themen 6
V Hashmap Iterieren Java Basics - Anfänger-Themen 4
C Csv File in Hashmap ausgeben Java Basics - Anfänger-Themen 14
T HashMap<String,Object> Werte auslesen Java Basics - Anfänger-Themen 5
I HashMap sortieren Java Basics - Anfänger-Themen 10
I HashMap Java Basics - Anfänger-Themen 11
H Collections Brauche modifizierte HashMap Java Basics - Anfänger-Themen 6
H TreeMap/HashMap synchronisieren Java Basics - Anfänger-Themen 2
A Datentypen Hashmap to Array Java Basics - Anfänger-Themen 11
D HashMap überschreibt Werte Java Basics - Anfänger-Themen 7
pg1337 Interface Comparable-Interface bei HashMap Java Basics - Anfänger-Themen 21
D erweiterte hashmap Java Basics - Anfänger-Themen 5
H HashMap<Int, String> - Er findet die Int-Klasse nicht. Java Basics - Anfänger-Themen 3
L HashMap zu JList Java Basics - Anfänger-Themen 6
S Erste Schritte HashMap Kurze Frage - Werte über Schleife ausgeben Java Basics - Anfänger-Themen 30
F Collections ArrayList oder Hashmap mittel Collections.sychronised Java Basics - Anfänger-Themen 6
B Klassen HashMap Zwei Objekte, gleicher Key Java Basics - Anfänger-Themen 4
N HashMap fehlerhafte Rückgabe Java Basics - Anfänger-Themen 7
K Durch eine HashMap wandern? Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Neue Themen


Oben