Array-Vergleich bei AutoIT

[Fireball89]

Hallo,

ich brauche ein Programm was 2 txt-Dateien einliest, jede Zeile als Array-Element speichert und dann vergleicht. Anschliessend kommt wieder eine txt-Datei heraus mit den den Zeilen aus den beiden Dateien, allerdings ohne Doppelte.

Hier gehts mir nur um den Array-Vergleich.

Func joinArrays($arr1, $arr2)
	$i=0
	$k=0
	$doppelte=0
	Local $arr [16777111]
	ProgressOn("Programmstatus", "Fortschritt","", IniRead("config.ini", "Global", "winx", "600"), IniRead("config.ini", "Global", "winy", "400"),16)
	While ($k<UBound($arr1))
		ProgressSet( ($k/UBound($arr1)*100), "Teil 1 - Doppelte: "&$doppelte&" - Position: "&$k)
		$vorhanden=False
		$u=0
		While ($u<UBound($arr2))
			If $arr1[$k] = $arr2[$u] Then 
				$vorhanden=True
				ExitLoop
			EndIf
			$u+=1
		WEnd
		If ($vorhanden=False) Then
			$arr[$i] = $arr1[$k]
			$i+=1
		Else
			$doppelte+=1
		EndIf
		$k+=1
	WEnd
	$u=0
	While ($u < UBound($arr2))
		ProgressSet( ($u/UBound($arr2)*100), "Teil 2 - Liste anfügen")
		$arr[$i]=$arr2[$u]
		$i+=1
		$u+=1
	WEnd
	ReDim $arr[$i]
	Return $arr
EndFunc

Das Problem an der Sache ist, selbst wenn ich das ganze mit 4 Threads auf meinem Phenom II X4 955 laufen lasse (d.h. das programm 4 mal starten, 8 txt-Dateien werden verarbeitet), braucht man für das Zusammenführen von 2 Arrays mit je 80.000 fast 6 Stunden.
Kann man da noch was optimieren?
Falls nein, will ich gerne, dass AutoIT die Arrays an ein CUDA-Programm übergibt, ist das möglich? Ich denke meine GPU würde das schneller hinbekommen.

 

[1668mib]

Eventuell könnte eine "richtige" Programmiersprache bessere Leistung erbringen...

CUDA würde hier glaub ich allerdings rein gar nichts bringen... vielleicht solltest du dich einfach mal über CUDA informieren.

Welche Ansprüche hast du denn an das Ergebnis, muss das irgendwie sortiert sein? Sind die Eingangsdateien irgendwie soritert? Wie soll die Struktur sein?

 

[DonnyDepp]

Du gehst das Array immer Linear durch. Adaptier doch mal den Quicksort-Algorithmus, damit würde der Aufwand deutlich sinken.
Ausserdem kannst die 4 Kerne durch optimierten Code selber anpassen.
http://www.autoit.de/index.php?page=Thread&threadID=5738
Einzelne Threads starten sollte ja laut dem Thread da gehen.


Oder benutz anstatt Arrays Listen. Und wenn du ein doppeltes Element gefunden hast, nimmste das aus der Suchliste raus.
Macht bei 80k Einträgen schon einen Unterschied.

 

[Fireball89]

ja, also das wäre schon möglich. Ich kann sonst noch Java. Aber ich weiss nicht ob das wirklich schneller ist als AutoIT.

Sortiert ist bislang noch nichts. Würde das denn was bringen?
Also ich bring jetzt mal ein Beispiel für meine TXT-Dateien:

Eingabe1

HANS
MARKUS
LINDA
BERT
PETER

Eingabe2

HERBERT
PETER
SUSANNE
ELISABETH
GISELA

Ausgabe

HANS
MARKUS
LINDA
BERT
HERBERT
PETER
SUSANNE
ELISABETH
GISELA

D.h. die Eingabe-Arrays enthalten bereits nur einzigartige Elemente. Und das soll eben in der Ausgabe auch so sein. Jedes Element der Ausgabe darf nur einmal vorkommen.
Alles andere ist egal.

Ergänzung (29. November 2009)

@DonnyDepp:
Wie meinst du das? Also Quicksort haben wir nur einmal kurz in der Schule gemacht, bin ich leider nicht wirklich fit drin. Und ich die Ausgabe muss ja sowieso nicht sortiert sein. Falls du noch ne Idee hast, kannst du ja mal ne Art Pseudo-Code posten.

 

[Woey]

… 6 Stunden um 2 Textdateien ohne Redundanzen zusammen zu führen (wie groß sind die Dateien? 0,5-2MB?) – das ist wirklich miserabel!
Du solltest die Sache in Java angehen - würde mal behaupten, dass man selbst in hier die Ausführungszeit auf wenige Sekunden reduzieren kann (besonders angesichts deines Computers).

 

