Textdatei am schnellsten sortieren, bash, php, python, C ?

[ren22]

Weiss einer von euch, was am schnellsten ist zum sortieren nach 0-9 und A-Z und doppelte Einträge entfernen?
bash , php oder python, ..notfalls auch C
Angenommen man hat eine Textdatei mit ca. 100000, (gemischtes Verhältnis), IP-Adressen, Domainname und subdomainname.domainname.endung alles in einer Datei, Zeile für Zeile, durcheinander gewürfelt. Welche "Sprache" wäre da am schnellsten auf einem Single Core Prozessor um diese Textdatei, 1.) doppelte Einträge entfernen und 2.) Sortieren nach [0-9], und [A-Z] ?

Danke

[wanne]

bash. Du nimmst das in C gschriebene sort -u, und die heben wesentlich mehr Gehirnschmalz reingesteckt als du je machen würdest.
Sost dürfte das schnellste String Handling in C++ möglich sein. Da muss man aber sehr gut wissen, was man tut.

[MSfree]

Die Ausgabe von sort kann man nach uniq pipen, um doppelte Einträge zu eliminieren.

[wanne]

Bei mir liefert sort | uniq tatsächlich merklich andere ergebnisse als
sort -u
Bei vollständig zufälligen Daten liegt sort -u aber vorn.

[Lord_Carlos]

Wenn es sich nur um 100000 eintraege handelt, ist es dann nicht fast egal?

[Meillo]

Bei mir liefert sort | uniq tatsächlich merklich andere ergebnisse als
sort -u

Mit ``anderen Ergebnissen'' meinst du aber andere Laufzeiten, nicht etwa andere Ausgaben, oder? Sonst waere ich doch sehr irritiert.


@ren22: Geht es dir um ein praktisches Problem oder um die akademische Frage? Wenn ersteres, dann verwende ``sort -u'' und denk nicht mehr drueber nach. Wenn zweiteres, dann sollten hier harte Fakten, wie Zeitperformance-Messungen und Code-Analysen gepostet werden, weil anderes nicht weiter hilft.

[eggy]

Etwas Offtopic da ja explizit nach A-Z0-9 gefragt war:

I.
Mit sort und uniq (und überhaupt allem was coreutils ist) wäre ich sehr vorsichtig: je nach locale gibts da lustige Ergebnisse z.B. bei doublewide chars.

Code: Alles auswählen

echo -e "カ\nキ\nク\nケ\nコ" |sort
echo -e "カ\nキ\nク\nケ\nコ" |sort -u 
echo -e "カ\nキ\nク\nケ\nコ" |sort | uniq

II.
@Wanne: warum glaubst Du, dass man aus C++ hier effizienteren Code erzeugt als in z.B. C? Bei der oben genannten Anforderung (PlainASCII ohne Sonderzeichen und Maskierungen) würde ich eher zusätzlichen Overhead erwarten, insbesondere wenn man da Objektorientiert draufkloppt.

[uname]

würde ich eher zusätzlichen Overhead erwarten, insbesondere wenn man da Objektorientiert draufkloppt.

Das optimiert der Compiler bestimmt alles weg

[Meillo]

je nach locale gibts da lustige Ergebnisse

So soll das ja auch sein -- wenn es das falsche Locale ist, dann ist die Sortierreihenfolge ggf. eine andere.

Dass nicht alle Implementierungen vollstaendig internationalisiert sind, ist aber natuerlich ein Problem.

[dufty2]

Vergleiche mal

Code: Alles auswählen

$ time sort -u blub > blob

mit

Code: Alles auswählen

$ time LC_ALL=C sort -u blub > blob

Mein normalo-user bekommt die "de_DE.utf8", damit 'date' nicht umgewöhnungsbedürftig wird
root hingegen hat "C.utf8", und damit tritt auch das von eggy beschriebene lustige Phänomen der doublewide chars nicht auf.

[eggy]

@Meillo: Ja, soweit das die Reihenfolge angeht, völlig ok und da halte ich "unterschiedliches Verhalten" auch für nen Feature.
Aber hier geht es nicht um "A kommt vor Z im Alphabet" sondern um "A und B sind zwei unterschiedliche Zeichen".
Das Beispiel von oben sind japanische Katakana, dabei ist z.B. カ ein "ka" und キ ein "ki". Die Kana sind ein sogenanntes Silbenalphabet.
Angenommen wir würden so ähnlich schreiben, für "Hund" und "Hand" statt "H"-"u"-"n"-"d" oder "H"-"a"-"n"-"d" dann "Hu"-"nd" oder "Ha"-"nd" und sort -u betrachtet hier auch nur jeweils den ersten von den zwei Buchstaben:
aus
echo -e "Hand\nHund" |sort -u
Hand
Hund
würde damit
echo -e "Hn\nHn" | sort -u
Hn
tja schon irgendwie "lustig". (Und ja, der Bug ist bereits in mehreren Varianten bei unterschiedlichen Distributionen gemeldet und auch Upstream bekannt. Würde wahrscheinlich auf nen kompletten rewrite der coreutils hinauslaufen, mit all den tollen Seiteneffekten die sowas mit sich bringt)

