FindMapElement

[Martin66119]

Hallo.

ich habe mal mit Hash (MD5) getestet. Die Berechnung dauert auf schon 76ms. Also auf Basis von Hashwerten den Vergleich zu machen dauert um einiges länger, wenn ich die Zeit der Berechnung des Hashwertes mit eingeziehe. Der Code von Nic bracuht 18 ms. Da ist das Sortieren der beiden Listen mit drin.

Code: Alles auswählen

StartTime = ElapsedMilliseconds()  
test.s = "This is a test string! der 42 Zeichen hat!"
For i = 1 To 20000
  MD5$ = MD5Fingerprint(@test, StringByteLength(test))
Next i           
Time =ElapsedMilliseconds() - StartTime
 MessageRequester("Information", Str(Time), #PB_MessageRequester_Ok)

[Martin66119]

Nochmal eine Frage.

Wenn ich mir den Code von Nic anschaue schaut es wenigstens für mich als Laien so aus, als würde alles soweit möglich mit Pointern realisiert. Gibt es Teile im Code, die "einfach" (wenn auch nicht für mich) in ASM realisierbar wären.

[STARGÅTE]

Gibt es Teile im Code, die "einfach" (wenn auch nicht für mich) in ASM realisierbar wären.

Mal ganz nebenbei, der ganze Code wird sowieso vom Compiler in ASM kompiliert.

Nun zum "einfach":
Wenn der Code wirklich in ASM geschrieben wird, dann kannst du ihn überhaupt nicht mehr lesen, also schlecht für spätere änderungen!
EIne gute optimierung ist leider nicht "einfach" machbar, denn "einfach" wäre im prinzip das, was der Compiler aus deinem Code macht.

[NicTheQuick]

Die Maps in Purebasic sind eigentlich nichts anderes als HashMaps. Du musst da also nicht das Rad neu erfinden.

Ich nutze deswegen in meinem Code Pointer, weil ich es vermeiden will die Strings zu kopieren.

Wieso hast du die Liste list1() und list2() nicht mit einem Pointer realisiert, so wie *onlyIn1.String() und *onlyIn2.String() oder geht das nicht?

Irgendwo braucht man ja was, wo der Zeiger drauf zeigen kann. Das heißt die ursprüngliche Liste muss eben Strings enthalten.

Hast du eigentlich mal gemessen wie lange das Auslesen der Dateien braucht? Möglicherweise ist es dort viel problematischer mit der Geschwindigkeit als die Vergleichfunktion selbst.

Meine anderen Fragen hast du auch noch nicht beantwortet:

Warum muss es überhaupt so schnell sein? Was ist das Grundproblem? Du willst ganz viele Dateien einlesen und miteinander vergleichen? Oder willst du viele Dateien mit genau einer anderen vergleichen?

[Martin66119]

Zu deinen Fragen Nic,

1) Die Anzahl der Daten wird recht groß sein. Wie groß weiß ich noch nicht.
2) Es sollen zwei große Listen miteinander verglichen werden, Als Ergebnis soll Angezeigt werden was ist in Liste 1 und nicht in Liste 2 und was ist in Liste 2 und nicht in Liste 1 enthalten.
3) Wie bekommt man das am schnellsten hin.
4) Meine TestDaten sind 10000 x 10000 Datensätze. Diese werden in ca. 30 ms eingelesen. Du hast recht, dass das einlesen recht lange dauert. Da Einlesen wird aber bei z.B.
10.000.000 x 10.000.000 vermutlich nicht proportional steigen. Die Auswertung aber quadratisch zunehmen.

Ich suche also nach einem sehr schnellen Code. Den ich auch noch verstehe. Vielleich PB-Code und ein paar Inline ASM gehen vielleicht noch in meinen Kopf.
Grüße

[NicTheQuick]

Bei diesem Problem lässt sich nicht viel mit InlineASM heraus holen.
Im Übrigen wächst die Auswertung nicht quadratisch, sondern in O(log(n) * n), da Purebasic zum Sortieren Quicksort nutzt.

Am schnellsten ist es die Zeilen in allen Dateien alphabetisch zu sortieren, wie es meine diff-Funktion in den ersten beiden Zeilen macht und dann den Rest ablaufen zu lassen. Bleibt die Frage, wo die Differenzen ausgegeben werden sollen. In eine weitere Datei?

