PureBoard

Das deutsche PureBasic-Forum
https://www.purebasic.fr/german/

FindMapElement

https://www.purebasic.fr/german/viewtopic.php?t=28132

Seite 7 von 9

Re: FindMapElement

Verfasst: 28.06.2014 14:33
von Martin66119
Hallo Nic,

dein Code braucht ca. 18 ms um die Daten herauszusuchen. Der von matbal nur 1-2ms. Klar,in deinem werden beide Listen sortiert. Das sortieren dauert ca.12ms und das Suchen der Daten dann noch ca. 6ms (auf meinem rechner). Der Geschwindigkeitsunterschied ist ca. 10. Wo liegt denn dieser größe Unterschied im Code versteckt? Das ist das was mich wundert.

Re: FindMapElement

Verfasst: 28.06.2014 14:55
von NicTheQuick
Hast du bei matbal auch die Zeit gestoppt, die es dauert die Zeilen in die Map einzutragen? Wahrscheinlich nicht. ;)

Ich habe mir jetzt selbst mal zwei Dateien mit je 20000 Zeilen erstellt und mal geschaut wie lange es so dauert.
matbals Code braucht bei mir 31 ms. Dabei werden auch die Zeilen 'Compare(key$)\ExistsInFile2 + 1' und 'Compare(key$)\ExistsInFile1 + 1' gemessen. Die brauchen nämlich die meiste Zeit.
Wenn man die #Slots auf 10000 setzte, dann dauert es nur noch 16 ms, aber trotzdem länger als bei mir. :wink:

Mein Code braucht hingegen nur 10 ms. Also ist matbals Code drei mal langsamer als meiner und du hast du falsch gemessen. Du hast wohl nur die ForEach-Schleife bei matbal gemessen. Das die so gut wie keine Zeit braucht, ist logisch, da hier nur die Map durchlaufen wird ähnlich einer LinkedList. Die eigentliche Zeit braucht die Map beim zuweisen neuer Elemente, da die Keys dort gehasht werden und in den internen Suchbaum eingebaut werden müssen. Das heißt je nach Zeilenlänge dauert es hier eine Weile bis sie gehasht wurde und dann dauert es nochmal logarithmische Zeit (je nach Anzahl Slots) bis der Hash in der Map an die richtige Stelle gesetzt wurde. Und diese Zeit hast du vergessen zu messen.

Code: Alles auswählen

EnableExplicit

Structure CompareMapStruc
	ExistsInFile1.i
	ExistsInFile2.i
EndStructure

