Stringvergleich

[Martin66119]

Hallo,

das was ich vor hatte, klappt soweit. Nur der Stringvergleich dauert recht lange, da ich 100000 Datensätze mit 95000 Datensätze vergleiche.

Was ich brauche ist folgendes:

a) Welche Datensätze sind in den 100000 drin, die in den 95000 nicht enthalten sind.
b) Welche Datensätze sind in den 30000 mit denen in den 20000 identisch.

Die 100000 Datensätze sind in einer Liste1() und die 95000 in einer Liste2() enthalten.
Die Datensätze a) sollen in einer Liste_verschieden() aufgenommen werden.
Die Datensätze b) sollen in einer Liste_identisch() aufgenommen werden.
Jeder Datensatz koomt nur 1x pro Liste vor.

Code: Alles auswählen

ForEach Liste1()
  ForEachListe2()
   If Liste1() = Liste2()
     Gefunden = 1
     AddElement(Liste_identisch())
     Liste_identisch() = Liste1()
     DeleteElement(Liste1())
     DeleteElement(Liste2())
   endif
next
if Gefunden = 0
  AddElement(Liste_verschieden(Liste1())
  Liste_verschieden() = Liste1()
Gefunden = 0
endif
Next

Gibt es eine Möglichkeit das zu beschleunigen?

Grüße und Danke schon einmal
Martin

[matbal]

Die Aufgabenstellung ist sehr ähnlich, wie die im vorherigen Thread.

Ich greife daher einfach meine alte Lösung auf. Ich habe sie geringfügig modifiziert. Statt doppelte zu löschen, kennzeichne ich sie nur. Ich speichere zu jeder Zeile den Text, die Zeilennummer und ein Flag (dup), das ich dann setze, wenn die Zeile in beiden Dateien gefunden wird.

Der Abgleich geschieht in meiner Procedure CompareText(). Damit das ganze schnell geht, werden beide Liste zuerst sortiert. Dann werden beide Listen gleichzeitig synchron durchgesehen. Finde ich in beiden Listen den gleichen Eintrag, setzte ich das dazugehörige Strukturelement "dup" auf 1.

In den Foreach-Schleifen muß ich nur pro Element prüfen, ob 'dup' gesetzt ist oder nicht.

Code: Alles auswählen

Structure ZeileStruc
   Text$   ; Zeileninhalt
   n.i     ; Zeilennummer
   dup.i   ; wird 1, wenn sie auch in der anderen Datei vorkommt
EndStructure

Procedure LoadFile(File$, List Text.ZeileStruc())
   Protected n
   
   If ReadFile(0, File$)
      While Not Eof(0)
         AddElement(Text())
         With Text()
            \Text$ = ReadString(0)
            \n = n
            n + 1
         EndWith
      Wend
      CloseFile(0)
   EndIf
   
   ProcedureReturn n
   
EndProcedure

Procedure CompareText(List Text1.ZeileStruc(), List Text2.ZeileStruc())
   ; Vergleicht zwei Listen
   
   ; Beide Texte sortieren
   SortStructuredList(Text1(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\Text$), #PB_Sort_String)
   SortStructuredList(Text2(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\Text$), #PB_Sort_String)
   
   ; In beiden Dateien zeilen weise einmal von oben nach
   ; unten durchgehen und vergleichen
   ; Solange e1 und e2 nicht NULL sind, ist das Ende der Listen nicht erreicht.
   
   Protected e1 = FirstElement(Text1())   
   Protected e2 = FirstElement(Text2())   
   
   While e1 And e2
      
      If Text1()\Text$ < Text2()\Text$
         e1 = NextElement(Text1())
         
      ElseIf Text1()\Text$ > Text2()\Text$
         e2 = NextElement(Text2())
         
      ElseIf Text1()\Text$ = Text2()\Text$
         Text1()\dup = 1   ; Duplikat in 1 markieren
         Text2()\dup = 1   ; Duplikat in 2 markieren
         
         e1 = NextElement(Text1())
         e2 = NextElement(Text2())
         
      EndIf
   Wend
   
   ; Sortierung rückgängig machen
   SortStructuredList(Text1(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\n), #PB_Sort_Integer)
   SortStructuredList(Text2(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\n), #PB_Sort_Integer)
   
EndProcedure


NewList Text1.ZeileStruc()
NewList Text2.ZeileStruc()

Define File1$ = "Text1.txt"
Define File2$ = "Text2.txt"

LoadFile(File1$, Text1())
LoadFile(File2$, Text2())
CompareText(Text1(), Text2())

Debug "Nur in Text1 enthalten: ------------------------"
ForEach Text1()
   If Text1()\dup = 0
      Debug Text1()\Text$
   EndIf
Next 

Debug "Nur in Text2 enthalten -------------------------"
ForEach Text2()
   If Text1()\dup  = 0
      Debug Text2()\Text$
   EndIf
Next

Debug "In beiden Dateien enthalten --------------------"
ForEach Text1()
   If Text1()\dup = 1
      Debug Text1()\Text$
   EndIf
Next

[helpy]

Nur ein paar kleine Änderungen zum ersten Beitrag:

Code: Alles auswählen

Gefunden = #False
ForEach Liste1()
	
	ForEach Liste2()
		If Liste1() = Liste2()
			Gefunden = #True
			Break    ; Innere Schleife muss nicht weiter durchlaufen werden!
		EndIf
	Next
	
	If Gefunden
		AddElement(Liste_identisch())
		Liste_identisch() = Liste1()
		; DeleteElement(Liste1())      Muss für richtige Funktion der Schleife nicht sein!
		DeleteElement(Liste2())
		Gefunden = #False
	Else
		AddElement(Liste_verschieden())
		Liste_verschieden() = Liste1()
	EndIf
	
Next

[matbal]

Eine Variante mit reinen String-Listen, falls es nicht stört, daß alle Listen am Ende sortiert sind...

Innerhalb der Procedur werden die gleichen aus Text1$() und Text2$() entfernt und in Gleich$() aufgenommen.
Das heißt, am Ende liegen 3 sortierte Listen vor: das, was nur in Liste 1 ist, das was nur in Liste 2 ist und das, was in beiden Listen war.

Code: Alles auswählen

Procedure Compare(List Text1$(), List Text2$(), List Gleich$())
   ; Vergleicht die Einträge zweier String-Listen
   
   SortList(Text1$(), #PB_Sort_Ascending)
   SortList(Text2$(), #PB_Sort_Ascending)
   
   ; Solange e1 und e2 nicht NULL sind, ist das 
   ; Ende der Listen nicht erreicht
   
   Protected e1 = FirstElement(Text1$())   
   Protected e2 = FirstElement(Text2$())   
   
   While e1 And e2
      If Text1$() < Text2$()
         e1 = NextElement(Text1$())
         
      ElseIf Text1$() > Text2$()
         e2 = NextElement(Text2$())
         
      ElseIf Text1$() = Text2$()
         
         AddElement(Gleich$())    ; Text gleich => kommt in neue Liste
         Gleich$() = Text1$()
         
         DeleteElement(Text1$()) ; und wird aus beiden Listen entfernt
         DeleteElement(Text2$())
         
         e1 = NextElement(Text1$())
         e2 = NextElement(Text2$())
         
      EndIf
   Wend
   
EndProcedure

[Martin66119]

Vielen Dank für die Hilfe,

den größten Zeitgewinn habe ich wenn ich die schleife mit break beende.

Durch die anderweitigen Änderungen kommt noch mal etwas Zeitgewinn hinzu, den ich im Moment mit meinen Testdaten nicht erfassen kann.

Vielen vielen Dak

[Martin66119]

Einen schönen guten Morgen!

Leider dauert mir das ganz suchen immer noch zu lange.

Nun eine anderer Ansatz.

1) Zusammenfügen der beiden Listen mit MergeLists
2) Sortieren der zusammengefügten Liste
3) Überprüfen wie häufig jedes einzelne ListenElement vorkommt
4) Die Häufigkeit jedem einzelnen ListenElement zuordnen - Liste1()\Anzahl -
5) Ausgabe der ListenElemente mit der Anzahl = 1 in die Datei_1
6) Ausgabe der Listenelemente mit der Anzahl > 1 in die Datei_2

Wie geht man nun vor, um die Schleife für Punkt 3 und 4 in der Geschwindigkeit optimal zu realisieren?

[matbal]

Ich glaube, du hast die meine Vorschläge noch nicht angesehen oder nicht verstanden. Hier mal ein vollständiger Demo-Code mit Zeitmessung.

CreateDatenFile() erstellt eine Datei zum Testen mit Zufallszahlen.
LoadFile() lädt eine Textdatei in eine Liste
CompareText() vergleicht zwei Listen und kennzeichnet Duplikate
SaveFile() speichert eine Liste wieder als Textdatei

Ich erstelle also zwei Dateien.
Ich lade sie in zwei Listen.
Ich gleiche die beiden Listen ab, dann weiß ich, wo überall Duplikate sind
Ich speichere vier Dateien. Die beiden Dateien, die die gleichen Einträge enthalten unterscheiden sich nur in der Sortierung ihrer Einträge, da sie einmal von der ersten Datei stammen, und einmal von der zweiten Datei.

Das reine heraussuchen von Doppelten Einträgen dauert bei mir mit 100.000 Einträgen in den Dateien unter einer Sekunde. Bei einer Million Einträgen in den Dateien im einstelligen Sekundenbereich. (6 Sekunden im Schnitt)

Code: Alles auswählen

EnableExplicit

Structure ZeileStruc
   Text$   ; Zeileninhalt
   n.i     ; Zeilennummer
   dup.i   ; Duplikat 
EndStructure

Procedure CreateDatenFile(File$, Anzahl)
   ; Erstellt eine Datei mit verschiedenen Zahlen
   
   Protected i
   If CreateFile(0, File$)
      For i = 1 To Anzahl
         WriteStringN(0, Str(Random(Anzahl)))
      Next i
      CloseFile(0)
   EndIf
      
EndProcedure

Procedure LoadFile(File$, List Text.ZeileStruc())
   ; Lädt eine Datei in eine Liste
   Protected n
   
   If ReadFile(0, File$)
      While Not Eof(0)
         AddElement(Text())
         With Text()
            \Text$ = ReadString(0)
            \n = n
            n + 1
         EndWith
      Wend
      CloseFile(0)
   EndIf
   
   ProcedureReturn n
   
EndProcedure

Procedure CompareText(List Text1.ZeileStruc(), List Text2.ZeileStruc())
   ; Vergleicht zwei Listen
   
   ; Beide Texte sortieren
   SortStructuredList(Text1(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\Text$), #PB_Sort_String)
   SortStructuredList(Text2(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\Text$), #PB_Sort_String)
   
   ; In beiden Dateien zeilen weise einmal von oben nach
   ; unten durchgehen und vergleichen
   ; Solange e1 und e2 nicht NULL sind, ist das Ende der Listen nicht erreicht.
   
   Protected e1 = FirstElement(Text1())   
   Protected e2 = FirstElement(Text2())   
   
   While e1 And e2
      
      If Text1()\Text$ < Text2()\Text$
         e1 = NextElement(Text1())
         
      ElseIf Text1()\Text$ > Text2()\Text$
         e2 = NextElement(Text2())
         
      ElseIf Text1()\Text$ = Text2()\Text$
         Text1()\dup = 1   ; Duplikat in 1 markieren
         Text2()\dup = 1   ; Duplikat in 2 markieren
         
         e1 = NextElement(Text1())
         e2 = NextElement(Text2())
         
      EndIf
   Wend
   
   ; Sortierung rückgängig machen
   SortStructuredList(Text1(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\n), #PB_Sort_Integer)
   SortStructuredList(Text2(), #PB_Sort_Ascending, OffsetOf(ZeileStruc\n), #PB_Sort_Integer)
   
EndProcedure

Procedure SaveFile(File$, List Text.ZeileStruc(), dup)
   ; Speichert eine Liste in eine Datei
   
   If CreateFile(0, File$)
      ForEach Text()
         If Text()\dup = dup
            WriteStringN(0, Text()\Text$)
         EndIf
      Next 
      CloseFile(0)
   EndIf
   
EndProcedure

OpenConsole()

NewList Text1.ZeileStruc()
NewList Text2.ZeileStruc()

Define File1$ = "Datensatz1.txt"
Define File2$ = "Datensatz2.txt"
Define t

PrintN("Erstelle Datensatz1")
CreateDatenFile(File1$, 100000)

PrintN("Erstelle Datensatz1")
CreateDatenFile(File2$, 100000)

PrintN("Lade Datensatz1")
LoadFile(File1$, Text1())

PrintN("Lade Datensatz2")
LoadFile(File2$, Text2())

t = ElapsedMilliseconds()

PrintN("Vergleiche")
CompareText(Text1(), Text2())

PrintN(#CRLF$ + "Dauer: " + Str(ElapsedMilliseconds() - t) + " ms" + #CRLF$)

PrintN("Speichere 'Nur in 1'")
SaveFile("Nur in 1.txt", Text1(), 0)

PrintN("Speichere 'Nur in 2'")
SaveFile("Nur in 2.txt", Text2(), 0)

PrintN("Speichere 'Gleiche aus 1'")
SaveFile("Gleiche aus 1.txt", Text1(), 1)

PrintN("Speichere 'Gleiche aus 2'")
SaveFile("Gleiche aus 2.txt", Text2(), 1)

PrintN("ENDE")
Input()

[NicTheQuick]

3) Überprüfen wie häufig jedes einzelne ListenElement vorkommt
4) Die Häufigkeit jedem einzelnen ListenElement zuordnen - Liste1()\Anzahl -


Wie geht man nun vor, um die Schleife für Punkt 3 und 4 in der Geschwindigkeit optimal zu realisieren?

Da die Listen ja sortiert sind, kommen gleiche Listenelemente immer direkt nacheinander. Man muss also schauen, ob beim Durchgehen der Listen bestimmte Einträge mehrmals nacheinander kommen. Falls ja, gibt es sie eben doppelt.

Aber hier erstmal noch meine Möglichkeit mit Maps:

Code: Alles auswählen

Procedure CompareText(List Text1.s(), List Text2.s(), List Gleich.s())
	Protected NewMap Map1.i(ListSize(Text1())), *count.Integer
	
	; Füge alle Elemente von Text1 zur Map1 hinzu
	ForEach Text1()
		*count = FindMapElement(Map1(), Text1())
		If (Not *count)
			AddMapElement(Map1(), Text1())
			Map1() = 1
		Else
			*count\i + 1
		EndIf
	Next
	
	; Vergleiche, welche Einträge von Text2 in der Map sind
	ForEach Text2()
		If (FindMapElement(Map1(), Text2()))
			If AddElement(Gleich())
				Gleich() = Text2()
			EndIf
		EndIf
	Next
EndProcedure

; B E I S P I E L

DataSection
	BeginLists:
		Data.i 5
		Data.s "a", "b", "c", "d", "e"
		Data.i 8
		Data.s "a", "e", "g", "5", "h", "c", "z", "Hundekuchen"
EndDataSection

NewList Text1.s()
NewList Text2.s()
NewList Gleich.s()

Restore BeginLists
Define i.i, max.i
Read.i max
For i = 1 To max
	If AddElement(Text1())
		Read.s Text1()
	EndIf
Next
Read.i max
For i = 1 To max
	If AddElement(Text2())
		Read.s Text2()
	EndIf
Next

Compare(Text1(), Text2(), Gleich())
ForEach Gleich()
	Debug Gleich()
Next

Wobei ich matlabs Methode favorisieren, da sie mit einer Laufzeit von O(n·log(n)) arbeitet. Meine Laufzeit ist theoretisch O(n), aber je nach Anzahl der zu vergleichenden Werte hat immer eine Methode die bessere Geschwindigkeit. Vermutlich ist bei riesigen Datenmengen meine Methode noch die schnellste, aber um solche Mengen geht es ja hier nicht.

Edit:
Funktion schneller gemacht.

[NicTheQuick]

Okay, wenn ich jetzt den Test oben nutze, dann ist meine Version doch nochmal erheblich langsamer. ^^

Edit:
Ich habe noch einen bösen Fehler in meiner Funktion gehabt. Jetzt ist sie sogar schneller als die Compare-Funktion von matlab. Bei 1000000 Zeilen braucht sie bei mir nur 2400 ms, matlabs Methode braucht dafür 6100 ms. Der Trick war nur der Map vorher genügend Slots zu geben. Theoretisch könnte man die Map auch gleich schon füllen, wenn man die Datei einliest. Das macht nochmal einiges schneller, weil man das Kopieren der Datensätze von der Liste zur Map nicht mehr machen muss.

[matbal]

Bei 1.000.000 geht bei meiner Prozedur die meiste Zeit beim Sortieren drauf.

Text sortieren = 2.9 s
Text vergleichen = 0.4 s
nach Zeilennummern sortieren = 2.1 s (originale Reihenfolge wiederherstellen)

Wenn sortierte Ergebnisse gebraucht werden, läßt man man das zweite Sortieren einfach weg.