Komplexeres? schnelles durchsuchen größerer Arrays

abc-user

Guten Tag,

ich habe 2 Arrays mit jeweils knapp 20.000 Werten die überprüft werden.
Das heißt, ich gucke im Moment mit _ArraySearch nach, ob der Wert in Array1 auch in Array2 vorhanden ist.
Dieser Vorgang dauert allerdings recht lange bei mir.. daher habe ich überlegt, wie man das abkürzen könnte.

Meine Idee wäre es - man könnte ja Strings miteinander vergleichen, das ginge viel schneller.
Also beispielweise man fügt die ersten 100 Arrays zu einem String zusammen und vergleicht dann diese 200 Strings miteinander.

Spoiler anzeigen

[autoit]

For $i = 0 To StringLen($StringNew) step 1000
$StringShortNew = stringMid($StringNew,$i,$i+1000)
$StringShortOld = stringMid($StringOld,$i,$i+1000)

if StringCompare($StringShortNew,$StringShortOld,2) <> 0 then ; Wenn ungleich lang
consolewrite("Ungleich"&@CRLF)
Else ; wenn gleich lang
consolewrite("Gleich"&@CRLF)
endif

Next

[/autoit]

Das geht nun aber leider nicht so einfach.. die Arrays sind alphabetisch geordnet und wenn ein neuer Artikel hinzukommt oder abgeht,
verschiebt sich ja alles.

Also habe ich überlegt, dass man es ungefähr wie folgt umsetzen müsste:
Packe die ersten 100 Werte beider Arrays jeweils in einen String - wenn gleich, ok - und die nächsten 100 checken.
Wenn nicht ok, - also StringCompare sagt,dass ein String in die eine oder andere Richtung größer ist - dann müsste er es
nach diesem Fall hin ja überprüfen.. also wenn diesem Teilabschnitt das "linke" Array größer als das "rechte" ist - dann müssen ja
alle Elemte des rechten auf's Vorhandensein im linken überprüft werden - durch "ArraySearch" würde ich dann sagen.

Wenn nun aber feststeht, dass mindestens? ein Element nicht vorhanden ist - muss im 2. Durchlauf für die nächsten 100 zusammengefassten Arrays ja etwas verändert werden.. aber irgendwie weiß ich nicht genau wie - oder habe ich einen Denkfehler?

Zu komplex? Falscher Ansatz? Würd mich freuen, wenn jemand die Zeit findet, kurz darüber nachzudenken!
Ich steh wohl ein wenig auf'm Schlauch

Beste Grüße

name22

Es würde vielleicht schneller gehen 2 Strings zu vergleichen, aber das wird durch die zum Umwandeln der Arrays in Strings benötigte Zeit zunichte gemacht ;).
Es gibt aber bestimmt eine Möglichkeit das zu beschleunigen, ich kenne sie leider nur nicht.

**Oscar**

Ich denke, Du solltest einen anderen Ansatz wählen. Vergleiche sind mit einem Scripting.Dictionary-Object rasend schnell.
Falls Du diesbezüglich Hilfe benötigst, wäre aber eine genauere Erklärung zum Datenbestand nötig.

**Andy**

AspirinJunkie hat mal Alternativen zum Array zusammengestellt:
Alternativen zum Array

abc-user

Hallo,

es handelt sich dabei um den Vergleich von alter und neuer Produktlisten.

Sie liegen als Textdatei vor - in der in jeder Zeile ein Produkt alphabetisch sortiert liegt.
Das ganze bringe ich dann per Stringsplit(String,@CR) in eine Arrayform.

Ein Beispiel wäre

Ist der Datenbestand so genau genug erklärt?

Vielen Dank im voraus,

EDIT:
Es ist aber wahrscheinlicher, dass kein neuer Artikel an diese Stelle tritt, das wäre halt schon ein großer Zufall bei rund 20.000 Artikeln - es wäre aber halt möglich.. es wäre wohl eher der Fall, dass der Artikel "10 000 Mammoth read" dann nach oben rutschen würde.. wobei das bei einem Vergleich ja wieder egal wäre.. Ich bin gespannt, wie viel schneller das mit dem Dictionary.Object gehen würde..

progandy

