WordCount lernen

[Dirty Oerti]

Und ein Dirty Oerti, der mehr Wörter zählt als wir.

Er hat eine sehr scharfe Beschreibung von dem, was ein Wort ist.
Die Aufgabenstellung war Wörter in einem String zu zählen, die zwischen Leerzeichen sind, es ging nicht um Sätze und auch nicht um Zeilenwechsel. "Dies ist ein\nSatz." sind drei Worte: "Dies", "ist", "ein\nSatz."
Die einzigen Trennsymbole sind Stringanfang, Stringende ('\0') und das Leerzeichen.

Ich zähle "echte" Wörter, sprich der Algorithmus testet nicht nach Leerzeichen, sondern nach allen Zeichen, die NICHT in einem Wort vorkommen können.

Wenn ich das nur zu Leerzeichen ändere, dann braucht mein Code auf einmal aber DEUTLICH länger?
Kann mir das jemand erklären?! -,-

Von daher:

Kann man gerne ausprobieren, aber dafür brauchen wir noch eine eindeutige Methode, um die Performance zu testen. clock() ist nur ein Näherungswert und wenn zur Ausführung des Programms swappen muss, dann bringt das nicht mehr viel.

Was soll hier geschehen loliger:

Er entfernt führende Leerzeichen

Ich hab nix dagegen. Vlt können wir dann gemeinsam einen Algorithmus entwickeln, der an sich schneller ist.

Das halte ich für eine sehr gute Idee!

Ich habe jetzt das Problem so gelöst, dass jetzt sogar " Ich bin . " möglich ist:

Dann probiere jetzt doch mal:

Code: Alles auswählen

"    Ich  bin es"

Ok, das ist gemein ^^



Meine Überlegung war im Übrigen, auszunutzen, dass wir hier mit (min) 32 bit Rechnern arbeiten.
Allerdings hat mich das gestern schon so verwirrt, dass meine Variante, die nur noch 1 Vergleich hat (und ansonsten identisch ist) plötzlich viel langsamer ist als die Variante mit ... 4 .. ? Vergleichen, dass ich das erstmal hab ruhen lassen.
Problem daran ist ja auch, dass man entweder hoffen muss, nicht in einen Bereich zu kommen, aus dem man nicht lesen darf.
Oder man muss die Länge des Strings kennen, aber das kostet eben auch Zeit.

[cloidnerux]

Problem daran ist ja auch, dass man entweder hoffen muss, nicht in einen Bereich zu kommen, aus dem man nicht lesen darf.
Oder man muss die Länge des Strings kennen, aber das kostet eben auch Zeit.

