ich hab ne relativ einfache Aufgabe bekommen. Wir haben eine Datei vorliegen die 500.000.001 32Bit Integers binär abgespeichert hat. Die 32Bit Integers sind signed und in little endian kodiert.
Die Aufgabe besteht nun daraus die Datei auszulesen und die Integers auf der Konsole aufsteigend sortiert aufzulisten.
An sich ist die Umsetzung easy. Es hängt allerdings an der schieren Menge der Daten. Im Moment nutze ich eine ArrayList von 500.000.001 länge. Dafür alleine will die VM schon 4GB Heap :twisted: Natürlich wärs furchtbar das erst im nachhinein zu sortieren. Daher dachte ich mir, ich sortier die neu eingelesene Zahl direkt an die passende stelle ein. Das läuft noch über brute force, die liste langgehen und schauen wanns zu groß wird. Da kann man eventuell noch was machen aber auf die schnelle fiel mir nichts ein.
Meine Frage ist nun, denn das Prog brauch ewig
Wie würdet ihr da ungefähr rangehen? Wäre es sinnvoll etwas zwischen zu speichern? Vielleicht sogar ganz abstruse ideen zu haben und das ganze auf multithreading auszubauen?
Mich stört auch dass ich hier schon mit relativ hohem JVM Heapspace hantieren muss
Die Aufgabe ist eigentlich auch in C gestellt aber man darf die Programmiersprache benutzen, die man möchte. Und ich bin eigentlich nen Java verfechter
Also was meint ihr. Vielleicht fällt euch ja ein Stichwort ein das mir schon hilft.
Vielen Dank schon mal und liebe Wochenendgrüße
Highchiller
ArrayList ist nicht speichereffizient genug, ein Integer-Objekt verbraucht leider ca. das dreifache eines int. Da du anscheinend genug RAM zur Verfügung hast sollte ein Array von ints möglich sein und weniger Speicher verbrauchen. Für das Sortieren selbst nimmst du dann einen in-place Sortieralgorithmus, so dass kein weiterer Speicher benötigt wird. Das wäre die einfachste Variante.
Die etwas spannendere Variante ist, dass du dich über externe Sortieralgorithmen informierst, davon einen implementierst und später vll. sogar noch parallelisierst. Ein gutes Beispiel dafür wäre das externe Mergesort. Da es sich um int’s handelt kann man die Blöcke dann auch mit Radixsort im Speicher sortieren und spart sich einige Abstiege.
Falls nicht, oder dem keine Beachtung geschenkt werden soll, dann einfach BitSet verwenden und den intwert setzen.
Alternativ ein Booleanarray und nur die Zahlen setzen.
Falls es doppelte Einträge gibt, dann einfach ein int-array nehmen und jetzt nicht die ints eintragen, sondern den index verwenden und hochzählen wie oft dieser int vorkommt.
int[] values = new int[Integer.MAX_VALUE];
public void set(int i) {
values[i - Integer.MIN_VALUE] = values[i - Integer.MIN_VALUE] + 1;
}
public void ausgabe() {
for(int i = 0; i< values.length; i++) {
for(int j = 0; j < values** ; j++) {
System.out.println(i + Integer.Min_VALUE);
}
}
}```
Das ganze jetzt noch auf die Grenzen überprüfen und gut ist. Also was passiert wenn man Integer.MIN_VALUE setzt. Was passiert wenn man Integer.MAX_VALUE setzt, etc.
Mir stellt sich bei solchen Aufgabe immer die Frage : praktisches Beispiel ?
Klar, als Übungsaufgabe durch aus mal ne Herausforderung wenn man die physischen Limits des Systems geht, aber es gibt für so einen Schwachsinn keinen praktischen Anwendungsfall. Wenn ich so riesige Daten habe die ich sortieren soll dann mach ich das Ganze natürlich Stück für Stück und nicht sinnfrei alles auf Einmal, denn ich tätige ja auch die Ausgabe Stück für Stück, und plotte nicht auf einmal ALLES aus.
Man sollte das eher mal andersrum anmerken : wer so einen Blödsinn vorhat hat defintiv ein extrem schweren Fehler in seinem Design, denn es macht schlicht keine Sinn (und ist in meinen Augen auch einfach falsch) ALLE Daten IMMER im Speicher zu haben obwohl man nur mit einem Bruchteil davon gerade wirklich arbeitet (weil man auch nur ein Bruchteil gleichzeitig verarbeiten KANN).
Wie gesagt : theoretisch zwar vielleicht wichtig zu wissen, in der Praxis aber völlig daneben da man bei so großen Datenmengen einfach nur noch seriell arbeiten kann.
o.O? Wenn der Speicher da ist, und keine bedeutsamen Beschränkungen vorliegen kann er auch verwendet werden, es wäre unökonomisch das nicht zu tun. Und du darfst dir sehr sicher sein das in der Praxis mit noch viel größeren Datenmengen nicht sequentiell gearbeitet wird (Google, Yahoo, etc.). Da heisst es dann verteilte Systeme etc. Und nur um dir einen kleinen Überblick bzgl. des Sortierens zu geben und was da so aufgefahren wird http://sortbenchmark.org/
Selbst wenn man sich solche riesigen Clouds wie Amazon, Google, Yahoo oder wie sie nicht alle heißen nimmt glaube ich kaum das selbst diese Kapazitäten auch nur ansatzweise dazu ausreichen ALLE Daten die auf den Platten liegen GLEICHZEITIG im RAM zu bearbeiten, von den geeigneten Algorithmen mal abgesehen.
Schon alleine wenn man folgendes Beispiel über-extremieren würde : Vergleich von 4 Strings : A->B , A->C , A->D , B->C , B->D , C->D. Das kann man schon parallelisieren, und sicher auch optimieren, aber irgendwann hat man schlicht mehr mögliche Strings die man miteinander vergleichen muss als halt durch das System gleichzeitig verarbeiten kann und damit gezwungen wird letzten Endes sequentiell zu arbeiten. Du sprichst von “in der Praxis mit noch viel größeren Datenmengen” ? Scheinbar noch nicht groß genug.
Man kann bei sowas beliebig weit gehen ( http://sortbenchmark.org/ ). Einerseits könnte man sagen: Nimm einen int[]-Array, dann passt’s. Aber man muss wohl davon ausgehen, dass es gerade darum ging, ein Beispiel zu finden, wo man NICHT mehr alle Daten im Speicher halten kann (oder es zu Übungszwecken nicht tut, selbst wenn man es notfalls könnte). Da gibt’s sicher ein bißchen Literatur dazu, müßte ich jetzt aber auch erst suchen…
ich denke auch, dass die Aufgabe absichtlich so gestellt ist, dass es unmöglich ist, alle Daten im Arbeitsspeicher zu halten.
Den Trick dazu kannten schon die alten Römer: “Teile und herrsche”.
Du liest immer nur so viele Daten ein, wie du bequem im Arbeitsspeicher sortieren kannst, und schreibst sie sortiert in jeweils eine Datei. Du könntest beispielsweise jeweils 50.000 Zahlen einlesen, sie sortieren und sie in 10.000 Dateien (mit jeweils 50.000 Daten) schreiben (die letzte “1” ignoriere ich hier - sie ist lästig, ändert aber nichts am Prinzip).
Im nächsten Schritt öffnest du beispielsweise 1.000 mal jeweils 10 (sortierte) Dateien und liest die Zahlen einzeln ein. Die kleinste Zahl aus den 10 Input-Streams schreibst du in eine Datei, bis alle Input-Streams leer sind. Anschließend hast du nur noch 1.000 sortierte Dateien mit jeweils 500.000 Daten.
Wenn du den zweiten Schritt noch einmal durchführst, erhälst du 100 Dateien mit jeweils 5.000.000 Daten,
nach dem nächsten Schritt 10 Dateien mit 50.000.000 Daten,
und nach einem letzten Schritt 1 Datei mit 500.000.000 Daten.
Mit einem solchen Verfahren, kannst du (fast) beliebige Mengen an Daten sortieren (das Problem besteht zumindest nicht mehr in der Größe des Arbeitsspeichers, sondern in der Größe der Festplatte).
Zum Suchen im Internet (weil meine Erklärung möglicherweise nicht verständlich ist) empfehle ich dir den Begriff “Mergesort”.
Du hast 10 Dateien mit jeweils 1000 Elementen/Daten, sortiert.
Dann läuft die innere Schleife von 0 bis 9.
Du wählst das kleinste elem aus, bis alle elem aus den 10 Dateien ausgewählt sind.
Binär (nur 2 Dateien) wäre das etwas einfacher.
Die Grenze der Kapazität wäre hier die Hdd.
Was kann man denn dafür nehmen?, QuickSor Merge Counting RadixSor oder so (divide an’). Grüße.
Edit: Die Römer wussten das noch nicht, SortAlgos gibt es noch nicht so lange.
Also wenn keine Doppelten in der Datei vorkommen, dann ist das BitSet (wie Unregistered schon anmerkte) die erste Wahl (@Unregistered: ein boolean-Array aber ist NIE EINE WAHL! ;)). Ansonsten muss man ja nicht den Heap der VM verwursten, man kann auch normalen Hauptspeicher nehmen, nämlich mit DirectBuffern. Bei diesen kann man zurnot auch die Ausgabe anpassen, wenn die Date z.B. mit Big_Endian gelesen wird.
import java.io.File;
import java.io.FileInputStream;
import java.nio.ByteBuffer;
import java.nio.IntBuffer;
public class IntSort {
public static void main(String[] args) throws Throwable {
File f = new File("./testfile.dat");
DataInputStream din = new DataInputStream(new FileInputStream(f));
int read, count;
IntBuffer list = ByteBuffer.allocateDirect((int) f.length()).asIntBuffer();
while(din.available() >= 4) {
read = din.readInt();
count = list.get(read);
count++;
list.put(read, count);
}
din.close();
for(;list.position() < list.capacity();) {
read = list.position();
for(count = list.get(); count > 0; count--) {
System.out.println(read);
}
}
}
}```
Analog zu DirectBuffern, lässt sich auch ein RandomAccessFile verwenden, wenn man entweder überhaupt keinen Speicher belasten will oder die Menge ausserhalb des Int-Bereichs liegt. RandomAccessFile geht dann natürlich merklich langsamer.
@ThreadPool :
Ich will ja nicht meckern, aber da solltest du mal etwas genauer lesen. Für boolean-Arrays werden nach wie vor 8 Bit pro boolean verwurstet.
In Oracle’s Java Virtual Machine implementation, boolean arrays in the Java programming language are encoded as Java Virtual Machine byte arrays, using 8 bits per boolean element.
[QUOTE=Spacerat]@ThreadPool :
Ich will ja nicht meckern, aber da solltest du mal etwas genauer lesen. Für boolean-Arrays werden nach wie vor 8 Bit pro boolean verwurstet.[/QUOTE]
Ja, das erwähnte ich, danke für die Wiederholung. Worauf ich hinweisen wollte ist die Tatsache das boolean-Arrays von JVM zu JVM unterschiedlich implementiert werden dürfen, es also auch gepackte Varianten geben darf. Ein boolean Array kann also eine Wahl sein. Ich habe also ein valides Gegenbeispiel gefunden das dein absolutes Argument “boolean Arrays sind nie eine Wahl” entkräftet. Darum ging es mir.
Die 8-Bit Variante der Oracle-JVM kann auch eine Wahl sein, da boolean-Arrays extrem einfach zu verwenden sind und direkt von der Sprache unterstützt werden. Für Indexierungen oberhalb von ein paar Millionen Elementen verwende auch ich Bitsets/Bitarrays aber dann je nach Form der Daten die intelligente bzw. dumme Variante. Zur letzeren gehört das Java-BitSet/BitArray.
[OT][QUOTE=ThreadPool]Ja, das erwähnte ich, danke für die Wiederholung. Worauf ich hinweisen wollte ist die Tatsache das boolean-Arrays von JVM zu JVM unterschiedlich implementiert werden dürfen, es also auch gepackte Varianten geben darf. Ein boolean Array kann also eine Wahl sein. Ich habe also ein valides Gegenbeispiel gefunden das dein absolutes Argument “boolean Arrays sind nie eine Wahl” entkräftet. Darum ging es mir.[/QUOTE]In keiner bekannten JVM ist ein boolean-Array-Element kürzer als 8 Bit, also stets mindestens ein Byte! Weil dem so ist, gibt es die Klasse BitSet, die dafür den von dir erwähnten Pack-Mechanismus bereit stellt. In keiner JVM hat ein boolean-Array-Element also jemals genau ein Bit, wie es sein sollte. Ein boolean-Array ist deswegen nie eine Alternative, nicht heute, nicht morgen, nicht irgendwann. Deine Posts entkräften meine Aussage also keineswegs.[/OT]
Problem: Nicht jede Jvm legt ein boolean-Array speicherschonend (dafür etwas langsamer) an, d.h., wer darauf setzt, entwickelt nicht plattformunabhängig, und das sollte es schon sein. Spezielle Jvms. Space hat recht, es stimmt, was er sagt.
Aber was hat das mit Sortieren zu tun? Indices?
du meine Güte, ich hab nach den ersten 2 Posts erst mal das umgesetzt und bissl probiert und es jetzt gut hinbekommen. Dann hatte ich nicht weiter rein geschaut.
Also, weil die Diskussion wohl doch ganz interessant zu sein scheint.
Hier mal die Aufgabe im Original:
**The file ndata.dat should then contain 500.000.001 numbers, binary stored as signed little endian 32 bit integers. The first number is 123456789.
Reads in the numbers from ndata.dat.
Prints the numbers, starting from 0, in increasing order, each number at most once, ASCII representation, one number per line, no leading zeros or spaces, lines ended by a single newline.**
Ich hab mir die Ausgabe auf der Konsole gespart und eine Datei stattdessen geschrieben.
Meine Lösung:
BitSet numbers = new BitSet(Integer.MAX_VALUE);
// try to read from file
try ( InputStream in = Files.newInputStream(
Paths.get(args[0]),
StandardOpenOption.READ)
) {
byte[] buffer = new byte[4*2048];
int readed = in.read(buffer);
while ( readed > 0 ){
for ( int i = 0; i < readed-4; i = i+4 ){
byte[] num = new byte[]{buffer**,buffer[i+1],buffer[i+2],buffer[i+3]};
int j = ByteBuffer.wrap(num).order(ByteOrder.LITTLE_ENDIAN).getInt();
if ( j < 0 ) continue; // ignore negative entries
numbers.set(j);
}
readed = in.read(buffer);
}
} catch (IOException e) {
e.printStackTrace();
return;
}
// create an output file
File outputFile = Paths.get(args[0]).getParent().resolve("output.txt").toFile();
if ( outputFile.exists() ) outputFile.delete();
try {
outputFile.createNewFile();
} catch (IOException e1) {
System.err.println("Cannot create an output file.");
e1.printStackTrace();
return;
}
// use an OutputStreamWriter to define encoding
try ( Writer out = new BufferedWriter( new OutputStreamWriter( new FileOutputStream(outputFile.getAbsoluteFile()), "US-ASCII" ) ) ) {
// prints all true bits, nextSetBit(i) returns -1 if there are no more true bits after i
for ( int i = numbers.nextSetBit(0); i >= 0; i = numbers.nextSetBit(i+1) )
out.write(i + "
");
out.flush();
System.out.println("Finished after " + (System.currentTimeMillis()-start) + "ms.");
} catch (IOException e) { // catch exceptions
System.err.println("Cannot write to output file: " + e.getMessage());
e.printStackTrace();
}
}```
Das läuft insgesamt in ungefähr 80Sekunden durch. Jetzt könnte man noch das einlesen (dauer 21Sekunden) parallelisieren, aber das lohnt nicht denk ich. Die output.txt ist am Ende knapp 4,6GB groß... ich wüsste nicht wie ich das noch schneller schreiben könnte. Zumal ja dann auch irgendwann die Platte nich hinterher kommt (wobei bei der getesteten SSD mit 300MB/s schreibgeschwindigkeit noch luft sein sollte).
Es geht also nicht darum doppelte Einträge zu berücksichtigen. Und selbst wenn denke ich es wäre besser sich multi-hits anderweitig zu merken als Listen anzulegen. Der Aufwand (Zeit UND Speicher) ist einfach exorbitant im vergleich zu dieser Variante...
Vielen Dank für die rege Anteilname, falls ihr noch weitere verbesserungsvorschläge habt, immer her damit. Ich bin gierig darauf zu erfahren wie man etwas in Java noch schneller bekommt :) Und/oder Speicherärmer verwaltet.
PS: @Sen-Mithrarin
Ich finde die Diskussion über den Sinn und Zweck dieser Übung für äußerst unpraktisch. Die Aufgabe ist nun mal gestellt, nimms doch hin. Ob das nun Sinnvoll ist oder nicht spielt doch absolut keine Rolle für diesen Thread. Außerdem hat Marco13 völlig Recht. Wenn es nun mal darum geht jemanden daran zu hindern den typischen/ineffizienten weg zu gehen, hat die Aufgabe doch genau das erreicht.
Werd’s mir vielleicht mal ansehen, aber nebenbei: Lese/Schreiboperationen zu parallelisieren hat leicht den Effekt, dass die Verarbeitung langsamer wird: Bei einer Platte muss der Lesekopf dann wie blöd hin-und-her hüpfen. Und auch bei einer SSD ist sequentielles lesen ggf. deutlich schneller, als “random access” (habe mal was gelesen, was grob nach Faktor 4 aussah, aber das hängt von etlichen Faktoren ab, und kann nur ein Daumenwert sein)
Also so effizient kann diese Lösung auch nicht sein, ganz einfach, weil “new byte[]” (Zeile 14) und “ByteBuffer.wrap()” ziemlich viel Datenmüll für den GC produzieren (ok, ab Java 1.7 uninteressant). Und wie das mit BitSet funktioniert, dürfte spätestens jetzt auch geklärt sein.
int j, i;
while ( readed > 0 ){
for(i = 0; i < readed-4; i+=4) {
// EINES von BEIDEN! (Welches ist wohl LittleEndian?)
j = (buffer** << 24) | ((buffer[i + 1] & 0xFF) << 16) | ((buffer[i + 2] & 0xFF) << 8) | (buffer[i + 3] & 0xFF);
// j = (buffer[i + 3] << 24) | ((buffer[i + 2] & 0xFF) << 16) | ((buffer[i + 1] & 0xFF) << 8) | (buffer** & 0xFF);
//
if ( j < 0 ) continue; // ignore negative entries
numbers.set(j);
}
readed = in.read(buffer);
}```
Was die Parallelisierung von Schreib-/Lesezugriffen angeht... solange du keinen anständigen Raid-Controller mit genügend Festplatten hast, macht das wenig Sinn, wie Marco13 schon gesagt hat. Ohne Raid werden die Schreibzugriffe nämlich per Hardwareeinschränkung wieder serialisiert, sodass ein Thread immer auf den anderen warten muss. Wenn du das Befüllen einer Datei mit z.B. berechneten Werten parallelisieren willst, dann solltest du dies per Chaches machen.
Schneller gehts jetzt wohl nur noch wenn man die Ausgabe optimiert. Dies könnte damit geschehen, indem man statt BufferedWriter und "write(i + "
")" PrintStream und "println(i)" verwendet.
BTW.: Zeile 38 ist überhaupt ein hübsches Beispiel für ein krasses Foulspiel beim proggen. Warum wird dort der OutputStreamWriter noch in ein BufferedWriter geschachtelt, wenn man am Ende eh nur auf die Writer-Methoden scharf ist?
@Marco13
Stimmt daran hatte ich gar nicht gedacht. @Spacerat
Darf ich Fragen wieso das ab Java 1.7 uninteressant ist?
Schreibt println(“i”) unter Windows nicht nen
\r? Laut Aufgabe darf ich nur ein Zeichen pro Zeilenumbruch benutzen. Wäre das dann trotzdem schneller?
Und das Foulspiel, tja das kann ich auch nicht genau erklären, ich hatte die Verschachtelung irgendwo gesehen als ich nach schneller Ausgabe gegooglet hatte.