Also wenn du tatsächlich 10 Mio. Dateien hast, dann sortiere zuerst alle vor. Und dann lass meinen Code drüber laufen ohne die beiden 'SortList()'-Zeilen am Anfang.
Je nachdem, was du für eine Festplattenanbindung hast, kannst du ja gleich mehrere Threads nutzen, die sich immer eine Datei "krallen" und sortieren. Bei einem Quadcore kannst du so möglicherweise die Geschwindigkeit vervierfachen, falls die Festplatte auch hinter her kommt.
Hast du einmal alle Dateien sortiert, dann musst du nur noch den Code ohne die beiden 'SortList()'-Zeilen ausführen. Und der läuft in linearer Zeit zur Zeilenanzahl.

Wenn man jetzt noch Cache-bewusst arbeiten will, dann nimmt man auch keine LinkedLists, sondern Arrays oder gleich einen zusammenhängenden Speicherbereich für die ganze Datei und dann ein Array mit Pointern zu den Zeilenanfängen in diesem Speicherbereich. Da kann der Prozessor dann sehr gut große Stücke in seinen Cache packen und vergleichen.

Wenn ich mal so annehme, dass jeder der 10 Mio. Dateien 10 MB groß ist, dann hast du ja schon 95 TB an Daten. Und selbst bei nur 1 MB pro Datei sind es ja schon 9,5 TB. 1 MB könnte man annehmen, wenn jede Zeile in so einer Datei 80 Zeichen lang ist und die Datei aus ca. 13000 Zeilen besteht.

Also ich finde die Datenmengen gerade etwas absurd, aber wenn du meinst.

[STARGÅTE]

Also für mich klingt das nach einem Synchronisations Programm.
Allerdings reicht es dafür doch nicht, nur die Datei-Namen zu vergleichen?
Schließlich können sich Dateien doch ändern,
entweder der Name selbst und der Inhalt bleibt gleich oder
der Inhalt ändert sich aber der Name bleibt gleich.

Es wäre echt toll Martin66119, wenn du endlich mal auf den Punkt kommen könntest
und nicht immer nur Vorderungen stellst zu einem Problem, was aktuell zu wenig Hintergrundinformationen hat!

[Martin66119]

Hallo Nic,

jeder Datensatz hat nicht mehr wie 80 Zeichen (im Mittel 60). Meine Testdatei hat 12.000 Zeilen und ist 1.1 MB groß.

Es geht nur darum, eine Möglichkeit zu implementieren, die möglichst schnell ist. Einfach etwas lernen, wie man so was macht.

Vielen Dank für die hilfe


Grüße
Martin

[NicTheQuick]

Wie gesagt, man kann jetzt noch mehrere Threads gleichzeitig starten, die jeweils ein Vergleich machen bzw. am Anfang erst mal alles vorsortieren. Aber das war's auch schon an Geschwindigkeitsoptimierung. Ab jetzt hängt es an deiner Hardware, die schneller werden muss.

Mir ist zumindest kein schnelleres Verfahren bekannt. Die Sortierung geht nicht schneller als in O(log(n) * n) und das Differenzieren geht nicht schneller als O(n), logischerweise.

Man kann natürlich auch mit Hashs arbeiten. Das heißt alle Dateien durchlaufen und jede ihrer Zeilen hashen. Das kann man auch wieder wunderbar parallelisieren und somit die Geschwindigkeit erhöhen. Im gleichen Zug könnte man alle Hashs in einer gemeinsamen Datenbank speichern mit Links zu ihren Ursprungsdateien und der Zeile, von der sie abstammen. Dann sieht man schon mal welche Zeile in mehreren Dateien vorkommt und welche Zeilen nur in dieser einen Datei vorkommen und sonst nirgendwo. Daraufhin ist es super einfach herauszufinden wie die Unterschiede zwischen verschiedenen Dateien sind.

Jetzt kannst du dich ja mal daran versuchen.

[Martin66119]

Guten Abend,

nun noch eine Frage. Folgender Code steh in der Hilfe. Diesen könnte ich also verwenden, um meine Zeichenkette direkt in den Speicher zu schreiben. Wird der String im Memory mut Null abgeschlossen. Wenn nicht, was muss ich denn dann noch reinschreiben.

Code: Alles auswählen

*MemoryID = AllocateMemory(5000)
  If *MemoryID
    Debug "Startadresse des 5000 Byte Speicherbereichs ist:"
    Debug *MemoryID
    PokeS(*MemoryID, "Wir speichern diesen String im Speicherbereich")
    FreeMemory(*MemoryID)  ; wird am Ende des Programms auch automatisch erledigt
  Else
    Debug "Konnte den angeforderten Speicher nicht reservieren!"
  EndIf

__________________________________________________
Code-Tags hinzugefügt
08.07.2014
RSBasic