[ownagi]

oder schreib nen php-script und mach ne exe draus ...

am besten einfach mit assoziativen arrays arbeiten wobei der value als key gesetzt wird
so ueberschreibst die doppelten einträge dann einfach

nen sort drauf, array imploden und mit file_put_contents wegschreiben, isn 10-zeiler

 

[1668mib]

Also wenn die Reihenfolge absolut keine Rolle spielt ist ein Quicksort drüber vor dem Vergleich das beste...
und dann könnte man die Arrays mit zwei Zählern durchgehen
durch die Sortierung hat man ja einiges an Wissen
Beispiel

ANTON    ANTON
ARTHUR
         FRANZ
GUSTAV   GUSTAV
HANS
         JAN
PETER    PETER

also man hat für beide Arrays ne Index-Variable (z.B. i, j) und fängt bei beiden mit 0 an
man vergleicht
ar1 mit ar2[j]
sind beide gleich wandert der Wert in die Zieldatei und i und j werden um je 1 erhöht...
ansonsten schaut man eben ob
- ar1 "kleiner" ist als ar2[j] wenn ja wandern alle werte aus ar1 in die Datei bis man eben den Wert von ar2[j] erreicht oder "überschritten" hat
- ar "größer" als ar2[j] läufts halt genau andersrum...
Ka wie effizient das ist...

@ownagi: statt assoziativen Arrays wäre es vielleicht besser gleich spezeille PHP-Array-Funktionen zu nutzen... Wobei ich glaube auch PHP wird aus Performance-Sicht keinen Blumentopf gewinnen können... ob EXE oder nicht ist hier nicht mal so entscheidend... die dürften effizienter arbeiten

 

[Fireball89]

nen sort drauf, array imploden und mit file_put_contents wegschreiben, isn 10-zeiler

sry, *nixpeil*^^

Habs glaub ich net so drauf wie ihr. Wenns wirklich so schnell geht, kannst du mir das Ding vielleicht schreiben?
Also das komplette Prog läuft so:

irgendwelche txt-Dateien aus einem bestimmten Ordner nehmen
Txt-Datei 1 -> Array 1
Txt-Datei 2 -> Array 2
txt-Dateien in .txt.old umbennen
Beide Arrays zusammenfügen und das resultierende Arrays in eine neue Txt schreiben.

In dem Ordner befinden sich wirklich nur .txt und .txt.old Dateien.

@Woey:
Das ganze einfach in nach Java portieren und den kompletten Algorithmus so lassen?
Ich probiers mal.

 

[Woey]

Mein sehr simpler Vorschlag währe:

Zuerst liest du die Textdateien als string array ein. Danach legst du ein weiteres string array an, dass genau so groß ist, wie die beiden anderen zusammen. Dies dient als Puffer und wird später in die Ausgabedatei geschrieben. Nun gehst du durch beide eingelesenen arrays (nacheinander) und schreibst die Einträge in den Puffer. Zum überprüfen auf Redundanz vergleichst du immer das aktuelle Element mit allen die sich schon im Puffer befinden.

 

[1668mib]

@Woey: Das ist total ineffizient...
Man muss beide Arrays zigfach abgrasen ...


Edit:
Hier mal mein C#-Code, ka ob der effizient ist :-)

 static void Main(string[] args)
        {
            string[] ar1 = { "ANTON", "ARTHUR", "GUSTAV", "HANS", "PETER" };
            string[] ar2 = { "ANTON", "FRANZ", "GUSTAV", "JAN", "PETER", "ZUSEL" };

            int i = 0;
            int j = 0;

            while (i < ar1.Length || j < ar2.Length)
            {
                if (ar1[i] == ar2[j])
                {
                    Console.WriteLine(ar1[i]);
                    i++;
                    j++;
                } else if (ar1[i].CompareTo(ar2[j]) < 0)
                {
                    while ((i < ar1.Length) && (ar1[i].CompareTo(ar2[j]) < 0))
                    {
                        Console.WriteLine(ar1[i]);
                        i++;
                    }
                }
                else // ar2[j].CompareTo(ar1[i]) < 0
                {
                    while ((j < ar2.Length) && (ar2[j].CompareTo(ar1[i]) < 0))
                    {
                        Console.WriteLine(ar2[j]);
                        j++;
                    }
                }

                if (i == ar1.Length)
                {
                    while (j < ar2.Length)
                    {
                        Console.WriteLine(ar2[j]);
                        j++;
                    }
                }

                if (j == ar2.Length)
                {
                    while (i < ar1.Length)
                    {
                        Console.WriteLine(ar1[i]);
                        i++;
                    }
                }
            }

            Console.WriteLine("--Ende--");
            Console.ReadLine();
        }

