Wie funktioniert `wc -l`?

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

Ich habe viele Lösungen implementiert und eine gefunden. Aber während meiner Suche habe ich darüber nachgedacht, 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?

linux coreutils Detraveller
quelle

lingrok.org/xref/coreutils/src/wc.c

Arjan

Antworten:

Es liest die gesamte Datei und zählt die Anzahl der Zeilenenden. Das Zählen von Zeilenenden ist wirklich billig; Die meiste Zeit wird mit dem Lesen der Datei verbracht. Wenn sich die Datei (meistens) im Puffercache befindet, ist das auch billig. Andernfalls hängt es von der Geschwindigkeit Ihres Dateispeichers ab.

Mit anderen Worten, es gibt keine Magie.

Rici
quelle

Es liest die gesamte Datei und zählt die Anzahl der Zeilenenden? Liest es nicht im Grunde die ganze Zeile, bis das Ende erreicht ist, um zum Zeilenende zu gelangen? Und das würde bedeuten, dass es die ganze Datei liest, oder?

Detraveller

@detraveller: ja, es liest die gesamte Datei, wie gesagt. Es liest es nicht Zeile für Zeile oder auf einmal, aber es liest jedes Zeichen und zählt, wie viele dieser Zeichen Zeilenendezeichen sind.

Rici

WC liest die Datei nur in Blöcken von Rohbytes (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 werden auch Leerzeichen, Tabulatoren, Formular-Feeds und andere Sonderzeichen gezählt, nur für den Fall, dass Sie andere Informationen als die Ausgabe -l wünschen.)

Das Lesen von der Festplatte ist der kostspielige Teil in Bezug auf die Geschwindigkeit. Das Scannen des Puffers nimmt im Vergleich dazu vernachlässigbare Zeit in Anspruch.

Angenommen, Sie haben 90 Millionen Zeilen mit durchschnittlich 100 Zeichen pro Zeile.
Das sind ungefähr 9.000.000.000 Zeichen oder ungefähr 860 MB.
Ein anständiger PC mit einem SATA-3-Gbit / s-Laufwerk erledigt dies in weniger als 10 Sekunden. Selbst in einem relativ langsamen Dateisystem, in dem gleichzeitig andere Aktivitäten ausgeführt werden.
Ein schneller Computer mit einigen Leistungsoptimierungen und einem optimierten Dateisystem kann dies in weniger als 5 Sekunden tun, auch ohne auf SATA-6G und ein SSD-Laufwerk zurückgreifen zu müssen.

Tonny
quelle

es durchsucht nur den Puffer und zählt die \nZeichen am Ende der Zeile ( ) - "-l, - Zeilen drucken die Zeilenumbrüche \ n \" - extrahiert auswc.c

Rahul Patil

@RahulPatil Die meisten Implementierungen bieten viel mehr als nur das Zählen von Zeilenumbrüchen. Siehe das oben im oberen Kommentar erwähnte Beispiel. Dies ist die Quelle von wc, wie sie in den Linux-Kerndienstprogrammen verwendet wird.

Tonny

ja .. ich habe das gesehen .. nur ich erwähne weil, Frage über wc -l.. sorry ...

Rahul Patil

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

Obwohl ich zugeben muss, dass ich kein C-Programmierer bin, bin ich nicht derjenige, der den Code wirklich für Sie erklären kann (und ich wäre selbst begeistert).

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

Alois Mahdal
quelle

Was meinen Sie damit, dass Sie nicht versuchen, die gesamte Datei auf einmal zu lesen?

Detraveller

Ich meine, die Datei in den Speicher zu laden, beispielsweise in einen einzelnen String / Array. In der Perl-Community wird dies als Slurping bezeichnet. Es handelt sich um eine schnelle und schmutzige Lösung, die in Ordnung ist, wenn Sie wissen, dass Sie nur wenige Zeilen lesen, aber es ist selten eine gute Idee, wirklich große Dateien gleichzeitig in den Speicher einzuspeisen.

Alois Mahdal

Auf der anderen Seite können Sie beispielsweise 64 KiB lesen, Zeilenumbrüche zählen und wegwerfen, wiederholen ... Auf diese Weise essen Sie höchstens etwas über 64 KiB auf, egal wie groß die Datei ist. (Es ist weniger einfach, wenn Sie erkennen, dass Newline 2 Bytes haben und somit auf 2 Chunks aufgeteilt werden kann; jetzt beginnt der Spaß)

Alois Mahdal

Nicht allzu wichtig, aber: "da wc die Datei selbst nicht öffnet, sondern das Betriebssystem dazu auffordert" - nicht sicher, was Sie damit meinen, aber ich bezweifle, dass dies richtig ist. Es liest sicherlich alle Zeichen für sich.

Arjan

@Arjan Obwohl, um wirklich richtig zu sein: Programme, die eingebettete Systeme ausschließen, kaum selbst lesen, ist der springende Punkt bei Kernel und OS, dass es die Arbeit für sie erledigt. Tatsächlich sind open (), close (), read () (sei es Linux, Windows, Socket oder Datei) alle Systemaufrufe, bei denen tatsächliche Programme keine Ahnung von der inneren Funktionsweise haben.

Alois Mahdal