Eine Frage hätte ich: Woher kommen die Textdateien denn?

**bernd670**

Hallo,

kannst du vllt. noch erklären was als Ergebnis rauskommen soll?
Soll es eine Liste mit den Änderungen sein?
Mußt du nur wissen ob sich was geändert hat, um die neue Liste einzulesen?

abc-user

Um genau zu sein:

Es handelt sich um eine Art Marktforschungsprogramm.
Ich möchte feststellen was meine Mitbewerber verkaufen - das stelle ich durch das Onlineangebot fest.
Durch winhttp erfasse ich den Quelltext und extrahiere daraus den Bestand - daraus entsteht dann eine Liste mit Artikeln.

Mich interessiert in erster Linie welche Produkte verkauft worden sind - aber welche hinzugekommen sind,
ist natürlich auch interessant! D.h. welche Produkte, die vorher in der "alten" Liste vorhanden waren - in der "neuen"
Liste es nicht mehr sind. Mein Ansatz mi dem "ArraySearch" funktioniert zwar - aber warum 5 Minuten warten, wenn es wahrscheinlich
auch innerhalb von einer Minute gehen könnte?

**BugFix**

Wenn du die Daten in Textdateien vorliegen hast, vergleiche doch einfach mit WinMerge.

progandy

Stimmt, WinMerge oder ein anderes Diff-Programm ist die beste Wahl (das ist einfacher, als das Diff komplett in Autoit zu erstellen)
Eine alternative wäre, die Daten in einer SQLite-Datenbank zu sammeln statt in Text-Dateien und dann per SQL-Kommandos die Daten zu auszuwerten.

Edit: Für Diff wäre das interessant:
http://neil.fraser.name/writing/diff/
http://src.opensolaris.org/source/xref/on…cmd/diff/diff.c

**peethebee**

Die Wahl des Algorithmus macht oft sehr viel aus:

Zitat von abc-User

die Arrays sind alphabetisch geordnet

Dann ist eine Suche mit Interpolationssucheoder Quadratischer Binärsuche rasend schnell. Bei 20.000 Objekten sollten da keine weit weniger als ein halbes Dutzend Vergleiche nötig sein. Fertig gibt es das für AutoIt glaube ich nicht, aber Wikipedia liefert bei der Interpolationssuche Pseudocode :).

Johannes

abc-user

Hallo und danke für die zahlreichen Antworten!

Ich habe Winmerge so in Erinnerung, dass es nur Zeile für Zeile vergleicht? Das wäre aber nicht meine Absicht!
Und selbst wenn es nicht Zeilenabhängig vergleicht ( wie eigentlich sonst?) müsste ich dann die 20.000 Zeilen einmal abscroolen
um die roten Stellen herauszufischen ? Das kann doch nicht der Sinn einer Automatisierung sein..

Der Ansatz von PeeTheBee klingt interessant - sollte ich das einmal so umsetzen melde ich mich nocheinmal!
Bis dahin danke!

progandy

@abc-user: WinMerge sollte eigentlich eingefügte zeilen und gelöschte Zeilen erkennen. Aus dem Ergebnis lässt isch dann eine Patch-Datei im gewünschten Format erstellen. (Wenn das nicht ausreicht, kannst du die Patchdatei nachträglich mit AutoIt formatieren)

Edit: Die DiffUtils lassen sich per Commandline bedienen und haben sofort eine verarbeitbare Ausgabe:
http://gnuwin32.sourceforge.net/packages/diffutils.htm

Ausgabe z.B.:

Spoiler anzeigen

Code