Statt Console.Writeline() natürlich in die Ziel-Datei schreiben...

 

[Woey]

1668mib,

effizient ist es sicherlich nicht, aber ob es gravierend ineffizienter als dein Vorschlag ist mag ich bezweifeln: Bei meine Vorschlag wird ausschließlich der Puffer x-mal durchlaufen (x= Anzahl aller Elemente des Quell-arrays). Zudem ist der Puffer zu Anfang noch sehr klein und wächst nur mit der Anzahl der nicht redundanten Elemente. Bei deinem Vorschlag müssen zuerst beide Arrays (Eingabedateien) vorsortiert werden, was doch einigen Mehraufwand mit sich bringt.
Möcht mich jetzt aber auch nicht zu weit aus dem Fenster lehnen, ohne irgend welche Tests angestellt zu haben ... Das könnte ja mal der Themenersteller machen .

 

[Fireball89]

sry, aber was soll ich den jetzt wieder mit C#? Ich hab weder ne Ahnung wie man das kompiliert, noch kann ich das Script anpassen.
Ich finds ja nett, dass ihr mir helfen wollt, aber ich hab davon echt keine Ahnung, also wärs gut, wenn ihr entweder n fertiges Programm gebt, oder mir n Pseudo- oder Java-Code postet.
Damit kann ich was anfangen. Alles andere ist nur unnötige Mühe.

//edit:
Ich krieg im Moment noch net mal meinen eigenen Code nach Java portiert. Deswegen siehts mit Testen eher schlecht aus.

Ergänzung (29. November 2009)

Intel Atom beats Phenom II x4 955
bei 40000er Arrays braucht mein Netbook mit dem Java-Programm unter 1min!
Vergleich: Desktop-Rechner braucht mit AutoIT-Script dafür 1,5 Std!
Kann mir mal einer auf die Sprünge helfen, wie ich in Java Dateien einlesen? Habs jetzt erstmal mit Zufallstrings gemacht.

Ergänzung (29. November 2009)

muss man für BufferedReader und FileReader noch irgendwelche Bibliotheken importieren?

public static void blaa()
{
BufferedReader in = new BufferedReader(new FileReader("Textdatei.txt"));
String str;
while((str=in.readLine())!=null) System.out.println(str);
in.close;
}

Das sollte doch funzen ... aber der Compiler meint nur "in.close" -> not a statement

 

[Woey]

Das sollte doch funzen ... aber der Compiler meint nur "in.close" -> not a statement

Fehlen da vieleicht Klammern: in.close() ?

 

[1668mib]

"Zum überprüfen auf Redundanz vergleichst du immer das aktuelle Element mit allen die sich schon im Puffer befinden. " <-- das ist doch viel Aufwand... und Sortieralgorithmen sind nun mal auch nicht mehr sooo langsam... kannst ja mal wenn du Lust hast nen Vergleich machen mit sehr großen Arrays...

Und hab ja gleich gemeint, dass es sinnvoller sein wird, eine Programmiersprache zu nehmen, da kann man auch ineffizienten Code nehmen :-)

Und was du mit C# willst? Schon mal gemerkt dass sich Java und C# nun mal nicht grundlegend unterscheiden? Schon mal bemerkt, dass es weniger um den Code als viel mehr den Ansatz geht? Vor allem würde das fast 1:1 unter Java so laufen...

 

[ownagi]

ok, ausführliche erklärung meines vorschlags


1. assoziatives array erzeugen
2a. file einlesen (zeile für zeile) -> jede zeile in das array schreiben (nicht als value, sondern key)
2b. file einlesen (komplett) -> splitten (\r\n bzw. \n) und jedes element des splits in das array schreiben (key, nicht value)
3. für jedes file 2a bzw. 2b wiederholen
4a. jeden key aus dem array als zeile wegschreiben
4b. alle keys als string aneinanderhängen und wegschreiben


php code

$files = array("blub.txt", "bla.txt");
$entries = array();
foreach($files as $file) {
    $content = file_get_contents($file);
    $content = split("\r\n", $content);
    foreach($content as $c) {
        $entries[$c] = "";
    }
}
$output = "";
foreach(array_keys($entries) as $key) {
    $output .= $key."\r\n";
}
file_put_contents("output.txt", $output);

edit: könntest auch mit values arbeiten, weiss aber nicht wie sich das von der performance verhaelt, da du vor jedem insert nen "in_array()" machen müsstest

vermutlich ist das die bessere lösung, da arrays in php ohnehin IMMER assoziativ sind

 

[Fireball89]

