Wie funktioniert 'wc -l'?

2061
detraveller

Ich muss eine große Datei lesen und bevor ich mit dem Lesen anfange, muss ich die Gesamtzahl der Zeilen in der Datei kennen (die in Millionen sind).

Ich habe viele Lösungen implementiert und eine gefunden. Aber während meiner Suche dachte ich darüber nach, wie es wc -lfunktioniert. Ich konnte bei Google nichts finden.

Obwohl ich eine Lösung für mein Problem gefunden habe, würde ich gerne wissen, wie es wc -lfunktioniert, da es die Anzahl der Zeilen einer Datei mit 92 Millionen Zeilen in wenigen Sekunden berechnen kann!

Wie?

9
http://lingrok.org/xref/coreutils/src/wc.c Arjan vor 10 Jahren 5

3 Antworten auf die Frage

19
rici

Es liest die gesamte Datei und zählt die Anzahl der Zeilenenden. Das Zählen von Zeilenenden ist wirklich günstig. Die meiste Zeit verbringt das Lesen der Datei. Wenn sich die Datei (meistens) im Puffercache befindet, ist das auch billig. Andernfalls hängt es von der Geschwindigkeit Ihrer Dateispeicherung ab.

Mit anderen Worten, es gibt keine Magie.

Es liest die gesamte Datei und zählt die Anzahl der Zeilenenden. Um an das Zeilenende zu gelangen, liest es nicht die gesamte Zeile bis zum Ende? Und das würde bedeuten, dass die gesamte Datei gelesen wurde, richtig? detraveller vor 10 Jahren 0
@ detraveller: ja, es liest die ganze Datei, wie ich schon sagte. Es liest es nicht Zeile für Zeile oder alle gleichzeitig, sondern liest jedes Zeichen und zählt, wie viele dieser Zeichen Zeilenendezeichen sind. rici vor 10 Jahren 0
7
Tonny

WC liest die Datei nur in Blöcken roher Bytes (vorzugsweise in Vielfachen der natürlichen Blockgröße des zugrunde liegenden Dateisystems, auf dem sich die Datei befindet).
Dann durchsucht es einfach den Puffer und zählt die Zeilenendezeichen. (Es zählt auch Leerzeichen, Tabulatoren, Formular-Feeds und andere Sonderzeichen, nur für den Fall, dass Sie andere Informationen als die -l-Ausgabe wünschen.)

Das Lesen von der Festplatte ist der kostenintensive Teil. Das Durchsuchen des Puffers benötigt im Vergleich dazu eine vernachlässigbare Zeit.

Angenommen, Sie haben 90 Millionen Zeilen mit durchschnittlich 100 Zeichen pro Zeile.
Das sind rund 9.000.000.000 Zeichen oder etwa 860 MB.
Ein anständiger PC mit einem SATA-3Gb / s-Laufwerk macht dies in weniger als 10 Sekunden. Sogar auf einem relativ langsamen Dateisystem, während gleichzeitig andere Aktivitäten ausgeführt werden.
Eine schnelle Maschine mit etwas Leistungsoptimierung und einem optimierten Dateisystem kann dies innerhalb von 5 Sekunden erledigen, auch ohne auf SATA-6G und ein SSD-Laufwerk zurückgreifen zu müssen.

Es durchsucht nur den Puffer und zählt die Zeilenendezeichen ("\ n") - "-l, --lines", um die Zeilenanzahl \ n \ "zu drucken - extrahiert aus" wc.c " Rahul Patil vor 10 Jahren 0
@RahulPatil Bei den meisten Implementierungen geht es nicht nur um das Zählen von Zeilenumbrüchen. Siehe das oben im Beispiel oben erwähnte Beispiel. Dies ist die Quelle von wc, wie sie in den Linux-Kernprogrammen verwendet wird. Tonny vor 10 Jahren 0
ja .. das habe ich gesehen .. ich erwähne es nur, Frage zu `wc -l '.. sorry ... Rahul Patil vor 10 Jahren 0
3
Alois Mahdal

Willkommen in der Welt der freien Software. Sie können immer den Quellcode betrachten

Obwohl ich zugeben muss, dass ich kein C-Programmierer bin, kann ich nicht wirklich den Code für Sie erklären (und ich würde mich selbst dafür interessieren).

Was ich weiß ist, da wc die Datei nicht selbst öffnet, sondern das Betriebssystem dazu auffordert, hängt dies weitgehend vom Betriebssystem und natürlich davon ab, wie die Datei gespeichert wird. Abgesehen davon erwarte ich, dass korrekte Programmierpraktiken vorhanden sein müssen, z. B. nicht versuchen, die Datei als Ganzes zu lesen, usw.

Was meinen Sie damit, "nicht versuchen, die gesamte Datei auf einmal zu lesen"? detraveller vor 10 Jahren 0
Ich meine, das Laden der Datei in den Arbeitsspeicher, z. B. in einen einzelnen String / Array. In der Perl-Community wird dies als Slurping bezeichnet. Dies ist eine schnelle und schmutzige Lösung, die in Ordnung ist, wenn Sie * wissen *, dass Sie nur wenige Zeilen lesen werden, aber das Einfügen wirklich großer Dateien gleichzeitig in den Speicher ist selten eine gute Idee. Alois Mahdal vor 10 Jahren 0
Auf der anderen Seite können Sie beispielsweise 64 KiB lesen, Zeilenumbrüche zählen und wegwerfen, wiederholen ... Auf diese Weise werden Sie etwas über 64 KiB aufbrauchen, egal wie groß die Datei ist. (Es ist weniger einfach, wenn Sie erkennen, dass Newline 2 Bytes haben kann und somit auf zwei Abschnitte aufgeteilt wird. Jetzt beginnt der Spaß.) Alois Mahdal vor 10 Jahren 1
Nicht zu wichtig, aber: * "da wc die Datei nicht selbst öffnet, sondern das Betriebssystem dazu auffordert" * - nicht sicher, was Sie damit meinen, aber ich bezweifle, dass dies richtig ist. Es liest sicher alle Charaktere für sich. Arjan vor 10 Jahren 0
@Arjan Ich meine das im Sinne von "Öffnen", nicht das Lesen der Bytes. IOW: Es spricht nicht mit dem Dateisystemtreiber oder bewegt die Festplattenköpfe an die richtige Position :) Es ist nicht einmal wichtig, wo / wie die Datei gespeichert oder zwischengespeichert wird. Ja, endlich kaut es die Bytes mit eigenen Zähnen :) Alois Mahdal vor 10 Jahren 0
@Arjan Obwohl, um wirklich richtig zu sein: Ohne eingebettete Systeme lesen Programme kaum wirklich das Lesen selbst. Der Kernpunkt von Kernel und Betriebssystem ist, dass es die Aufgabe für sie erledigt. In der Tat sind open (), close (), read () (sei es Linux, Windows, Socket oder Datei) alles Systemaufrufe, bei denen die eigentlichen Programme keine Ahnung von inneren Abläufen haben. Alois Mahdal vor 10 Jahren 1

Verwandte Probleme