#Slots = 10000 ; Dieser Wert erhöhen, um die Zugriffsgeschwindigkeit bei großen Datenmengen zu erhöhen (siehe PB-Hilfe)
NewMap Compare.CompareMapStruc(#Slots)
Define key$

; Zunächst lesen wir die Datei zeilenweise ein
NewList lines.s()

If ReadFile(0, "/tmp/Datei1.txt")
	While Not Eof(0)
		If AddElement(lines())
			lines() = ReadString(0)
		EndIf
	Wend
	CloseFile(0)
EndIf

; Dann fügen wir die Zeilen in die Map ein und messen die Zeit
Define time1.i = ElapsedMilliseconds()
ForEach lines()
	Compare(lines())\ExistsInFile1 + 1
Next
time1 = ElapsedMilliseconds() - time1

; Das selbe machen wir für die zweite Datei
ClearList(lines())

If ReadFile(0, "/tmp/Datei2.txt")
	While Not Eof(0)
		If AddElement(lines())
			lines() = ReadString(0)
		EndIf
	Wend
	CloseFile(0)
EndIf

Define time2.i = ElapsedMilliseconds()
ForEach lines()
	Compare(lines())\ExistsInFile2 + 1
Next
time2 = ElapsedMilliseconds() - time2

; Und jetzt messen wir noch die Ausgabeschleife
Define time3.i = ElapsedMilliseconds()
ForEach Compare()
	If Compare()\ExistsInFile1 > Compare()\ExistsInFile2
		Debug "Nur in Datei 1: >" + MapKey(Compare()) + "<"
		Debug "     Anzahl: " + Str(Compare()\ExistsInFile1 - Compare()\ExistsInFile2)
		Debug "---------------------------------------------"
	ElseIf Compare()\ExistsInFile1 < Compare()\ExistsInFile2
		Debug "Nur in Datei 2: >" + MapKey(Compare()) + "<"
		Debug "     Anzahl: " + Str(Compare()\ExistsInFile2 - Compare()\ExistsInFile1)
		Debug "---------------------------------------------"
	EndIf
Next
time3 = ElapsedMilliseconds() - time3

MessageRequester("Time", "time1 = " + time1 + #LF$ +
                         "time2 = " + time2 + #LF$ +
                         "time3 = " + time3 + #LF$ +
                         "total = " + Str(time1 + time2 + time3))

Re: FindMapElement

Verfasst: 28.06.2014 15:16
von Martin66119
Ja, ich hatte nur die Zeit der Auswerteschleife gemessen. Da hast du recht. Bei einem zweiten Vergleich habe ich folgendes verglichen.

- Bei deinem Code nach der Sortieren der Listen bis vor EndProcedure (ca. 6ms)
- Beim Code von matbal ForEach-Schleife 1-2ms

Da habe ich aber auch nicht an einem vergleichbaren Messpunkt die Zeit ermittelt. Oder?
Ist das was in der ForEach Schleife steht nicht vergleichbar mit dem was bei dir in der Procedure nach dem Sortieren gemacht wird?

Re: FindMapElement

Verfasst: 28.06.2014 16:26
von NicTheQuick
Ist es letztendlich nicht wichtig wie lange alles zusammen dauert? Also das Auslesen aus der Datei bis hin zum Auswerten und Festschreiben der Auswertung? Wenn das, was du mit den festgestellten Unterschieden machen willst, sowieso nochmal länger dauert, dann ist es doch auch egal, ob die Auswertung selbst ein paar ms länger oder weniger brauchen. Vermutlich wird das Lesen aus den Dateien sowieso am längsten brauchen, wenn du davon gleich einen ganzen Haufen vergleichen willst.

Re: FindMapElement

Verfasst: 28.06.2014 20:58
von Sicro
Hier noch eine Variante von NicTheQuicks Code mit Threads:

Code: Alles auswählen

Global Thread1_FilePath.s, Thread1_Error.i, NewList Thread1_List.s()
Global Thread2_FilePath.s, Thread2_Error.i, NewList Thread2_List.s()

Procedure Thread1(void.i)
  
  Protected File.i
  Protected FileLine.s
  
  File = ReadFile(#PB_Any, Thread1_FilePath)
  If IsFile(File)
    While Not Eof(File)
      FileLine = ReadString(File)
      AddElement(Thread1_List())
      Thread1_List() = FileLine
    Wend
    CloseFile(File)
    SortList(Thread1_List(), #PB_Sort_Ascending)
  Else
    Thread1_Error = #True
  EndIf
  
EndProcedure

Procedure Thread2(void.i)
  
  Protected File.i
  Protected FileLine.s
  
  File = ReadFile(#PB_Any, Thread2_FilePath)
  If IsFile(File)
    While Not Eof(File)
      FileLine = ReadString(File)
      AddElement(Thread2_List())
      Thread2_List() = FileLine
    Wend
    CloseFile(File)
    SortList(Thread2_List(), #PB_Sort_Ascending)
  Else
    Thread2_Error = #True
  EndIf
  
EndProcedure

Procedure.i diff()
    
  ; Threads lesen die Dateien und sortieren die Listen
  Protected Thread1.i = CreateThread(@Thread1(), 0)
  If Not IsThread(Thread1)
    ProcedureReturn #False
  EndIf
  Protected Thread2.i = CreateThread(@Thread2(), 0)
  If Not IsThread(Thread2)
    KillThread(Thread1)
    ProcedureReturn #False
  EndIf
  
  ; Warten, bis die Threads beendet wurden
  Repeat
    Delay(1)
  Until (IsThread(Thread1) = 0 And IsThread(Thread2) = 0)
    
  ; Kam es zu Fehlern in den Threads?
  If Thread1_Error Or Thread2_Error
    ProcedureReturn #False
  EndIf
  
  Protected NewList *onlyIn1.String()
  Protected NewList *onlyIn2.String()
  
  ; Erstes Element bei den Listen setzen. Ist keins vorhanden, wird abgebrochen.
  If FirstElement(Thread1_List()) = 0 Or FirstElement(Thread2_List()) = 0
    ProcedureReturn #False
  EndIf
  
  Protected next1.i, next2.i
  
  Repeat
    ; Nur, damit man sieht, was gerade verglichen wird
    ;Debug "Vergleiche '" + list1() + "' - '" + list2() + "'"
    
    next1 = #True
    next2 = #True
    If (Thread1_List() = Thread2_List())
      ; Element ist in beiden Listen, also tue nichts
    ElseIf (Thread1_List() < Thread2_List())
      ; Element in Liste 1 ist nicht in Liste 2
      If AddElement(*onlyIn1())
        *onlyIn1() = @Thread1_List()
      EndIf
      next2 = #False
    Else
      ; Element in Liste 2 ist nicht in Liste 1
      If AddElement(*onlyIn2())
        *onlyIn2() = @Thread2_List()
      EndIf
      next1 = #False
    EndIf
    
    If (next1)
      If (Not NextElement(Thread1_List()))
        ; Wenn es in Liste 1 nicht mehr weiter geht
        While NextElement(Thread2_List())
          If AddElement(*onlyIn2())
            *onlyIn2() = @Thread2_List()
          EndIf
        Wend
        Break
      EndIf
    EndIf
    If (next2)
      If (Not NextElement(Thread2_List()))
        ; Wenn es in Liste 2 nicht mehr weiter geht
        While NextElement(Thread1_List())
          If AddElement(*onlyIn1())
            *onlyIn1() = @Thread1_List()
          EndIf
        Wend
        Break
      EndIf
    EndIf
  ForEver
  
  Debug ""
  Debug "Zeilen, die nur in Liste 1 vorhanden sind:"
  ForEach *onlyIn1()
    Debug "'" + *onlyIn1()\s + "'"
    ;MessageRequester("Information", *onlyIn1()\s, #PB_MessageRequester_Ok)
  Next
  Debug ""
  
  Debug "Zeilen, die nur in Liste 2 vorhanden sind:"
  ForEach *onlyIn2()
    ;MessageRequester("Information", *onlyIn2()\s, #PB_MessageRequester_Ok)
    Debug "'" + *onlyIn2()\s + "'"
  Next
  Debug ""
  
  ProcedureReturn #True
  
EndProcedure

; ----------------------Hauptprogramm-----------------------------------

StartTime = ElapsedMilliseconds()
Thread1_FilePath = "D:\PB\ExcelDll\Datei1.csv"
Thread2_FilePath = "D:\PB\ExcelDll\Datei2.csv"
If diff()
  Time = ElapsedMilliseconds() - StartTime
  MessageRequester("Information", Str(Time))
Else
  MessageRequester("Fehler", "Beim Vergleichen sind Fehler aufgetreten")
EndIf
Threads können gleichzeitig ausgeführt werden, dadurch könnte der Code mit Prozessoren mit MultiThread-Unterstützung nochmal schneller sein.
Ein Geschwindigkeitsverlust könnte durch das ständige hin und her Springen zwischen ReadString(Datei1) und ReadString(Datei2) entstehen (besonders, wenn die zwei Dateien zu weit auseinander auf dem Datenträger liegen), befinden sich die zwei Dateien aber auf unterschiedlichen Datenträgern, wird nochmal die Geschwindigkeit gesteigert, weil sie gleichzeitig gelesen werden.

Re: FindMapElement

Verfasst: 28.06.2014 21:43
von Martin66119
das geht ja noch etwas flotter.

Die Gesamtzeit "lesen + auswerten" dauert ohne Threads ca. 300ms und mit nur noch ca. 230ms.
Das geht ja noch um einiges flotter damit. Echt schnell und das mit meinem langsamen Rechner.
Vielen vielen Dank.

Ich glaube, damit habe ich ein optimales Ergebnis.

Danke an alle für die Mühe.
Grüß
Martin

Re: FindMapElement

Verfasst: 28.06.2014 22:30
von Martin66119
Habegerade zwei Dateien erstellt. jede mit 1.000.000 Zeilen

Code: Alles auswählen

If CreateFile(0, "D:\PB\ExcelDll\AText1.csv")         ; wir erstellen eine neue Textdatei...
  For a=1 To 1000000
    s.s=Str(Random(10000))
      WriteStringN(0, s.s+"Yxcvbnm,.-#äölkjhgfdsaqwertzuiopü+ß0987654321qwertzuiopü+#äölkjhgfdsayxcvbnm,.-äölkjhgfdsaqwertzuiop")  ; wir schreiben 10 Zeilen (jede mit einem Zeilenumbruch)
    Next
    CloseFile(0)                       ; schließen der zuvor geöffneten Datei und damit endgültiges Abspeichern der Daten
  Else
    MessageRequester("Information","Konnte Datei nicht erstellen!")
  EndIf
  If CreateFile(0, "D:\PB\ExcelDll\AText2.csv")         ; wir erstellen eine neue Textdatei...
  For a=1 To 1000000
    s.s=Str(Random(10000))
      WriteStringN(0, s.s+"Yxcvbnm,.-#äölkjhgfdsaqwertzuiopü+ß0987654321qwertzuiopü+#äölkjhgfdsayxcvbnm,.-äölkjhgfdsaqwertzuiop")  
    Next
    CloseFile(0)                       ; schließen der zuvor geöffneten Datei und damit endgültiges Abspeichern der Daten
  Else
    MessageRequester("Information","Konnte Datei nicht erstellen!")
  EndIf
Jede der Dateien ist 112MB groß.

Das Einlesen einschließlich der Auswertung hat 58 Sekunden gedauert. Eurer Code ist sehr gut!!

Grüße
Martin

Re: FindMapElement

Verfasst: 29.06.2014 12:27
von Martin66119
Guten Tag,

Wie ihr wisst, habe ich selbst keine Erfahrung, um einen solchen Code zu programmieren, den ich jetzt habe. Deshalb nochmals herzlichen Dank für den Code. Nun wollte ich hier oder aber auch im englischen Forum noch was nachfragen. Wenn man mal den Einlesevorgang außen vor lässt, welche Schleife wäre in ASM nicht zu aufwenidig zu realisieren und würde auch noch einen Geschwindigkeitsvorteil bringen. Dass ich das nicht hinbekomme ist wohl klar. Von dem Aufwand der dahinter stecken würde, habe ich auch keine Vorstellung. Das einzige was ich mal gemacht habe ist, den ausführbaren Code zu disassemblieren.

Grüße und einen schönen Sonntag
Martin

PS.: Sorry schonmal für die Frage.

Re: FindMapElement

Verfasst: 29.06.2014 12:53
von STARGÅTE
Martin66119 hat geschrieben:Wenn man mal den Einlesevorgang außen vor lässt, welche Schleife wäre in ASM nicht zu aufwenidig zu realisieren und würde auch noch einen Geschwindigkeitsvorteil bringen. [...] Von dem Aufwand der dahinter stecken würde, habe ich auch keine Vorstellung.
Was du immer mit ASM hast. /:->
Natürlich ist der Aufwand groß, da du ASM und PB nicht einfach mischen kannst.
Demnach müsstest du Sachen wie die Listenverwaltung und Sortierung ebenfalls in ASM schreiben, denn hier und da ein bisschen ASM einzufügen macht den Code nicht schneller.
Martin66119 hat geschrieben:Dass ich das nicht hinbekomme ist wohl klar.
Das wir dir das in unserer Freizeit nicht auf dem Silbertablett servieren ist wohl auch klar. :evil:

Re: FindMapElement

Verfasst: 29.06.2014 19:17
von Martin66119
Hallo Stargate,

also viel zu kompliziert. Dann bleibt jeztzt alles so wie es ist.

Gruß und Dank an alle die mir geholfen haben
Alle Zeiten sind UTC+02:00
Seite 7 von 9

Powered by phpBB® Forum Software © phpBB Limited

Deutsche Übersetzung durch phpBB.de