ubuntuusers.de

Hallo!

Ich habe ein Array von Strings, in dem ich alle doppelten Wörter löschen will und danach die Wörter der Länge nach sortiere.

Habe leider bis jetzt nur eine nicht sehr performante Funktion dafür, brauche darin ungefähr $(Anzahl_Wörter_nach_Löschen)^2 Schleifendurchläufe. Sortieren kann ich mit O(array.length * log (array.length) (unstable, nach jedem Kriterium oder O(array.length * log(array.length)^2) stable). Würde jetzt gerne das Löschen schneller machen, da ich für ein Array von ~29000 Wörtern schon ~ 35 Millionen Schleifendurchläufe brauche und es beim doppelten schon 4 mal so viel sind.

Immo sieht das ganze so aus:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//Erfordert d2
//Für alle, die dem D nicht mächtig sind inkl. Erklärungen :)

import std.algorithm : sort; //Fürs sortieren

//T steht für irgendeinen Typ (string)
T[] removeElement (T)(T[] array, int pos) {
    //operator~ : aneinanderhängen
    return array[0..pos] ~ array[pos+1..length];
}

T[] removeDouble(T)(T[] array) { 
    T[] result;
    while (array.length != 0) {
        //~= ist der Append - Operator, fügt result Element 0 aus array hinzu
        result ~= array[0];
        for (int i = 0; i < array.length;) {
            if (array[i] == result[length-1]) //length -1 ist das letzte Element
                //Gleich array = removeElement!(string)(array, i);
                //Ausrufezeichen braucht man (oben) für Templates
                array = array.removeElement (i); 
            else i++;
        }
    }
    return result;
}

int main () {
    string[] words;
    //Lese einen Text ein und splitte ihn in Wörter
    //...
    words = words.removeDouble (); //T ist jetzt string
    sort!("a.length > b.length")(words); //dmd Generiert aus dem String Code   
    //verarbeite weiter...
    return 0;
}

Ideen können ruhig in jeder Sprache sein, so lange man sie auf D/C/C++ übertragen kann ☺

Für alle, die sich Dmd 2 installieren wollen, habe ich noch ein kleines Script, das alles in die Ordner unter /usr/local/ installiert. (Eigendlich nur herunterladen, entpacken, kopieren und anpassen)

MfG
Yoschi

Yoschi schrieb:

Hallo!

Ich habe ein Array von Strings, in dem ich alle doppelten Wörter löschen will und danach die Wörter der Länge nach sortiere.

Habe leider bis jetzt nur eine nicht sehr performante Funktion dafür, brauche darin ungefähr $(Anzahl_Wörter_nach_Löschen)^2 Schleifendurchläufe. Sortieren kann ich mit O(array.length * log (array.length) (unstable, nach jedem Kriterium oder O(array.length * log(array.length)^2) stable). Würde jetzt gerne das Löschen schneller machen, da ich für ein Array von ~29000 Wörtern schon ~ 35 Millionen Schleifendurchläufe brauche und es beim doppelten schon 4 mal so viel sind.

Immo sieht das ganze so aus:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

//Erfordert d2 //Für alle, die dem D nicht mächtig sind inkl. Erklärungen :) import std.algorithm : sort; //Fürs sortieren //T steht für irgendeinen Typ (string) T[] removeElement (T)(T[] array, int pos) { //operator~ : aneinanderhängen return array[0..pos] ~ array[pos+1..length]; } T[] removeDouble(T)(T[] array) { T[] result; while (array.length != 0) { //~= ist der Append - Operator, fügt result Element 0 aus array hinzu result ~= array[0]; for (int i = 0; i < array.length;) { if (array[i] == result[length-1]) //length -1 ist das letzte Element //Gleich array = removeElement!(string)(array, i); //Ausrufezeichen braucht man (oben) für Templates array = array.removeElement (i); else i++; } } return result; } int main () { string[] words; //Lese einen Text ein und splitte ihn in Wörter //... words = words.removeDouble (); //T ist jetzt string sort!("a.length > b.length")(words); //dmd Generiert aus dem String Code //verarbeite weiter... return 0; }

Ideen können ruhig in jeder Sprache sein, so lange man sie auf D/C/C++ übertragen kann ☺

Für alle, die sich Dmd 2 installieren wollen, habe ich noch ein kleines Script, das alles in die Ordner unter /usr/local/ installiert. (Eigendlich nur herunterladen, entpacken, kopieren und anpassen)

MfG
Yoschi

Ich würde nur einmal sortieren mit einer Vergleichsfunktion, die primär auf Länge und sekundär lexikographisch vergleicht. Sortieren braucht im Average-Case O(n*log(n)). Danach reicht ein Durchlauf mit O(n) um die Dubletten zu finden.

Die Art und Weise, wie du Elemente aus dem Array löschst sieht nicht gesund aus:

return array[0..pos] ~ array[pos+1..length]

Ich bin kein D-Experte, aber für mich sieht das so aus, als ob bei jedem Löschen die beiden Restteile zu einem neuen Arrayobjekt zusammenkopiert werden.

Es dürfte schneller sein, ein neues Array zu belegen, anstatt das ursprüngliche Array zu verändern. Das Einfügen in ein Array hat in der Regel konstante Laufzeit (vor allem, wenn der interne Speicher entsprechend groß reserviert wird), während das Entfernen aufgrund der erforderlichen Kopieraktionen wohl eher lineare Laufzeit hat.

Ich persönlich würde einen unsortierten Mengentyp verwenden, um Duplikate zu eliminieren. Das Einfügen in eine Menge auf Basis einer Hashtabelle hat im Durchschnitt konstante Laufzeit, so dass die Duplikateliminierung in linearer Zeit läuft. Danach kann man die Menge dann sortieren, so dass die Gesamtkomplexität in O(n²*log n) liegen dürfte.

In Python wäre das übrigens trivial:

1

sorted(set(words), key=len)

Gibt es kein sorted Set in D? Oder geht es ums Selbermachen?

Werden die Wörter initial gesammelt und sortiert, oder kommen später weitere Wörter hinzu?

Wenn es ein einmaliger Vorgang ist, dann könnte man ja verschiedene Sammlungen gründen, getrennt nach Wortlänge. Kennt man vorab die statistischen Wortlängenhäufigkeiten, so kann man z.B. für kurze Wörter bis 3 Zeichen eine Sammlung bilden, für alle Zeichen von 4-12 Zeichen je eine Sammlung, und eine für längere Wörter.

Dies würde den zu durchsuchenden Raum etwa auf ein 10tel begrenzen, und der quadratische Effekt ist dann ein hundertstel. Nicht ganz - aber von der Tendenz.

Am Ende kann man ja immer noch ein Array draus machen, wenn man das wirklich benötigt.

Die Art und Weise, wie du Elemente aus dem Array löschst sieht nicht gesund aus:

return array[0..pos] ~ array[pos+1..length]

Ich bin kein D-Experte, aber für mich sieht das so aus, als ob bei jedem Löschen die beiden Restteile zu einem neuen Arrayobjekt zusammenkopiert werden.

Ja, da hast du ganz Recht... ☺

Ich würde nur einmal sortieren mit einer Vergleichsfunktion, die primär auf Länge und sekundär >lexikographisch vergleicht. Sortieren braucht im Average-Case O(n*log(n)). Danach reicht ein Durchlauf mit >O(n) um die Dubletten zu finden.

Sortiere ich 2 mal ❓

So vieleicht:

1
2
3
4
5
6

//Statt Strings kann man auch Delegates verwenden
sort!(delegate bool (string a, string b) {
    if (a.length > b.length) return true;
    else if (a.length == b.length) return a < b; //erst "a", dann "b", …
    else return false;
})(words);

@user unknown: Dem Programm werden Dateipfade übergeben, von denen er dann die Wörter einließt und alle doppelten löscht. Nach dem einlesen kommen keine mehr hinzu, es werden nur noch welche gelöscht oder Teil - Bereiche des Arrays verwendet.

@Lunar: wo genau?

@Yoschi: Wie "wo genau"? Bezieht sich das auf den ersten Absatz meines Beitrags? Was ist daran schwierig zu verstehen? Statt das übergebene Array zu manipulieren, solltest Du ein neues Array anlegen, und im Laufe der Duplikateliminierung eindeutige Elemente in dieses Array kopieren, anstatt doppelte Elemente aus dem ursprünglichen Array zu entfernen.

Lunar schrieb:

Es dürfte schneller sein, ein neues Array zu belegen, anstatt das ursprüngliche Array zu verändern.

Ja, das Vorsortieren nach Länge und Alphabet würde ich im ursprünglichen Array machen, und danach ein zweites Array aufmachen in dem dann nacheinander die Nicht-Dubletten übertragen werden.

Das Einfügen in ein Array hat in der Regel konstante Laufzeit (vor allem, wenn der interne Speicher entsprechend groß reserviert wird), während das Entfernen aufgrund der erforderlichen Kopieraktionen wohl eher lineare Laufzeit hat.

Zu klein werdende Arrays werden daher in der Regel mit Zweierpotenz-Größen realloziert, D wird das wohl auch so machen.

Ich persönlich würde einen unsortierten Mengentyp verwenden, um Duplikate zu eliminieren. Das Einfügen in eine Menge auf Basis einer Hashtabelle hat im Durchschnitt konstante Laufzeit, so dass die Duplikateliminierung in linearer Zeit läuft. Danach kann man die Menge dann sortieren, so dass die Gesamtkomplexität in O(n²*log n) liegen dürfte.

Das ist auch gut.

Yoschi schrieb:

Ich würde nur einmal sortieren mit einer Vergleichsfunktion, die primär auf Länge und sekundär >lexikographisch vergleicht. Sortieren braucht im Average-Case O(n*log(n)). Danach reicht ein Durchlauf mit >O(n) um die Dubletten zu finden.

Sortiere ich 2 mal ❓

Ne, das geht in einem Rutsch.

So vieleicht:

1 2 3 4 5 6

//Statt Strings kann man auch Delegates verwenden sort!(delegate bool (string a, string b) { if (a.length > b.length) return true; else if (a.length == b.length) return a < b; //erst "a", dann "b", … else return false; })(words);

Ja, genau so!

Danach ist das Dubletten rausfiltern ja einfach ⇒ O(n).

In D müsste man das eigentlich, zumindest auf Ebene des Quelltextes, mit einem einzigen Array machen können. Dieses wie YEPEHNAS beschrieben hat, sortieren und die Doubletten dann "in place" entfernen und am Ende die Länge des Arrays entsprechend nach unten korrigieren. Ob dann intern dabei das Array kopiert wird, am Ende des Arrays einfach nur Speicher freigegeben wird, oder nichts weiter passiert weil kein oder nur wenig Platz verschwendet wird, hängt von der Implementierung von D-Arrays ab.

Habe die removeDouble Funktion jetzt so:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import std.algorithm : uniq;

//Benötigt ein sortiertes Array
T[] removeDouble (T)(T[] array) {
    T[] result;
    //Die Struktur, die uniq zurückgibt, überspringt doppelte Elemente
    auto it = uniq!("a == b")(array);
    while (!it.empty) {
        result ~= it.front ();
        it.popFront ();
    }
    return result;
}

Danke für eure Hilfe, ist jetzt deutlich schneller und ich denke auch linear. 👍

MfG
Yoschi

YEPEHNAS schrieb:

Ich würde nur einmal sortieren mit einer Vergleichsfunktion, die primär auf Länge und sekundär lexikographisch vergleicht.

Ich hatte den Eindruck, daß lexikographisch (lexigraphisch?) gar nicht sortiert werden soll (sondern stabil/instabil).

Yoschi schrieb:

@user unknown: Dem Programm werden Dateipfade übergeben, von denen er dann die Wörter einließt und alle doppelten löscht. Nach dem einlesen kommen keine mehr hinzu, es werden nur noch welche gelöscht oder Teil - Bereiche des Arrays verwendet.

Um ein doppeltes Wort zu löschen muß es ja gefunden werden. Gefunden werden kann in einer sortierten Sammlung viel leichter. Daher würde ich dazu tendieren doppelte Elemente beim Lesen gar nicht erst aufzunehmen, und was ich aufnehme gleich an die richtige Stelle zu stecken. So wird jedes Element nur einmal angefaßt.

Hier ein Scala-Democode (working) im Python-Layout (was wäre besser geeignet?), der aber am Ende kein Array erzeugt wie gefordert, sondern das Ergebnis ausgibt.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import scala.collection.mutable._

object LenBucket {
  var lili = for (i <- (1 to 12).force)
          yield new ListBuffer [String] ()
  
  def add (s: String) {
    val l = s.length
    if (l >= 10) {
      if (! lili(10).contains (s)) 
        lili(10) += s 
    } else
      if (! lili (l).contains (s)) 
        lili (l) += s
  }
  
  def show () {
    lili.map (println (_))
  }
}

import java.io.File 

object WordlenSort {
	def main (args: Array[String]) : Unit = {
		val sample = "/opt/mini/xorg-edit-08.08.06/COPYING"
		val sc = new java.util.Scanner (new File (sample))
		val lb = LenBucket
		while (sc.hasNext ())
			lb.add (sc.next ())
		lb.show 
	}
}

Als Beispieltext fand ich nur eine der vielen Lizenzen zum testen, welche aus rd. 5600 Wörtern besteht, davon ca. 1550 unterschiedliche. Auf meiner Raketenmaschine (1.6 Ghz) ist der Job in 1 sec. erledigt:

ibmux:~/proj/mini/forum > wc copying.sorted 
   13  1561 14445 copying.sorted
ibmux:~/proj/mini/forum > wc /opt/mini/xorg-edit-08.08.06/COPYING
  674  5644 35147 /opt/mini/xorg-edit-08.08.06/COPYING

Mit einem leicht längeren Text

wc adele.txt 
   8071  304147 2098378 adele.txt

beschäftigt sich mein Programm schon 2 Minuten.

Setze ich dann aber die Maximale Wortlänge von 12 auf 20, so sinkt die Verarbeitungsdauer auf 1 Minute, und sage ich dem Scanner, daß Komma, Punkt usw. nicht zum Wort zählt:

1

	sc.useDelimiter ("[ \\n\\r,.;:\"'!?()-]");

so sinkt die Verarbeitungszeit auf unter 30s, als Ergebnis bleibt:

wc adele.sorted 
    20  28434 365361 adele.sorted

Das Sortierkriterium kann man so natürlich nicht erst zur Laufzeit übergeben, wenn das ein wichtiger Punkt sein sollte.

Ob die Wörter auch lexigraphisch sortiert sind oder nicht, ist egal, genauso wie lang die Wörter dann eigendlich sind. d-sort kann man auch nicht zur laufzeit einen String mit der Sortierregel übergeben.

Wieder mal D Code, working

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

//Verwende lange import Zeilen, ka. warum :)
import std.stdio : writeln;
import std.file : readText;
import std.date : benchmark;
import std.algorithm : sort, uniq;
import std.string : lowercase, tolower, split;

//Lösche doppelte Elemente in einem Array
//Benötigt sortiertes Array
T[] removeDouble (T)(T[] array) {
	T[] result;
	auto it = uniq!("a == b")(array);
	while (!it.empty) {
		result ~= it.front;
		it.popFront;
	}
	return result;
}

void main (string[] args) {

	string[] words, uniq_words;
	foreach (i, arg; args[1..$]) {
		//Funktion für das Benchmark
		void func () {
			words = readText (arg).tolower().split ();
			sort!("a.length > b.length || (a.length == b.length && a < b)")(words);
			uniq_words = words.removeDouble ();
		}
		//Time ist vom Typ int[1u]
		auto time = benchmark!(func)(1);

		writeln ("Datei ", i+1, ": W\&ouml;rter gesamt: ", words.length, "; einzigartige:",
                         uniq_words.length, "; Zeit: ", time[0], " ms");
	}
}

Ausgaben (dmd Flags zur Optimierung; Lappi: 1,6 GHz Atom):

$> dmd -O -inline -release -run test.d alice_adventures_in_wonderland.txt gpl-3.0.txt
Datei 1: Wörter gesamt: 29459; einzigartige: 5578; Zeit: 73 ms
Datei 2: Wörter gesamt: 5644; einzigartige: 1384; Zeit: 11 ms

Dann bekomme ich mit uniq_words ein vernünftiges ergebnis geliefert. Größere Dateien hatte ich leider nicht im Angebot. Wenn ich meinem Programm sage, dass er beliebige Satzzeichen auch als Worttrenner verwenden soll, verdoppelt sich die Zeit.

readText() sollte außerhalb der gemessenen Funktion liegen, ansonsten verzerrt die E/A-Latenz die Ergebnisse.