ein spezielles Byte-Array sortieren

[beurk]

Hallo,

ich hab ein leicht verzwicktes Problem und möglicherweise kann mir jemand von euch helfen.
Ich hab eine Datei mit ca. 1.5 Mio. Ints bzw. 4-mal so vielen Bytes drin. Diese lese ich mittels InputStream in ein entsprechend großes Byte-array (die Größen sind vorher bekannt und daher kein Problem) ein.

Das eigentliche Problem besteht jetzt darin, dieses array zu sortieren und dabei soll der Inhalt als Integer interpretiert werden und nicht als Byte! Die Umwandlung in ein Int-Array ist aus Performancegründen und weil der Speicher begrenzt ist nicht möglich (Beides passt nicht gleichzeitig auf den Heap).

Nun meine 3 Lösungansätze:

1. Irgendwie (??) das 1-dimensionale byte-array auf ein byte[][4] casten. Ich schätze mal, dass es nicht möglich ist, aber vielleicht geht's ja doch Danach könnte ich locker Array.sort verwenden und einen simplen Comparator dazu erstellen.

2. Eine eigene Sortierfunktion schreiben. QuickSort und Konsorten sind bekannt, aber ich bezweifle, dass ich alle Tricks kenne um die gleiche Performance wie Array.sort zu erreichen.

3. Die Daten anders einlesen und direkt ein byte[][4] oder int[] Array erhalten. (Performance ist sehr wichtig!)


Was denkt ihr? (Ich tendiere wegen Unkenntnis für 1. und 3. zu Lösung 2)

 

[Der Müde Joe]

Arrays.sort (items, new Comparator<Byte>(){

            public int compare(Byte o1, Byte o2) {

                return XXmyCompareMethodXX;

               }});

was spricht dagegen?

 

[Guest]

Wie sag ich der sort-Methode , dass er nicht alle Bytes sondern nur 4er-Blöcke von Bytes (also Ints) vergleichen soll?

 

[Der Müde Joe]

so geht das nicht....

wrapper zb der immer 4 Bytes buschelt... und dann Wrapper comparen

oder direkt ein int einlesen (wohl in dem Fall am besten)

 

[SlaterB]

> Die Daten anders einlesen und direkt ein byte[][4] oder int[] Array erhalten.

wenn dir das int-Array als Möglichkeit offen steht, warum machst du es dann nicht?
das ist doch in jeder (bisher zu sehener) Hinsicht das beste,

ansonsten würde ich mir an deiner Stelle über die Geschwindigkeit eines eigenen Algoritmus nicht allzuviele Sorgen machen,
sofern die einen n log n-Algorithmus benutzt und allgemeine Fehler auslässt, kannst du nicht wesentlich langsamer werden als Arrays.sort,
und wenn der Speicher das Manko ist, ist doch meist Rechenzeit weniger wichtig?

 

[Gast]

Das war mehr als Frage gedacht, wie man schnell das Ganze in ein int-Array einliest...

Wenn ich wüsste wie das geht, hätte ich das ja direkt so gemacht. Da aber die Standard-Input-Methoden nur auf Byte-Arrays basieren habe ich halt die benutzt.

 

[Der Müde Joe]

stell sich die Frage, was bei dir ein byte darstellt???

zb... ein byte nehmen
zum int adden
dann int um 8 stellen verschieben (mit << 8)
byte 2 adden
8....etc

 

[beurk]

Mir ist durchaus klar, wie ich aus meinen Bytes einen Int mache, aber ich kann das nirgendswo speichern. Also muss ich es direkt so sortieren, passend casten oder gleich im richtigen Format einlesen.

 

[Der Müde Joe]

lies 4 bytes ein.... ( 32 bit)

mach die operation toInt()

ins int array

und das ganze solange, bis alles eingelesen ist

 

[SlaterB]

oder einen DataInputReader benutzen und direkt ints lesen,
wobei natürlich noch gar nicht näher geklärt ist, was 'einlesen' genau bedeutet

 

[Guest]

lies 4 bytes ein.... ( 32 bit)

mach die operation toInt()

ins int array

und das ganze solange, bis alles eingelesen ist

Das dauert ewig. Kannst du ja mal testen.

oder einen DataInputReader benutzen und direkt ints lesen,
wobei natürlich noch gar nicht näher geklärt ist, was 'einlesen' genau bedeutet

Einlesen == Datei auf Festplatte komplett in den Hauptspeicher kopieren.
...und DataInputReader mit readInt() ist äquivalent zu der Lösung vom müden Joe.

 

[SlaterB]

wenn es langsam ist, dann wahrscheinlich weil du immer 4 Bytes einzeln liest,
da musst du natürlich auf 10000 und noch viel höher erhöhen,

ob es direkt mit DataInputStream geht weiß ich nicht
(z.B. BufferedInputStream dazwischenschalten, oder direkt BufferedInputStream, da gibts ja auch paar read()-Operationen),
aber wenn nicht, dann ist die kleine toInt()-Operation ja kein Beinbruch,