Schnellste Methode zum Summieren von Ganzzahlen in der Textdatei
Angenommen, Sie haben eine große ASCII-Textdatei mit einer zufälligen nicht-negativen Ganzzahl in jeder Zeile im Bereich von 0 bis 1.000.000.000. Die Datei enthält 100.000.000 Zeilen. Was ist der schnellste Weg, um die Datei zu lesen und die Summe aller ganzen Zahlen zu berechnen?
Einschränkung: Wir müssen mit 10 MB RAM arbeiten. Die Datei hat eine Größe von 1 GB, daher möchten wir nicht alles einlesen und dann verarbeiten.
Hier sind verschiedene Lösungen, die ich ausprobiert habe. Ich fand die Ergebnisse eher überraschend.
Gibt es etwas schnelleres, das ich verpasst habe?
Bitte beachten Sie Alle unten angegebenen Zeiten gelten für die Ausführung des Algorithmus10 ma insgesamt (einmal ausführen und verwerfen; Timer starten; 10-mal ausführen; Timer stoppen). Die Maschine ist ein ziemlich langsamer Core 2 Duo.
Methode 1: der natürliche AnsatzDas erste, was Sie versuchen sollten, ist der offensichtliche Ansatz:
private long sumLineByLine() throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String line;
long total = 0;
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
br.close();
return total;
}
Beachten Sie, dass der maximal mögliche Rückgabewert 10 ^ 17 ist, was immer noch leicht in ein @ passlong, damit wir uns keine Sorgen um Überläufe machen müssen.
Auf meinem Computer dauert das elfmalige Ausführen und das Reduzieren des ersten Laufs ungefähr 92,9 Sekunden.
Methode 2: a minor tweak Inspiriert von einem Kommentar zudiese Frag, Ich habe versucht, kein neues @ zu erstellint k, um das Ergebnis der Analyse der Zeile zu speichern und stattdessen den analysierten Wert direkt zu @ hinzuzufügetotal. Also das
while ((line = br.readLine()) != null) {
int k = Integer.parseInt(line);
total += k;
}
wird dies:
while ((line = br.readLine()) != null)
total += Integer.parseInt(line);
Ich war mir sicher, dass dies keinen Unterschied machen würde, und hielt es für sehr wahrscheinlich, dass der Compiler den gleichen Bytecode für die beiden Versionen generieren würde. Aber zu meiner Überraschung hat sich die Zeit etwas verkürzt: Wir sind bei 92,1 Sekunden.
Methode 3: Manuelles Parsen der GanzzahlEine Sache, die mich am Code stört, ist, dass wir das @ drehString In einint, und fügen Sie es am Ende hinzu. Könnte es nicht schneller sein, etwas hinzuzufügen, wenn wir gehen? Was passiert, wenn wir das @ analysierString uns selbst? Etwas wie das..
private long sumLineByLineManualParse() throws NumberFormatException,
IOException {
BufferedReader br = new BufferedReader(new FileReader(file));
String line;
long total = 0;
while ((line = br.readLine()) != null) {
char chs[] = line.toCharArray();
int mul = 1;
for (int i = chs.length - 1; i >= 0; i--) {
char c = chs[i];
switch (c) {
case '0':
break;
case '1':
total += mul;
break;
case '2':
total += (mul << 1);
break;
case '4':
total += (mul << 2);
break;
case '8':
total += (mul << 3);
break;
default:
total += (mul*((byte) c - (byte) ('0')));
}
mul*=10;
}
}
br.close();
return total;
}
Dies, dachte ich, könnte ein wenig Zeit sparen, insbesondere bei einigen Bitverschiebungsoptimierungen für die Multiplikation. Aber der Aufwand für die Konvertierung in ein Zeichen-Array muss alle Gewinne übersteigen: Dies dauert jetzt 148,2 Sekunden.
Methode 4: Verarbeitung in binärenAls letztes können wir versuchen, die Datei als Binärdaten zu verarbeiten.
Parsing eine ganze Zahl von vorne ist umständlich, wenn Sie die Länge nicht kennen. Es ist viel einfacher, es rückwärts zu analysieren: Die erste Ziffer, auf die Sie stoßen, ist Einheiten, die nächste ist Zehn und so weiter. Der einfachste Weg, sich dem Ganzen zu nähern, besteht darin, die Datei rückwärts zu lesen.
Wenn wir ein @ zuweisbyte[] buffer of (say) 8MB, wir können es mit den letzten 8MB der Datei füllen, es verarbeiten, dann die vorhergehenden 8MB lesen und so weiter. Wir müssen ein wenig vorsichtig sein, damit wir keine Zahl vermasseln, die gerade analysiert wird, wenn wir zum nächsten Block übergehen, aber das ist das einzige Proble
Wenn wir auf eine Ziffer stoßen, addieren wir sie (entsprechend ihrer Position in der Ziffer multipliziert) zur Summe und multiplizieren dann den Koeffizienten mit 10, damit wir für die nächste Ziffer bereit sind. Wenn wir auf etwas stoßen, das keine Ziffer ist (CR oder LF), setzen wir einfach den Koeffizienten zurück.
private long sumBinary() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[8*1024*1024];
int mul = 1;
long total = 0;
while (lastRead>0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead-len);
raf.readFully(buf, 0, len);
lastRead-=len;
for (int i=len-1; i>=0; i--) {
//48 is '0' and 57 is '9'
if ((buf[i]>=48) && (buf[i]<=57)) {
total+=mul*(buf[i]-48);
mul*=10;
} else
mul=1;
}
}
raf.close();
return total;
}
Dies läuft in 30,8 Sekunden! Das ist ein Geschwindigkeitserhöhung um den Faktor 3 über dem vorherigen besten.
FolgefrageWarum ist das so viel schneller? Ich habe erwartet, dass es gewinnt, aber nicht ganz so beeindruckend. Ist es hauptsächlich der Aufwand für die Konvertierung in einString? Und all die Sorgen hinter den Kulissen über Zeichensätze und dergleichen?Können wir etwas Besseres tun, indem wir ein @ verwendeMappedByteBuffer helfen? Ich habe das Gefühl, dass der Overhead des Aufrufs von Methoden zum Lesen aus dem Puffer die Dinge verlangsamen würde, insbesondere wenn rückwärts aus dem Puffer gelesen wird.Wäre es besser, die Datei vorwärts und nicht rückwärts zu lesen, aber den Puffer trotzdem rückwärts zu scannen? Die Idee wäre, dass Sie den ersten Teil der Datei lesen und dann rückwärts scannen, aber die halbe Zahl am Ende verwerfen. Wenn Sie dann den nächsten Block lesen, stellen Sie den Versatz so ein, dass Sie ab dem Anfang der Zahl lesen, die Sie verworfen haben.Ist da irgendetwas, woran ich nicht gedacht habe, dass es einen signifikanten Unterschied machen könnte?Update: überraschendere ErgebnisseZunächst eine Beobachtung. Es hätte mir schon mal einfallen sollen, aber ich denke der Grund für die Ineffizienz desString -basiertes Lesen ist nicht so sehr die Zeit, die benötigt wird, um das gesamte @ zu erstelleString objects, aber die Tatsache, dass sie so kurzlebig sind: Wir haben 100.000.000 davon für den Müllsammler. Das wird es bestimmt verärgern.
Nun einige Experimente basierend auf Antworten / Kommentaren, die von Leuten gepostet wurden.
Betrüge ich mit der Größe des Puffers? Ein Vorschlag war, dass seit einemBufferedReader verwendet einen Standardpuffer von 16 KB, und ich habe einen Puffer von 8 MB verwendet, ich vergleiche nicht wie mit wie. Es ist sicher schneller, wenn Sie einen größeren Puffer verwenden.
Hier ist der Schock. DassumBinary()ie @ -Methode (Methode 4) lief gestern in 30,8 Sekunden mit einem 8-MB-Puffer. Heute, Code unverändert, hat sich die Windrichtung geändert und wir sind bei 30,4 Sekunden. Wenn ich die Puffergröße auf 16 KB absenke, um zu sehen, wie viel langsamer es wird,es wird schneller! Es läuft jetzt in 23,7 Sekunden. Verrückt. Wer hat das kommen sehen?!
Ein bisschen experimentieren legt nahe, dass 16 KB ungefähr optimal sind. Vielleicht haben die Java-Leute die gleichen Experimente gemacht, und deshalb sind sie mit 16KB gefahren!
Ist das Problem I / O-gebunden?ch habe mich auch darüber gewundert. Wie viel Zeit wird für den Festplattenzugriff aufgewendet und wie viel für das Knacken von Nummern? Wenn es sich fast ausschließlich um Festplattenzugriff handelt, wie in einem gut unterstützten Kommentar zu einer der vorgeschlagenen Antworten angegeben, können wir nicht viel verbessern, was auch immer wir tun.
Dies ist einfach zu testen, indem der Code mit allen Kommentaren zum Parsen und Knacken von Zahlen ausgeführt wird, die Anzeige jedoch noch intakt ist:
private long sumBinary() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int mul = 1;
long total = 0;
while (lastRead > 0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead - len);
raf.readFully(buf, 0, len);
lastRead -= len;
/*for (int i = len - 1; i >= 0; i--) {
if ((buf[i] >= 48) && (buf[i] <= 57)) {
total += mul * (buf[i] - 48);
mul *= 10;
} else
mul = 1;
}*/
}
raf.close();
return total;
}
Dies läuft jetzt in 3,7 Sekunden! Das sieht für mich nicht I / O-gebunden aus.
Natürlich wird ein Teil der E / A-Geschwindigkeit durch Treffer im Festplatten-Cache verursacht. Aber das ist hier nicht der eigentliche Punkt: Wir benötigen immer noch 20 Sekunden CPU-Zeit (auch mit dem @ von Linux bestätigttime Befehl), der groß genug ist, um ihn zu reduzieren.
Ich hatte in meinem ursprünglichen Beitrag behauptet, dass es einen guten Grund gebe, die Datei eher rückwärts als vorwärts zu scannen. Das habe ich nicht sehr gut erklärt. Die Idee war, dass Sie, wenn Sie eine Nummer vorwärts scannen, den Gesamtwert der gescannten Nummer aufsummieren und dann hinzufügen müssen. Wenn Sie rückwärts scannen, können Sie es bei Bedarf zur kumulierten Gesamtsumme hinzufügen. Mein Unterbewusstsein ergab für sich selbst einen Sinn (worauf später noch näher eingegangen wurde), aber ich hatte einen wichtigen Punkt übersehen, auf den in einer der Antworten hingewiesen wurde: Um rückwärts zu scannen, führte ich zwei Multiplikationen pro Iteration durch, jedoch mit vorwärts scannen Sie brauchen nur eine. Also habe ich eine Forward-Scan-Version programmiert:
private long sumBinaryForward() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
int fileLength = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int acc = 0;
long total = 0;
int read = 0;
while (read < fileLength) {
int len = Math.min(buf.length, fileLength - read);
raf.readFully(buf, 0, len);
read += len;
for (int i = 0; i < len; i++) {
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
total += acc;
acc = 0;
}
}
}
raf.close();
return total;
}
Dies läuft in 20.0 Sekunden, um einiges schneller als die Version mit Rückwärtsabtastung. Nett
Multiplication Cacheährend der Nacht wurde mir jedoch klar, dass es, obwohl ich zwei Multiplikationen pro Iteration durchführte, die Möglichkeit gab, diese Multiplikationen mit einem Cache zu speichern, damit ich sie nicht während der Rückwärtsiteration ausführen musste. Ich war erfreut zu sehen, als ich aufwachte, dass jemand die gleiche Idee hatte!
Der Punkt ist, dass die Zahlen, die wir scannen, höchstens 10 Ziffern und nur 10 mögliche Ziffern enthalten, also nur 100 Möglichkeiten für den Wert einer Ziffer zur kumulierten Summe. Wir können diese vorausberechnen und sie dann im Code für das Rückwärtsscannen verwenden. Das sollte die Vorwärts-Scan-Version übertreffen, denn wir haben die Multiplikationen jetzt vollständig beseitigt. (Beachten Sie, dass dies beim Vorwärtsscannen nicht möglich ist, da die Multiplikation vom Akkumulator ausgeht, der einen Wert von bis zu 10 ^ 9 annehmen kann. Nur im Rückwärtsfall sind beide Operanden auf einige wenige Möglichkeiten beschränkt.)
private long sumBinaryCached() throws IOException {
int mulCache[][] = new int[10][10];
int coeff = 1;
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 10; j++)
mulCache[i][j] = coeff * j;
coeff *= 10;
}
RandomAccessFile raf = new RandomAccessFile(file, "r");
int lastRead = (int) raf.length();
byte buf[] = new byte[16 * 1024];
int mul = 0;
long total = 0;
while (lastRead > 0) {
int len = Math.min(buf.length, lastRead);
raf.seek(lastRead - len);
raf.readFully(buf, 0, len);
lastRead -= len;
for (int i = len - 1; i >= 0; i--) {
if ((buf[i] >= 48) && (buf[i] <= 57))
total += mulCache[mul++][buf[i] - 48];
else
mul = 0;
}
}
raf.close();
return total;
}
Dies läuft in 26,1 Sekunden. Enttäuschend, um es gelinde auszudrücken. Rückwärtslesen ist in Bezug auf E / A weniger effizient, aber wir haben gesehen, dass E / A hier nicht die größten Kopfschmerzen sind. Ich hatte erwartet, dass dies einen großen positiven Unterschied machen würde. Vielleicht ist die Array-Suche genauso teuer wie die von uns ersetzten Multiplikationen. (Ich habe versucht, das Array 16x16 zu machen und Bitverschiebungen zum Indizieren zu verwenden, aber es hat nicht geholfen.)
Sieht so aus, als ob das Vorwärtsscannen dort ist, wo es ist.
Mit einem MappedByteBufferNächstes, was hinzugefügt werden muss, ist einMappedByteBuffer, um zu sehen, ob dies effizienter ist als die Verwendung eines rohenRandomAccessFile. Es muss nicht viel am Code geändert werden.
private long sumBinaryForwardMap() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
byte buf[] = new byte[16 * 1024];
final FileChannel ch = raf.getChannel();
int fileLength = (int) ch.size();
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0,
fileLength);
int acc = 0;
long total = 0;
while (mb.hasRemaining()) {
int len = Math.min(mb.remaining(), buf.length);
mb.get(buf, 0, len);
for (int i = 0; i < len; i++)
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
total += acc;
acc = 0;
}
}
ch.close();
raf.close();
return total;
}
Dies scheint die Dinge ein wenig zu verbessern: Wir sind jetzt bei 19.0 Sekunden. Wir haben eine weitere Sekunde von unserer persönlichen Bestleistung abgezogen!
Was ist mit Multithreading?Eine der vorgeschlagenen Antworten umfasst die Verwendung mehrerer Kerne. Ich schäme mich ein wenig, dass mir das nicht eingefallen ist!
Die Antwort kam für einen Stick, weil angenommen wurde, dass es sich um ein E / A-gebundenes Problem handelt. Dies scheint im Lichte der Ergebnisse zu I / O ein wenig hart zu sein! Auf jeden Fall einen Versuch wert.
Wir machen das mit fork / join. Hier ist eine Klasse, die das Ergebnis einer Berechnung für einen Teil der Datei darstellt, wobei zu berücksichtigen ist, dass sich links möglicherweise ein Teilergebnis befindet (wenn wir auf halber Strecke mit einer Zahl begonnen haben) und rechts ein Teilergebnis (wenn die Puffer auf halbem Weg durch eine Zahl beendet). Die Klasse verfügt auch über eine Methode, mit der wir zwei solcher Ergebnisse zu einem kombinierten Ergebnis für zwei benachbarte Unteraufgaben zusammenfügen können.
private class SumTaskResult {
long subtotal;
int leftPartial;
int leftMulCount;
int rightPartial;
public void append(SumTaskResult rightward) {
subtotal += rightward.subtotal + rightPartial
* rightward.leftMulCount + rightward.leftPartial;
rightPartial = rightward.rightPartial;
}
}
Nun das Schlüsselbit: dasRecursiveTask das berechnet das Ergebnis. Bei kleinen Problemen (weniger als 64 Zeichen) wird @ aufgerufecomputeDirectly(), um das Ergebnis in einem einzelnen Thread zu berechnen; Bei größeren Problemen wird es in zwei Teile geteilt, die beiden Unterprobleme werden in separaten Threads gelöst und die Ergebnisse werden dann kombiniert.
private class SumForkTask extends RecursiveTask<SumTaskResult> {
private byte buf[];
// startPos inclusive, endPos exclusive
private int startPos;
private int endPos;
public SumForkTask(byte buf[], int startPos, int endPos) {
this.buf = buf;
this.startPos = startPos;
this.endPos = endPos;
}
private SumTaskResult computeDirectly() {
SumTaskResult result = new SumTaskResult();
int pos = startPos;
result.leftMulCount = 1;
while ((buf[pos] >= 48) && (buf[pos] <= 57)) {
result.leftPartial = result.leftPartial * 10 + buf[pos] - 48;
result.leftMulCount *= 10;
pos++;
}
int acc = 0;
for (int i = pos; i < endPos; i++)
if ((buf[i] >= 48) && (buf[i] <= 57))
acc = acc * 10 + buf[i] - 48;
else {
result.subtotal += acc;
acc = 0;
}
result.rightPartial = acc;
return result;
}
@Override
protected SumTaskResult compute() {
if (endPos - startPos < 64)
return computeDirectly();
int mid = (endPos + startPos) / 2;
SumForkTask left = new SumForkTask(buf, startPos, mid);
left.fork();
SumForkTask right = new SumForkTask(buf, mid, endPos);
SumTaskResult rRes = right.compute();
SumTaskResult lRes = left.join();
lRes.append(rRes);
return lRes;
}
}
Bitte beachten Sie, dass dies auf einem @ ausgeführt wirbyte[], anstatt das ganzeMappedByteBuffer. Der Grund dafür ist, dass wir den Festplattenzugriff sequenziell halten möchten. Wir werden ziemlich große Stücke nehmen, sie teilen / verbinden und dann zum nächsten Stück übergehen.
Hier ist die Methode, die das macht. Beachten Sie, dass wir die Puffergröße auf 1 MB erhöht haben (früher suboptimal, hier jedoch sinnvoller).
private long sumBinaryForwardMapForked() throws IOException {
RandomAccessFile raf = new RandomAccessFile(file, "r");
ForkJoinPool pool = new ForkJoinPool();
byte buf[] = new byte[1 * 1024 * 1024];
final FileChannel ch = raf.getChannel();
int fileLength = (int) ch.size();
final MappedByteBuffer mb = ch.map(FileChannel.MapMode.READ_ONLY, 0,
fileLength);
SumTaskResult result = new SumTaskResult();
while (mb.hasRemaining()) {
int len = Math.min(mb.remaining(), buf.length);
mb.get(buf, 0, len);
SumForkTask task = new SumForkTask(buf, 0, len);
result.append(pool.invoke(task));
}
ch.close();
raf.close();
pool.shutdown();
return result.subtotal;
}
Nun hier ist die seelenvernichtende Enttäuschung: Dieser gut verarbeitete Code nimmt jetzt 32,2 Sekunden. Warum so langsam? Ich habe eine ganze Weile damit verbracht, dieses Problem zu beheben, vorausgesetzt, ich habe etwas Schreckliches falsch gemacht.
Turns da draußen war nur ein kleiner Tweak nötig. Ich hatte gedacht, die Schwelle von 64 zwischen kleinem und großem Problem sei vernünftig. stellt sich heraus, das war total lächerlich.
Denke darüber so nach. Die Unterprobleme haben genau die gleiche Größe, daher sollten sie praktisch in der gleichen Zeit abgeschlossen sein. Es macht also wirklich keinen Sinn, in mehr Teile aufzuteilen, als Prozessoren zur Verfügung stehen. Auf dem Computer, den ich mit nur zwei Kernen verwende, ist es lächerlich, auf einen Schwellenwert von 64 zu sinken: Es erhöht nur den Overhead.
Jetzt wollen Sie die Dinge nicht einschränken, sodass nur zwei Kerne verwendet werden, auch wenn mehr verfügbar sind. Vielleicht ist es das Richtige, die Anzahl der Prozessoren zur Laufzeit herauszufinden und in so viele Teile aufzuteilen.
Wenn ich den Schwellenwert auf 512 KB (die Hälfte der Puffergröße) ändere, wird er jetzt in @ abgeschlosse 13,3 Sekunden. Wenn 128 KB oder 64 KB verwendet werden, können mehr Kerne verwendet werden (bis zu 8 bzw. 16), und die Laufzeit wird nicht wesentlich beeinflusst.
So Multithreading does einen großen Unterschied machen.
Es war eine ziemlich lange Reise, aber wir haben mit etwas angefangen, das 92,9 Sekunden gedauert hat und jetzt sind wir auf 13,3 Sekunden gesunken ... das istseven mal die Geschwindigkeit des ursprünglichen Codes. Und das nicht durch die Verbesserung der asymptotischen (Big-Oh) Zeitkomplexität, die von Anfang an linear (optimal) war ... es ging nur darum, den konstanten Faktor zu verbessern.
Ein guter Tag Arbeit.
Ich nehme an, ich sollte als nächstes versuchen, die GPU zu verwenden ...
Postscript: Erzeugen der ZufallszahlendateiIch habe die Zufallszahlen mit dem folgenden Code generiert, den ich ausgeführt und in eine Datei umgeleitet habe. Natürlich kann ich nicht garantieren, dass Sie genau die gleichen Zufallszahlen erhalten, die ich hatte:)
public static void genRandoms() {
Random r = new Random();
for (int i = 0; i < 100000000; i++)
System.out.println(r.nextInt(1000000000));
}