Input/Output Schneller Sort mit wenigen Zugriffen (oder was anderes?)

[Bernd Hohmann]

Ich habe hier ein Performanceproblem in meinem Objectcache (einfach Objekte serialisieren und in ein RandomAccessFile werfen - die Liste mit Pointer und Länge der Chunks werden im Speicher verwaltet).

Die Engine bietet an, den Cache zu sortieren. Das ist im Moment so gelöst, dass die Cacheobjekte "Comparable" implementieren. Für den Quick-Sort wird nun der Chunk von Platte gelesen, deserialisiert, compareTo(..) ausgeführt und entsprechend der Index in der Chunkliste getauscht.

Im konkreten Fall muss eine Bilderliste nach Datum (long) sortiert werden, die Chunks sind 10-40MB gross - entsprechend lahm ist der Sort.

Die eine Variante wäre, dass ich mir mein eigenes Comparable definiere wo zusätzlich verlangt wird dass der Chunk den zu vergleichenden Wert zurückgibt. Dann könnte mir den Wert bei beim .add(Object value) abgreifen und für den Sort zwischenspeichern.

Die andere Variante wäre ein Sort, der mit möglichst wenigen Zugriffen auskommt und sich ggf. Zwischenergebnisse merken kann (ich meine mal von sowas gehört zu haben).

Stand schonmal jemand vor diesem Problem oder hat eine näherungsweise Lösung?

bernd

 

[Ark]

Interessanterweise stehe ich momentan vor einem ähnlichen Problem. Leider bin ich da noch unschlüssig, ob ein fertiges Datenbanksystem nutzen sollte oder eine Eigenentwicklung meine Anforderungen besser erfüllt.

Aber mal zu deinem Problem, ganz konkret: Spricht was dagegen, die Datumsangaben zusammen mit den dazugehörigen Pointern im Arbeitsspeicher mitzuführen? Also etwa: ein long[]-Array d mit den Datumsangaben und ein long[]-Array p mit den Pointern zu den Objekten, wobei jedes d das Datum zum Objekt ist, auf das p zeigt?

Ark

 

[Bernd Hohmann]

Aber mal zu deinem Problem, ganz konkret: Spricht was dagegen, die Datumsangaben zusammen mit den dazugehörigen Pointern im Arbeitsspeicher mitzuführen? Also etwa: ein long[]-Array d mit den Datumsangaben und ein long[]-Array p mit den Pointern zu den Objekten, wobei jedes d das Datum zum Objekt ist, auf das p zeigt?

Da spricht nur dagegen, dass ich ein anderes Comparable Interface brauche - nämlich eines, was den Vergleichswert abgreifen lässt. Wenn es sich nicht vermeiden lässt, mache ich das so.

Der Source für meinen ObjectCache fliegt hier im Forum herum (werde ich gelegentlich mal aktualisieren), ein anderer Kollege hatte ein ähnliches Projekt in dem Thread angesprochen - da hättest Du schonmal was zum abschreiben.

Bernd

 

[Bernd Hohmann]

Ark,

hat sich im ersten Coding-Ansatz als "Problembehaftet" gezeigt als ich das mal mit Strings testen wollte. Da ist ja der Vergleich nicht so trivial wie bei einem long/int etc.. und ich muss den String zum Vergleichen im Speicher halten.

Als ich das mit 50GB Texten probierte tats einfach nur noch einen dumpfen Knall *fg*.

Bernd