public static ArrayList joinArrays(ArrayList arr1, ArrayList arr2)
	{
		long anfang = System.currentTimeMillis();
		long zeit;
		int doppelte=0;
		for (int i=0; i<arr2.size(); i++) {
			if (i%100==0) System.out.println((i*100/arr2.size())+" Prozent");
			if (!(arr1.contains(arr2.get(i)))) arr1.add(arr2.get(i));
			else doppelte++; }

		zeit = (System.currentTimeMillis() - anfang)/1000;
		System.out.println("Doppelte: "+doppelte+"\tDauer: "+zeit);
		return arr1;
	}

So hab ich das jetzt mal in Java gecoded. Gibts da Performance-technisch noch was zu verbessern?

 

[1668mib]

Klar gehts besser... aber ka ob meines das ist :-)
Die Dinger vorher sortieren mit nem QuickSort und dann parallel durchgehen wäre wohl effizienter... aber offensichtlich ist es ja zu schwer einen C#-Code in Java zu übertragen... wieso versuchst du nicht mal das hier

public static ArrayList joinArrays(ArrayList ar1, ArrayList ar2)
{
	long anfang = System.currentTimeMillis();
	long zeit;
	// hier ar1 mit Quicksort sortieren
	// hier ar2 mit Quciksort sortieren
	int i = 0;
	int j = 0;
	int doppelte = 0;

	while (i < ar1.size() || j < ar2size())
	{
		if (ar1.get(i) == ar2.get(j))
		{
			i++;
			j++;
			doppelte++;
                } else if (ar1.get(i).compareTo(ar2.get(j)) < 0) {
			while ((i < ar1.size()) && (ar1.get(i).compareTo(ar2.get(j)) < 0))
			{
				i++;
			}
		}
		else // ar2get(j).compareTo(ar1get(i)) < 0
		{
			while ((j < ar2.size()) && (ar2.get(j).compareTo(ar1.get(i)) < 0))
			{
				ar1.add(i, ar2.get(j));  // evtl i-1 statt i
				i++;
				j++;
			}
		}

		if (i == ar1.size())
                {
			while (j < ar2.size())
			{
				ar1.add(ar2.get(j));
				j++;
			}
		}

		if (j == ar2.size())
                {
			i = ar1.size();
		}
	}
	zeit = (System.currentTimeMillis() - anfang)/1000;
	System.out.println("Doppelte: "+doppelte+"\tDauer: "+zeit);
	return ar1;
}

QuickSort lässt sich ergooglen
Code ist ungetestet

 

[DonnyDepp]

machs wie ownagi vorgeschlagen hat.

in java benutzt du dafür einfach eine Map.

also:

map<string, string> daten;
for (int i=0; i<arr2.size(); i++) {
daten[arr2] = arr2;
}

und wenn du mal leerzeichen in der zeichenkette hast, ersetzt es einfach auf der linken seite.

 

[generalad]

machs wie ownagi vorgeschlagen hat.

in java benutzt du dafür einfach eine Map.

also:

map<string, string> daten;
for (int i=0; i<arr2.size(); i++) {
daten[arr2] = arr2;
}

und wenn du mal leerzeichen in der zeichenkette hast, ersetzt es einfach auf der linken seite.

Wieso gibst Du C++ Code an, wenn Du von Java redest? Oo

In Java funktioniert imho der Trick mit den Leerzeichen so nicht. Für C++ kann ich es spontan nicht sagen, bin aber sehr skeptisch.

Weiterhin

• Keine Map benutzen, wenn es ein Set tut - wie in diesem Fall.
• Map ist in Java ein Interface - HashMap bzw. HashSet wäre die richtige Klasse
• HashMap in Java ist einer C++ map in Sachen Performance weit überlegen - weil letztgenannte ein binärer Suchbaum ist.

Und ja, der Vorschlag von ownagi, speziell unter Verwendung eines assoziativen Containers, ist genau richtig.

Falls jemand die Variante mit Sortieren noch testen will - MergeSort findet sich in Java unter Collections#sort(List)

 

[lalas]

Mal eine blöde Frage;

Warum wird hier so ein Aufwand bezgl. String-Vergleich betrieben ?

Wenn ich den OP richtig lese, dann will er 2 Dateien zeilenweise vergleichen.

Warum also nicht die komplette Zeile als String ablegen und hinterher einfach vergleichen, z.B.:

pseudo-code:
if (zeile_links == zeile_rechts) then append $zeile_links an $AUSGABEFILE
else
append $zeile_links an $AUSGABEFILE
append $zeile_rechts an $AUSGABEFILE

Die meisten Programmiersprachen können ja mittlerweilen direkte Stringvergleiche und mit script-Sprachen sollte das auch kein Thema sein.
Mit Autoit kenne ich mich leider nicht aus, könnte sowas höchstens in bash bauen.