@dufty: Dass man das Problem umgehen kann ist mir bewusst, aber dazu muss man ja erstmal wissen, dass es überhaupt ein Problem gibt

[Meillo]

Mein normalo-user bekommt die "de_DE.utf8", damit 'date' nicht umgewöhnungsbedürftig wird

Darum gibt es nicht nur LC_ALL sondern die Unterscheidung zwischen LC_TIME und LC_COLLATE.


Vielleicht bin ich ja zu sehr ein Theoretiker, aber wenn man das gewuenschte Locale gewaehlt hat und dieses korrekt implementiert ist und die verwendete sort-Implementierung dieses korrekt verwendet, dann bekommt man das richtige Ergebnis. Wenn eine der Implementierung falsch ist, dann ist das ein Bug. Wenn man das falsche Locale gewaehlt hat, dann ist man selber schuld.

Hab mir zumindest die Muehe gemacht, GNU uniq mit Heirloom uniq zu vergleichen:

Code: Alles auswählen

:-Q locale | grep LC_COLLATE
LC_COLLATE="en_US.UTF-8"

:-Q printf "カ\nキ\nク\nケ\nコ\n" |uniq    # GNU
カ

:-Q printf "カ\nキ\nク\nケ\nコ\n" |./uniq    # Heirloom
カ
キ
ク
ケ
コ

Fazit: GNU uniq ist nicht UTF-8-faehig. Irgendwie hat mich das nicht ueberrascht ... Man muss halt eine ordentliche Implementierung nehmen. Die GNU-Tools sind in der Hinsicht leider ziemlich hinten dran.

[wanne]

@Wanne: warum glaubst Du, dass man aus C++ hier effizienteren Code erzeugt als in z.B. C? Bei der oben genannten Anforderung (PlainASCII ohne Sonderzeichen und Maskierungen) würde ich eher zusätzlichen Overhead erwarten, insbesondere wenn man da Objektorientiert draufkloppt.

Wenn man mit zu viel Objektorientierung drauf kloppt ist natürlich Schluss.
Die strings (Falls da viel ausländische URLs drin sind vielleicht auch u16string schneler) sollte man deutlich schneller arbeiten können als mit den komischen C Dingern.
Wahrscheinlich ist man aber am schnellsten, wenn man sich sowas in C selbst baut.

Fazit: GNU uniq ist nicht UTF-8-faehig. Irgendwie hat mich das nicht ueberrascht ... Man muss halt eine ordentliche Implementierung nehmen. Die GNU-Tools sind in der Hinsicht leider ziemlich hinten dran.

Ich sehe das anders. en_US enthällt halt kein カ entsprechend darf man da solche Fälle wegoptimieren. Das hast dann du verkackt.

Code: Alles auswählen

export LC_COLLATE="ja_JP.UTF-8"
printf "カ\nキ\nク\nケ\nコ\n" | uniq
カ
キ
ク
ケ
コ

Willst du eine saubere vollständige UTF-8 Implementierung musst du C.UTF-8 nehmen. Auch der funktioniert wie gewünscht. Den benutze ich.
Btw. ist der C.UTF-8 deutlich schneller als der en_US.UTF-8. Was mich jetzt schon wieder an den GNU Leuten zweifeln lässt. Kann der C.UTF-8 nicht schlicht nur mehr?

[Meillo]

Fazit: GNU uniq ist nicht UTF-8-faehig. Irgendwie hat mich das nicht ueberrascht ... Man muss halt eine ordentliche Implementierung nehmen. Die GNU-Tools sind in der Hinsicht leider ziemlich hinten dran.

Ich sehe das anders. en_US enthällt halt kein カ entsprechend darf man da solche Fälle wegoptimieren.

Da hast du Recht, wir haben unterschiedliche Meinungen dazu.

IMO darf uniq(1) nicht einfach alle Zeichen, die nicht Teil der gewaehlten Sprache sind, als identisch werten. Vielmehr muesste es sie als unverstanden ansehen und damit das einzig Sinnvolle tun was moeglich ist, naemlich ihre Codepoints zu vergleichen. Das passiert aber nicht.

btw: Auch in einem deutschsprachigen Buch koennen japanische Zeichen vorkommen, wenn ich davon die Zeichenhaeufigkeit auswerten will (wozu ich uniq(1) brauche) sollen diese ebenso aufgefuehrt sein, keinesfalls aber ignoriert werden, bloss weil ich ein deutsches Locale verwende.

Edit: Wie sollten denn U+1F384 und U+1F389 behandelt werden? Sind das englische Zeichen?

Willst du eine saubere vollständige UTF-8 Implementierung musst du C.UTF-8 nehmen. Auch der funktioniert wie gewünscht.

Bei mir nicht (GNU uniq 8.13).

[wanne]

Die jessie coreutils (8.23) können es.
Mit dem Weihnachtsbaum bekommt man sie dann aber auch.
Aber da stürzt auch das Forum ab