Muss nicht, man sollte nur das Ende nicht verpassen.
Man könnte aber die API dahingehend erweitern, das übergeben wird, wie lang doch der String ist, bzw das man den String 2/4/6/8-Byte align anlegt und vorher mit '\0' füllt, sodass am Ende, sofern nicht schon 2X-Byte aligned das Ende bestimmt mit \0 gefüttert ist.
Ich hab auch schon daran gedacht, mit 4(auf meine Laptop unter x64 auch mal 8-Byte zu Iterieren, hab aber noch keinen Plan, wie ich aus einem 4-K Block mögliche Leerezichen Extrahieren soll.
Alleine bei der Unterscheidung Leerzeichen/Nicht Leerzeichen ergeben sich bei 4-Byte 2^4= 16 Möglichkeiten.
Ich habe Momentan pro Stelle mindestens 2 Operationen, maximal 3(C-Code, nicht assembler), würde als im Schlimmsten Fall bei 4 Zeichen in Folge 12 Operationen + Iterationen machen. Wenn ich aber 16 Möglichkeiten prüfen müsste...
Ich denk aber nochmal drüber nach...

[Xin]

Wenn ich das nur zu Leerzeichen ändere, dann braucht mein Code auf einmal aber DEUTLICH länger?
Kann mir das jemand erklären?! -,-

Schick mir Deinen Code, dann lach ich mal
Nein, aber vielleicht kann ich auch 'n Tipp geben ^^

Von daher:

Kann man gerne ausprobieren, aber dafür brauchen wir noch eine eindeutige Methode, um die Performance zu testen. clock() ist nur ein Näherungswert und wenn zur Ausführung des Programms swappen muss, dann bringt das nicht mehr viel.

Ist ein günstiger Moment, diesen Artikel endlich mal abzuschließen: http://proggen.org/doku.php?id=theory:time:start

Problem daran ist ja auch, dass man entweder hoffen muss, nicht in einen Bereich zu kommen, aus dem man nicht lesen darf.
Man könnte aber die API dahingehend erweitern, das übergeben wird, wie lang doch der String ist, bzw das man den String 2/4/6/8-Byte align anlegt und vorher mit '\0' füllt, sodass am Ende, sofern nicht schon 2X-Byte aligned das Ende bestimmt mit \0 gefüttert ist.

Wörter derart zählen ist kein übliches Problem, aber eins, dass recht nah an Alltagsproblemen liegt.

Das Ziel der Übung für lollinger ist/war, dass es eben keine Zählübung ist, wo man Leerzeichen zählt, sondern Wörter. Und Wörter haben - im Vergleich zu einzelnen Leerzeichen - keine konstante Länge. Das zweite Problem ist, dass Leerzeichen mehrfach hintereinander auftreten können. Man muss einen Status einführen: "Ich bin innerhalb des Wortes" oder "Ich bin außerhalb des Wortes".
Die Überlegung von Alignments ist nett - bringt aber nichts, da es keinen Einfluss auf die Länge der Leerblöcke oder Wörtlänge hat.
Ich kann Dir allerdings sagen, dass bei der hocheffizienten Bearbeitung von Texten Wörter tatsächlich Alignments erhalten, um genau diesen Effekt zu nutzen. Das funktioniert aber nur bei bekannten und für den Zugriff optimierten Texten (das ist dann kein ASCII mehr) - das Problem hier ist anderer Natur: wir haben unbekannte Daten.

Viele speichern den Status mit einer Variable, die 0/false (Leerzeichen) oder 1/true (innerhalb eines Wortes) ist. Dazu gehören auch die beiden schnellsten Algorithmen von bbl und cloidnerux. Mein Algorithmus hat diese Variable nicht, ich wechsle den Codeabschnitt, vergleichbar mit einer Turing-Maschine: Der Status wird durch den Code repräsentiert, daher muss keine Variable setzen oder auslesen.
Wieso ich dann trotzdem ein bisschen langsamer bin, habe ich noch nicht verstanden, aber wir werden es uns wohl später noch ansehen.


@lollinger: Was gibt die Neue Version beim String "Hallo Welt" zurück (kein Satzzeichen!).
Vergiss die Satzzeichen, Wörter im String zählen, nicht im ersten Satz. Der String endet, wenn Du das Nullbyte gefunden hast.

[canlot]

Xin kannst du meinen neuen Algorithmus bitte auswerten, denn ich dir zugeschickt habe?

[Xin]

Xin kannst du meinen neuen Algorithmus bitte auswerten, denn ich dir zugeschickt habe?

Ruhig Blut, es soll Tage geben, an denen ich nicht nur am Rechner sitze :->

cloidnerux und canlot werfen neue Versionen rein. Weiterhin hat ein Arbeitskollege zwei Versionen präsentiert.

Code: Alles auswählen

xin@trinity:~/Personen/xin$ time ./wc
File geöffnet
Size: 3760664220
xin   : 598752090 Wörter - Zeit: 17140000
xin++ : 598752090 Wörter - Zeit: 15920000
xinasm: 598752090 Wörter - Zeit: 10320000
cloid : 598752090 Wörter - Zeit: 16680000
cloid2: 598752090 Wörter - Zeit: 17220000
cloido: 598752090 Wörter - Zeit: 17020000
nouse : 598752090 Wörter - Zeit: 20620000
nouse2: 598752090 Wörter - Zeit: 18750000
mail  : 598752090 Wörter - Zeit: 21100000
mail2 : 598752090 Wörter - Zeit: 16220000
dirty : 606372480 Wörter - Zeit: 20890000
dirty2: 606372480 Wörter - Zeit: 22220000
lollinger: 9 Wörter - Zeit: 0
canlot: 598752090 Wörter - Zeit: 21780000
canlo2: 1197504180 Wörter - Zeit: 18930000
d93asm: 598752090 Wörter - Zeit: 12720000
micbac: 598752090 Wörter - Zeit: 18530000
micbac2: 598752091 Wörter - Zeit: 17970000

real    5m10.915s
user    4m51.314s
sys     0m2.848s

Die micbac Version ist eine der schönsten Codes. Der Code zwischen den { Klammern } ist nur 4 Zeilen lang.


Ich habe gerade die C-Quellen jetzt nochmal mit maximaler Optimierung laufen lassen. Das zeigt sehr schön, dass ein optimierender C-Compiler einem Assembler-Programmierer heute voraus ist.
Die Funktion xinasm ist die Assemblerversion der Funktion xin++.

Code: Alles auswählen

xin@trinity:~/Personen/xin$ time ./wc
File geöffnet
Size: 3760664220
xin   : 598752090 Wörter - Zeit: 10490000
xin++ : 598752090 Wörter - Zeit: 10190000
xinasm: 598752090 Wörter - Zeit: 10490000
cloid : 598752090 Wörter - Zeit: 9900000
cloid2: 598752090 Wörter - Zeit: 10520000
cloido: 598752090 Wörter - Zeit: 9740000
nouse : 598752090 Wörter - Zeit: 11430000
nouse2: 598752090 Wörter - Zeit: 8590000
mail  : 598752090 Wörter - Zeit: 9790000
mail2  : 598752090 Wörter - Zeit: 10480000
dirty : 606372480 Wörter - Zeit: 10120000
dirty2: 606372480 Wörter - Zeit: 11990000
lollinger: 9 Wörter - Zeit: 0
canlot: 598752090 Wörter - Zeit: 11760000
canlo2: 1197504180 Wörter - Zeit: 10630000
d93asm: 598752090 Wörter - Zeit: 12770000
micbac: 598752090 Wörter - Zeit: 10430000
micbac: 598752091 Wörter - Zeit: 10490000

real    3m13.806s
user    2m59.823s
sys     0m2.392s

Die ASM-Versionen von dani93 und mir werden durch die Optimierung nicht verändert.

[nouseforname]

[quote="Xin"]
Ich habe gerade die C-Quellen jetzt nochmal mit maximaler Optimierung laufen lassen. Das zeigt sehr schön, dass ein optimierender C-Compiler einem Assembler-Programmierer heute voraus ist.
Die Funktion xinasm ist die Assemblerversion der Funktion xin++.

Code: Alles auswählen

nouse : 598752090 Wörter - Zeit: 11430000
nouse2: 598752090 Wörter - Zeit: 8590000  <------

Fehlt da ne null oder is das in der Runde eindeutig am schnellsten (bei mehr als 9 gefundenen Wörtern)???

[canlot]

Hm so wie ich sehe bin ich jetzt am schnellsten, oder nicht?

[Xin]

Ich habe gerade die C-Quellen jetzt nochmal mit maximaler Optimierung laufen lassen.

Code: Alles auswählen

nouse : 598752090 Wörter - Zeit: 11430000
nouse2: 598752090 Wörter - Zeit: 8590000  <------

Fehlt da ne null oder is das in der Runde eindeutig am schnellsten (bei mehr als 9 gefundenen Wörtern)???

Da fehlt keine Null. Der Compiler optimiert das soweit wie es ihm machbar ist. Das bedeutet allerdings, dass da nicht nur Dein Know How drin steckt sondern auch eine Menge Know-How des Compilers, wie man das optimal an eine CPU verfüttert.
Während dani93 und ich das Problem mit braven Assembler zwar schnell lösen können, hat da vermutlich ein Compilerentwickler Wochenlang dran gesessen, um den genau diesen Fall herauszufinden, wo er mit speziellen uns völlig unbekannten Assemblerbefehlen diesem Problem noch mehr einheizen kann.
Das sollte aber aufzeigen, dass man mit gut optimierten C-Programmen und einem optimierten C-Compiler einen Assemblerprogrammierer schlägt, sofern er nicht wirklich top fit ist.
Ich bin aber auch erstaunt, dass zwischen uns noch ein so großer Unterschied ist, weil ich meinen ASM-Code für gar nicht mal sooo schlecht hielt.
Ich habe zuletzt vor 1999 x86-Assembler programmiert, ich bin also definitiv nicht top fit, brauchte sogar dani93s Hilfe, um herauszufinden, wie die 64-Bit Register in Assembler heißen, weil es die damals noch gar nicht gab. ^^

[nouseforname]

Alles in allem zeigt das aber wiedermal, dass es viele Wege gibt um eine Aufgabe zu lösen, und keine davon mag als 100% falsch/richtig eingestuft werden.

ps. Dass der Compiler eine wichtige Rolle spielt habe ich schon verstanden. Fand nur den "grossen" Unterschied so interessant, wo doch mein Code sonst eher im Mittelfeld angesiedelt ist, zeitlich gesehen. Mir fällt auch im Moment kein Weg ein, noch mehr einzusparen oder zu optimieren. Aber ich sitze auch nicht Std-lang da um darüber nachzudenken^^

[Xin]

Hier die Auswertung:

Auswertung