D:\Downloads\diff>diff -w -B --normal  smiley.txt sm
10a11
> #-)        Oh, what a night!
17,19d17
< 8-)        User is wearing sunglasses.
< :'-(       User is crying.
< :'-)       User is so happy, s/he is crying.
50,52d47
< }:-(       Toupee in an updraft.
< B-)        User wears horn-rimmed glasses.
< :-{}       User wears lipstick.
108d102
< :-`        User spitting out its chewing tobacco.
188a183
> ~~:-[      Net Flame.
191,192c186
< 3:[        Mean Pet Toy smiley.
< ...        Something else.
---
> 3:[        Mean Pet smiley.
199a194
> C=:-)      User is a chef.
202c197
< E-:-)      User is a fgfg Ham radio operator.
---
> E-:-)      User is a Ham radio operator.

Alles anzeigen

Zeilen mit > gibt es nur in smiley2.txt, Zeilen mit < nur in Smiley.txt (das ist jeweils eine bearbeitete Datei von http://piology.org/smiley.txt )
Die restlichen Zeilen sind dazu da, die Ausgabe zu formatieren (Einordnung der Zeilen in die Datei, Trennung zwischen hinzugefügt, gelöscht)
Veränderungen in einer Zeile (Hinzufügen oder löschen eines Wortes) werden als entfernen einer Zeile und hinzufügen einer neuen registriert.

abc-user

@progandy

ah, wenn das so ist - werde ich das mal ausprobieren! Vielen Dank!
Aber ich guck heute und morgen mal - ob ich die Interpolationssuche nachvollziehen und als Funktion bauen kann..
Das ist doch mal ne nette Aufgabe!

abc-user

Sodle - mit Zahlen funktioniert das soweit ganz gut, habe das JavaBeispiel einfach AutoIt umgebaut.

Spoiler anzeigen

[autoit]

Dim $aArray[1]
for $i = 1 to 20000
_arrayAdd($aArray,$i)
next

[/autoit] [autoit][/autoit] [autoit]

$anfang = Timerinit()
$index = _interpolationSearch($aArray,"18000")
$ende = Timerdiff($anfang)
ConsoleWrite($ende&' '&$aArray[$index]&@CRLF)

[/autoit] [autoit][/autoit] [autoit]

$anfang = Timerinit()
$index = _arraysearch($aArray,"18000")
$ende = Timerdiff($anfang)
ConsoleWrite($ende&' '&$aArray[$index]&@CRLF)

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

Func _interpolationSearch($array, $value)

[/autoit] [autoit][/autoit] [autoit]

;Returns index of toFind in sortedArray, or -1 if not found
Local $low = 1;
Local $high = UBound($array)-1
Local $mid

[/autoit] [autoit][/autoit] [autoit]

While $array[$low] <= $value and $array[$high] >= $value
$mid = $low + (($value - $array[$low]) * ($high - $low)) / ($array[$high] - $array[$low]);
;MsgBox(1,1,$mid)

[/autoit] [autoit][/autoit] [autoit]

if $array[$mid] < $value Then
$low = $mid + 1;
Elseif $array[$mid] > $value then
$high = $mid - 1;
Else
Return int($mid);
EndIf
WEnd

[/autoit] [autoit][/autoit] [autoit][/autoit] [autoit]

If $array[$low] == $value Then
Return $low;
Else
Return -1; // Not found
EndIf

[/autoit] [autoit][/autoit] [autoit]

EndFunc ;==>_interpolationSearch

[/autoit]

Suchezeit bei 20.000 Einträgen nach dem 18.000 Element
mit _arraysearch: 70.83 ms
mit _interpolationSearch: 0.10 ms

Na ja, jetzt muss das nur noch für Strings funktionieren.. kann man einen String in eine Zahl umwandeln oder gibt es eine Funktion die auswirft welcher String alphabetisch "eher/größer" ist? Ansonsten würde mir nur einfallen, eine Funktion zu erstellen die aus einem String
je nach Buchstabe/Ziffer daraus eine Zahl erstellt.. also z.B. aus "1Abba" würde dann etwas wie "01 10 11 11 10" werden.. oder blöde Idee?

Beste Grüße!

name22

Vielleicht mit Befehlen wie

[autoit]

Binary
;oder
Chr

[/autoit]

Aber alle 20.000 Einträge in deinem Array so umzuwandeln würde möglicherweise auch einige Zeit in Anspruch nehmen...

**autoBert**

Hallo abc user,

die Verglichsoperatoren <, <=, >, >=, = und == funktionieren auch mit Strings, einzig bei = must du beachten dass hier nicht auf Gross- Kleinschreibung geachtet wird,

mgf autoBert

Großvater

Hallo,

wenn Dein Array im Sinne der Vergleichsoperatoren wirklich korrekt sortiert ist, würde Dir auch schon _ArrayBinarySearch() ein gutes Stück weiterhelfen:

Spoiler anzeigen

[autoit]

#include <Array.au3>

[/autoit] [autoit][/autoit] [autoit]

$String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
$aString = StringSplit($String, "", 2)
$Len = StringLen($String)
$sString = ""

[/autoit] [autoit][/autoit] [autoit]

Dim $aArray[$Len * $Len * $Len]
$Index = 0
For $I = 0 To $Len - 1
For $J = 0 To $Len -1
For $K = 0 To $Len - 1
$aArray[$Index] = $aString[$I] & $aString[$J] & $aString[$K]
$Index += 1
$sString &= $aString[$I] & $aString[$J] & $aString[$K] & @CRLF
Next
Next
Next

[/autoit] [autoit][/autoit] [autoit]

Dim $aFind[3] = ["ABC", "MMM", "ZAB"]

[/autoit] [autoit][/autoit] [autoit]

For $A = 0 To 2
ConsoleWrite(" >>>>>>>>>> Lauf " & ($A + 1) & " - gesucht wird " & $aFind[$A] & @CRLF)
$Start = Timerinit()
$Index = _ArraySearch($aArray, $aFind[$A])
$Dauer = Timerdiff($Start)
ConsoleWrite(" _ArraySearch: " & $Dauer & ' ' & $aArray[$Index] & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

$Start = Timerinit()
$Index = _ArrayBinarySearch($aArray, $aFind[$A])
$Dauer = Timerdiff($Start)
ConsoleWrite(" _ArrayBinarySearch: " & $Dauer & ' ' & $aArray[$Index] & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

$Start = Timerinit()
$Index = StringInStr(@CRLF & $sString, @CRLF & $aFind[$A] & @CRLF)
$Dauer = Timerdiff($Start)
ConsoleWrite(" StringInStr: " & $Dauer & ' ' & StringMid($sString, $Index, StringLen($aFind[$A])) & @CRLF)
Next
Exit

[/autoit]

Anmerkung 1: Die Funktion StringInStr() scheint nicht optimal umgesetzt zu sein.

Anmekung 2: @abc-user: Ich hoffe, Du erstellst die 20000er Arrays in Deinen echten Skripten nicht - wie in Deinem letzten Beispiel - per _ArrayAdd() !?!

**AspirinJunkie**

Zitat von Großvater

Anmerkung 1: Die Funktion StringInStr() scheint nicht optimal umgesetzt zu sein.

Warum?
Hast du auch mal beim CaseSense-Parameter eine 2 eingetragen?
Ansonsten sagen Einzelzeitmessungen nicht so viel aus da sie noch stark streuen.
Besser wäre es mehrere Durchgänge zu machen - dann sind die Ergebnisse auch aufschlussreicher:

Spoiler anzeigen

[autoit]

#include <Array.au3>

[/autoit] [autoit][/autoit] [autoit]

Global $N = 100

[/autoit] [autoit][/autoit] [autoit]

$String = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
$aString = StringSplit($String, "", 2)
$Len = StringLen($String)
$sString = ""

[/autoit] [autoit][/autoit] [autoit]

Dim $aArray[$Len * $Len * $Len]
$Index = 0
For $I = 0 To $Len - 1
For $J = 0 To $Len - 1
For $K = 0 To $Len - 1
$aArray[$Index] = $aString[$I] & $aString[$J] & $aString[$K]
$Index += 1
$sString &= $aString[$I] & $aString[$J] & $aString[$K] & @CRLF
Next
Next
Next

[/autoit] [autoit][/autoit] [autoit]

Dim $aFind[3] = ["ABC", "MMM", "ZAB"]

[/autoit] [autoit][/autoit] [autoit]

For $A = 0 To 2
ConsoleWrite(" >>>>>>>>>> Lauf " & ($A + 1) & " - gesucht wird " & $aFind[$A] & @CRLF)
$Start = TimerInit()
For $I = 1 To $N
$Index = _ArraySearch($aArray, $aFind[$A])
Next
$Dauer = TimerDiff($Start) / $N
ConsoleWrite(" _ArraySearch: " & $Dauer & ' ' & $aArray[$Index] & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

$Start = TimerInit()
For $I = 1 To $N
$Index = _ArrayBinarySearch($aArray, $aFind[$A])
Next
$Dauer = TimerDiff($Start) / $N
ConsoleWrite(" _ArrayBinarySearch: " & $Dauer & ' ' & $aArray[$Index] & @CRLF)

[/autoit] [autoit][/autoit] [autoit]

$Start = TimerInit()
For $I = 1 To $N
$Index = StringInStr(@CRLF & $sString, @CRLF & $aFind[$A] & @CRLF, 2)
Next
$Dauer = TimerDiff($Start) / $N
ConsoleWrite(" StringInStr: " & $Dauer & ' ' & StringMid($sString, $Index, StringLen($aFind[$A])) & @CRLF)
Next

[/autoit]

Großvater

[OT]

Zitat von AspirinJunkie

Warum?

Weil ich, wie schon gesagt, eine Zeit lang mit AutoHotkey geskriptet habe:

AHK

Code

#NoEnv
; Wenn die folgende Zeile "entkommentiert" wird, geht es noch schneller
; SetBatchLines, -1


DefaultCaseSense := "AHK" ; Oder auch "AU3"


Chars := "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
StringSplit, Chars, Chars
Len := StrLen(Chars)
String := "`r`n"


Loop, %Len% {
   I := A_Index
   Loop, %Len% {
      J := A_Index
      Loop, %Len% {
         K := A_Index
         String .= Chars%I% . Chars%J% . Chars%K% . "`r`n"
      }
   }
}


Find := "ZAB"


If (DefaultCaseSense = "AU3")
   StringCaseSense, Locale


OuterLoop := 5
InnerLoop := 200
Dauer := 0


Loop, %OuterLoop% {
   Sleep, 1000
   Start := A_TickCount
   Loop, %InnerLoop%
      Index := Instr(String, "`r`n" . Find . "`r`n")
   Dauer += A_TickCount - Start
}


Found := SubStr(String, Index + 2, StrLen(Find))
MsgBox, 0, AHK-Ergebnis:
      , % "Dauer (" . InnerLoop . " Durchläufe):  " . Round(Dauer / OuterLoop) . " ms - Treffer: " . Found


ExitApp

Alles anzeigen

AU3

[autoit]

$DefaultCaseSense = "AHK" ; oder auch "AU3"

[/autoit] [autoit][/autoit] [autoit]

$Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
$aChars = StringSplit($Chars, "", 2)
$Len = StringLen($Chars)
$String = @CRLF

[/autoit] [autoit][/autoit] [autoit]

For $I = 0 To $Len - 1
For $J = 0 To $Len -1
For $K = 0 To $Len - 1
$String &= $aChars[$I] & $aChars[$J] & $aChars[$K] & @CRLF
Next
Next
Next

[/autoit] [autoit][/autoit] [autoit]

$Find = "ZAB"

[/autoit] [autoit][/autoit] [autoit]

If $DefaultCaseSense = "AU3" Then
$CaseSense = 0
Else
$CaseSense = 2
EndIf

[/autoit] [autoit][/autoit] [autoit]

$OuterLoop = 5
$InnerLoop = 200
$Dauer = 0

[/autoit] [autoit][/autoit] [autoit]

For $C = 1 To $OuterLoop
Sleep(1000)
$Start = TimerInit()
For $I = 1 To $InnerLoop
$Index = StringInStr($String, @CRLF & $Find & @CRLF, $CaseSense)
Next
$Dauer += TimerDiff($Start)
Next

[/autoit] [autoit][/autoit] [autoit]

$Found = StringMid($String, $Index + 2, StringLen($Find))
MsgBox(0, "AU3-Ergebnis:", "Dauer (" & $InnerLoop & " Durchläufe): " & Round($Dauer / $OuterLoop) & " ms - Treffer: " & $Found)
Exit

[/autoit]

Ergebnisse:

Schlechtestes AHK Ergebnis bei 10 abwechselnd mit AU3 gestarteten Durchläufen: 156 ms
Bestes AU3 Ergebnis bei 10 abwechselnd mit AHK gestarteten Durchläufen: 1512 ms

Und dabei lief AHK noch mit leicht angezogener Handbremse. Manchmal träume ich davon, dass die besten Teile beider Interpreter (wieder) in einer Sprache vereint werden!

[/OT]