Gibt es eine Datei (binär oder textuell), was ist die schnellste oder eleganteste Methode in C ++, um die Einsen und Nullen in der Binärdarstellung dieser Datei zu zählen?
Erstellen Sie ein Char-Array mit 256 Zeichen Länge. Durchstreichen Sie die Datei jeweils byteweise, um die Array-Position jedes Bytes zu erhöhen. Hard-Code die Anzahl der 1s in jedem der 256 Bytes in einem anderen Array. Multiplizieren Sie die 2 Arrays und die Summe.
Nicht sicher über Eleganz und erfordert definitiv mehr Speicher, aber könnte schneller sein als linuxuser27 Algorithmus.
Wann immer ich den besten Bitmanipulationstrick für eine bestimmte Aufgabe wissen möchte, beginne ich hier: Ссылка
Unter "Zählen von Bits, die parallel gesetzt sind" listen sie eine 12-Funktions-Methode zum Zählen der in einer 32-Bit-Ganzzahl gesetzten Bits auf. Sie zeigen auch Methoden für Ganzzahlen größer als 32 Bit.
Auf fast jedem System wird die Hauptausführungszeit in die E / A-Richtung gehen. Und wie man den schnellsten E / A erreicht, hängt sehr vom System ab. Es gibt also keine einzige Antwort auf "Schnellster".
Am meisten "elegant" hängt von den Augen ab, die sehen.
Zusammenfassend ist festzustellen, dass keine der beiden Fragen eine eindeutige Antwort hat. es klingt nach Angeln nach Lösungen für eine Hausaufgabe. Ist es Hausaufgaben?
Hier ist ein vollständiges Beispiel (naja, es gibt fast eine Übung für den Implementor am Ende ...) Es benutzt die 12 Instruktionszählung für 32 Byte Werte von Ссылка . Außerdem lädt es die Datei mit mmap, da diese (oft) schneller ist als andere Lesemethoden. Ich denke, das einzige, was man tun kann, um es schneller zu machen, wäre, die Anzahl auf mehrere Threads aufzuteilen. Aber auf meinem System verarbeitet es schon 10MB Dateien in weniger als 0.03s, was mir ok erscheint.
%Vor% Ich lese in der Datei ein unsigned int gleichzeitig ein und zähle die Anzahl der Bits, die in jedem bis EOF eingeschaltet sind. Sie können den klassischen Sparse-Count-Algorithmus verwenden, um die Anzahl von 1 s in einem unsigned int -Wert zu zählen.
Machen Sie das oben für alle in unsigned int Werte gelesen und behalten Sie eine laufende Summe.
Ich würde versuchen, std::bitset zu verwenden, es hat eine gute Implementierung der Methode count() () Schnittstelle ), indem ein vorberechnetes Array der Länge 256 für die Zählung aller möglichen Werte beibehalten wird
Bytes. Zum Zählen von Nullen,
Ich würde file_zero_count = 0 initialisieren und die Datei öffnen. Dann würde ich in jeder Iteration einer Schleife N Bits in ein Bitset einlesen und die zero_count dieser N Bits zu file_zero_count hinzufügen. Dann lies die nächsten N Bits und so weiter ...
Die entscheidende Wahl ist der Wert von N . Meine erste Wahl wäre so, dass N Bits in eine Speicherseite passen, z. N = 4096 .
Ein einfacher und schneller Weg besteht darin, eine Nachschlagetabelle zu erstellen, die Ihnen sagt, wie viele 1 irgendwelche der Zeichen aufweist, z. 'a' mit ASCII 97 hat 3. Sie können eine solche Nachschlagetabelle in einem Array fester Länge für den Zugriff bei konstanter Zeit speichern. Laden Sie die Datei Seite für Seite in den Speicher, um die Anzahl der E / A zu minimieren und für jedes Zeichen sequenziell zu zählen.
Wenn Sie mehr Informationen über die Art der Daten erhalten, die Sie bearbeiten, können interessantere Lösungen erstellt werden. Wenn Sie beispielsweise wissen, dass die Datei textuelle Daten in natürlicher Sprache enthält, können Sie Nachschlagetabellen für häufig vorkommende Begriffe wie "das", "von" und "und" erstellen, um die Berechnungen zu beschleunigen. Eine solche Nachschlagetabelle kann effizient in der Hash-Tabelle gespeichert werden.
Ich würde Byte für Byte in die Datei einlesen und die Anzahl von 1/0 in jedem Byte zählen:
Der Grund, warum ich Byte wählen würde, ist, dass es einfach ist, ein Lookup für die Anzahl von 1 in einem Byte von Hand zusammenzustellen. Hinweis: Ich habe die Anzahl der Einsen in einem Byte gezählt. Aber ich habe die Tabelle rückwärts gebaut (also ist es eigentlich eine Zählung der Anzahl der Nullen (wie es die Inversen der Einsen sind)).
%Vor%Jetzt müssen Sie nur noch ein std :: for_each verwenden, das über einen Stream iteriert (ohne Leerzeichen zu löschen.
) %Vor%Jetzt müssen Sie nur einen geeigneten Typ für den Zähler definieren und der Rest ist Geschichte.