Assoziatives Datenfeld, schneller wie Hashmap

[leon_20v]

Hallo Zusammen,

ich habe sehr sehr viele Datenpunkte in einer LinkedHashmap, da ich immer x und y werte habe.

Die x Werte sind aufsteigend sortiert.

Ich frage mich gerade ob ich mit einem guten Suchalgorithmus wie divide and conquer oder einer eigenen Hashmap implementierung nicht schneller auf werte zugreifen kann?


Oder ist die LinkedHashMap von Java schon so optimiert, dass ich mir die Zähne ausbeisen werde?


Bsp.
Sagen wir im Array sind die Werte 10, 16, 21, 27. Jetzt such ich den Wert 20, dann hätte ich den inde von 16 zurück gegeben.

 

[nvidia]

Wieviel ist denn "sehr sehr viel" bei dir? Die Entwickler der Standardbibliothek geben sich schon Mühe nicht den langsamsten Kram zu implementieren. Vll. schreibst du mehr zu deinem Anwendungsfall? Kannst du den Wertevorrat und Definitionsbereich eingrenzen? Arbeitest du nur mit primitiven Werten? Falls ja wären Bibliotheken wie https://bitbucket.org/robeden/trove oder HPPC: High Performance Primitive Collections for Java geeigneter. Bei Java und "schnell" geht es in den meisten Fällen darum den Memoryfootprint so klein wie möglich zu halten.

 

[Ruzmanz]

Bei X/Y-Koordinaten ist ein Array am schnellsten, sofern es um die Lese- und Schreibzugriffe geht und der Speicherverbrauch egal ist.

 

[Bahare]

Hallo,

Ich weiß das hat nichts mit dem Thema zu tun, aber ich wollte fragen ob mir jemand bei einem Übungsblatt helfen könnte. Natürlich gegen Entschädigung. Wer Interesse hat soll mir eine pn schreiben.

 

[knilch]

Hi,

Hallo,
Ich weiß das hat nichts mit dem Thema zu tun, aber ich wollte fragen ob mir jemand bei einem Übungsblatt helfen könnte. Natürlich gegen Entschädigung. Wer Interesse hat soll mir eine pn schreiben.

Wie du schon schreibst, hat das nichts mit dem ursprünglichen Thread zu tun, darum... einen neuen Thread erstellen und dein Anliegen dort posten!

 

[leon_20v]

Entschuldigung für die späte Antwort, ich steck mitten in der BA und das ist schrecklich.

Wieviele Punkte es genau sind, kann ich nicht sagen. Es können innerhalb einer Sekunde 10 Punkte sein, es können aber auch soviel sein wie die CPU schafft (glaub das waren mal 16000).

Die Punkte werden irgendwann auch Serialisiert und entfernt. Das muss der GC alles wegräumen und macht Stop-The-World für 50ms. Das ist absolut unpassend ;(

Habe mir schon überlegt, dass ich mir die toten Objekte aufhebe und diese wiederverwende. Dadurch hat der GC keine Arbeit mehr.

Jetzt stellt sich aber die Frage, ob ich die LinkedHashMap auch wiederverwenden kann, denn diese Hat ja auch n haufen overhead? (before, after, hashwerte usw) Die Frage ist ob das nicht auch nen Stop-the-World effekt verursacht, wenn er die Map wegräumt.

 

[leon_20v]

hmm ich muss irgendwas unternehmen, wenn ich die daten mal 20 multipliziere (was durchaus ein Anwendungsfall ist) kommt der GC garnimmer nach und muss alle 2-3 sekunden für 400ms die Welt anhalen.

 

[nvidia]

Gib dem Programm halt genug Speicher. Aber ohne konkrete Ansagen, bzw. Code oder irgendwas zum Experimentieren wird hier nicht viel rauskommen.

 

[DrZoidberg]

Wenn es so effizient wie möglich sein soll, erstelle zwei Arrays. Eins für die x Werte und eins für die y Werte.
Dann verwendest du java.util.Arrays.binarySearch um einen bestimmten Wert zu finden.
Handelt es sich dabei um double/float Werte?

In jedem Fall sollte dein Rechner sehr viel mehr als 16000 Punkte pro Sekunde schaffen. 100 Millionen müssten schon drin sein bei einem double Array.

 

[leon_20v]

Danke für deine Antwort, die werte sind sortiert, da könnte binarySearch wirklich schneller sein als ein Zugriff auf die HashMap. Dadurch muss ich halt nicht hashen.


Ich hab aber aktuell ein vieeeel größeres Problem. Die Garbage Collection haut immer mega Pausen rein. Manchmal sogar 100ms. Das ist unerträglich.

Leider kann ich keinen Code posten.

Es ist einfach so, ich hab eine Map mit Punkten. Ich hole alle Punkte aus der Map und schreib sie auf die Platte und Speicher die Map in einem Array (FIFO) zwischen. Wenn das Array voll ist und ein neuer Eintrag hinzukommt, fliegt immer der erste Eintrag raus. Ein neuer Eintrag kommt alle 5sekunden dem Array hinzu.

Wenn ein Eintrag dann aus dem Array raus fliegt, muss die Map von der Garbage Collection aufgeräumt werden. Dies verursacht Mega lücken. Ich weiß nicht wie dich das Problem in den griff bekommen soll. Alle möglichkeiten die GC einzustellen sind fehlgeschlagen.


Angelika Langer beschreibt unter Pausen genau mein Problem:
AngelikaLanger.com - Garbage Collection Tuning - Die Ziele - Angelika Langer Training/Consulting

Ich weiß aber nicht wie ich das bei mir lösen soll, da ich einfach sehr unterschiedliche Mengen an Punkten habe.

 

[Phash]

Evtl die punkte in eine in memiry db auslagern?
Oder die map größer Initialisieren

 

[leon_20v]

wie größer initalisieren? was meinst du damit?


was ist memiry db? eine datenbank?

 

[Phash]

mein Tablett hat mich falsch verstanden, sorry

ich meinte eine in-Memory Datenbank sowas wie Derby In-Memory-Datenbank ? Wikipedia

beim erweitern von Collections wird die Collection verdoppelt und alle Referenzen werden rüberkopiert, die alte Collection wird verworfen.
Wenn du die Collection von Anfang an größer machst, musst du seltener kopieren

List<Eier> eier = new ArrayList<Eier>(50000); (hier ist gleich Platz für 50000 Einträge)

 

[leon_20v]

Gegen die Datenbank ist mein Chef komplett dagegen. Das hatte ich ihm auch schon vorgeschlagen. Er meinte nur das wurde schonmal gemacht und das war viel zu langsam.

naja mit dem größermachen hab ich kein problem, da ich ja eine LinkedHashMap benutze.Ich hab eher beim kleinermachen das problem wenn ich die mpas wiederverwenden möchte...

 

[Phash]

Datenbank zu langsam? oO


warum willst du die maps wiederverwenden?
btw. nutz doch mal jvisualvm.exe aus deinem jdk/bin ordner, und verbinde dich auf deine JVM, während dein Programm läuft.
Dann siehst du, wo Speicher und Zeit verbraten werden

 

[DrZoidberg]

Versuchs mal mit nem Ringbuffer.

public class RingBuffer {
  private int index = 0;
  private int length = 0;
  private final double[] arrayX, arrayY;
  private double lastX, lastY;
  
  RingBuffer(int size) {
    arrayX = new double[size];
    arrayY = new double[size];
  }
  
  public void add(double x, double y) {
    if(length > 0 && x < lastX) throw new RuntimeException("X Werte sind nicht sortiert");
    arrayX[index++] = lastX = x;
    arrayY[index++] = lastY = y;
    if(length < arrayX.length) length++;
    if(index >= arrayX.length) index = 0;
  }
  
  public int findIndexOfX(int x) {
    int end = Math.min(index+length, arrayX.length);
    int end2 = index + length - arrayX.length;
    int i = Arrays.binarySearch(arrayX, index, end, x);
    if(i < 0 && end2 > 0) {
      i = Arrays.binarySearch(arrayX, 0, end2, x);
    }
    return i;
  }
}

 

[leon_20v]

RingBuffer hilft mir nicht weiter, da ich nicht weiß wie groß meine Segmente sind... ;(

 

[DrZoidberg]

...und Speicher die Map in einem Array (FIFO) zwischen. Wenn das Array voll ist und ein neuer Eintrag hinzukommt, fliegt immer der erste Eintrag raus...

Das klingt aber so als ob du die Grösse des Arrays kennst. Dann kannst du doch einen Ringbuffer als FIFO Array verwenden.

 

[leon_20v]

Tut mir leid, Array ist flalsch. Es ist ne ArrayList, also unbekannt.


Ich hab jetzt Lösung, bin mir aber noch nciht sicher was ich selber schreiben muss.


Ich brauch ne TreeMap, am besten die aufgebaut ist wie ein AVL Baum. Allerdings möchte ich das die Map nur meine Notes verwaltet, da ich auch die Notes recyclen will.

Gibt es iwi eine Möglichkeit um an den Speicher der TreeMap zu kommen?

Wenn ich eine eigene Map implementieren sollte, müsste ich beim hinzufügen immer rotieren. Gibt es da vll ne Möglichkeit die das für mich übernimmt?



Also im Endeffekt kann ich mir doch aus einer Map alle Entrys geben lassen? Entrys = Knoten?

Ich brauch also etwas, damit ich meiner Map Entrys hinzufügen kann, ohne zu kopieren oder sonst was?

 

[leon_20v]

Hab weiter geforscht.

eigentlich brauch ich nur eine map die mit put(Entry aEntry) klar kommt. Das gibts leider nicht. Also brauch ich eine eigene Map.

Leider kann ich wegen dem GPL Dreck nicht einfach eine put(Entry aEntry) einbauen sondern muss mir irgendwie eine eigene Map basteln. (außer es kennt jemand eine TreeMap die ich kommerziell verwenden und verändern darf?)



Wenn ich eine eigene Map schreibe, dann reicht es mir wenn die hinzufügen und entnehmen kann, sowie getValuebyKey(key).
Kann mir da jemand weiter helfen? die Zeit eilt...

 

[DrZoidberg]

Tut mir leid, Array ist flalsch. Es ist ne ArrayList, also unbekannt.

Du fügst also Einträge zu dieser ArrayList hinzu und sobald sie voll ist fliegt der erste Eintrag raus? Wenn sie voll sein kann, dann heisst das es gibt eine maximale Länge folglich kennst du die Grösse.
Es ist immer noch nicht klar was genau dein Problem ist.
Du willst Punkte in eine Liste oder Map schreiben? Und es sollen keine nennenswerten GC Pausen dabei auftreten?
Wozu brauchst du überhaupt eine Map? Und hat diese Map auch eine maximale Grösse?

Vielleicht könntest du dein Problem noch mal komplett von Anfang an erklären.

 

[leon_20v]

Also:

Ich Zeige Daten an. Der Startpunkt ist beliebig. Es können jederzeit neue Datenpunkte hinzukommen.

Der Benutzer kann sich Daten von einer beliebigen Stelle anzeigen lassen.
Die Daten haben einen Zeitstempel und eine Value.


Wenn der Datenpuffer voll ist schreibe ich die Elemente die rausfliegen auf die Festplatte. Dann werden sehr viele Objekte verworfen und müssen von der GC gelöscht werden.


IDEE: Alle Objekte Recyclen... D.h. ich erstelle keine neuen Objekte sonder schreib die Objekte in eine ArrayList. Wenn jetzt neue Punkte erzeugt werden, schau ich zuerst in die ArrayList ob da "tote Objekte" sind.

So wenn ich jetzt nur Key und Value Recycle hab ich ja immer noch ein haufen Overhead der Map den die GC wegräumen muss. Deswegen möchte ich die Notes der Map recyclen.


Ich hoffe ich habe das Probelem gut erklären können. Eine Map brauch ich weil ich jederzeit beliebig Punkte aus der Map holen muss. Ausserdem können unendlich viele Punkte kommen. Wenn ich Punkte wieder nachlade, dann stimmt die Sortierung nicht mehr. Deswegen muss ich mit einer Map arbeiten.


So wenn ich jetzt das hier mache

import java.util.Map;
import java.util.TreeMap;

public class TreeMapnew<K, V> extends TreeMap<K, V> {


    public void putEntry(Map.Entry<K, V> entry) {
        super.put(entry.getKey(), entry.getValue()); // entry wird neu erstellt, altes entry muss aufgerumt werden
    }
}

Dann habe ich nur die hälfte gewonnen.

Wenn man sich den Source der TreeMap anschaut, dann könnte man das leicht umbauen. Aber das ist GPL und dann wäre das Program GPL...

 

[Ruzmanz]

Das wird nichts.

 

[leon_20v]

ja und warum?

ich mein,hätte ich eine eigene Map, dann könnte ich der Notes hinzufügen, die Referenzen neu setzen und alles gut.


Ich hatte auch schon ne Idee, wenn man sich die TreeMap von Java anschaut und dort die put(...) funktion. Dann könnte man diese einfach auf put(Entry e) umbauen. Aber der Java Source Code ist ja GPL License, d.h. verändere ich den Code, dann wird meine komplette Software GPL und das geht natürlich nicht..

 

[Ruzmanz]

Habe blind drauf losgeraten. Deine Informationen zu deinem Projekt sind unbrauchbar. Anhand deinem Code (und das sind nur ein paar Zeilen!) kann ich erkennen, dass du nicht in der Lage bist den AVL-Baum effizient zu programmieren. Mal davon abgesehen sehe ich darin keinen nutzen. Ist alles hoch spekulativ, da du nahezu keinen Input zu deinen Problem geliefert hast ... die Daten auf der Festplatte verwalten sich nicht von selbst und wenn du auf die Festplatte zugreifen musst, wird dein Programm ausgebremst.

 

[leon_20v]

es geht hier aber nicht wie die daten auf die platte gespeichert werden, und es geht auch nicht um das restliche zeug...


es geht hier nur darum, wie ich eine map recyclen kann, also den knoten einer map in eine andere map verschiebe ohne zu kopieren, sonder nur mit referenzen setzen...

und den code den ich gepostet habe, da gehts nur darum um zu erläutern was ich meine, das ich genau das nicht will sonder hier ein Entry hinzufügen will...

 

[DrZoidberg]

Mal sehen ob ich das Ganze jetzt richtig verstanden habe.
Du hast eine Map<Zeit, Value> zu der du ständig Punkte hinzufügst und eine ArrayList<Map<Zeit, Value>>.
Alle 5 Sekunden fügst du nun die aktuelle Map zu der ArrayList hinzu und erstellst eine neue leere Map.
Die alten Maps werden dann aus der ArrayList geholt, auf Festplatte geschrieben und danach vom GC entsorgt.

Du musst aber nicht jedes mal eine neue Map erstellen. Sieh die mal die Dokumentation von LinkedHashMap.removeEldestEntry an.
LinkedHashMap (Java Platform SE 7 ))

Wenn du die Methode überschreibst, kannst du immer den ältesten Eintrag in der Map löschen lassen, sobald die Map eine bestimmte Grösse erreicht hat oder sobald der älteste Eintrag älter als ein paar Sekunden ist. Das schreiben von Einträgen auf Platte kannst du dann auch in der removeEldestEntry Methode machen.

Falls du die GC Pausen absolut nicht in den Griff bekommst, kannst du auch folgendes versuchen.
Schreib zwei Programme und lass sie auf zwei verschiedenen Instanzen der JVM laufen. Das eine agiert als "Datenbank". D.h. es nimmt Zeit/Value Paare entgegen und speichert sie in einer Map/auf Festplatte ab. Das andere Programm macht den ganzen Rest. Die beiden kommunizieren per Netzwerkverbindung. Wenn nun die Datenbank kurz stoppt wegen dem GC, läuft das andere Programm trotzdem weiter. Das Übertragen der Daten sollte dabei in einem extra Thread stattfinden, um sicher zu stellen, dass der Hauptthread nie blockiert.

Übrigens - das Erstellen und Löschen eine grossen Anzahl an kleinen Objekten verursacht in der Regel keine grossen GC Pausen. Du kannst eine Millionen kleiner Objekte pro Sekunde erzeugen und löschen ohne nenneswerte Pausen. Probleme bekommst du nur wenn eine grosse Menge an Objekten auf einen Schlag gelöscht werden muss.

Teste mal den Code hier.

LinkedHashMap<Double, Double> map = new LinkedHashMap<Double, Double>() {
  @Override
  protected boolean removeEldestEntry(Map.Entry<Double,Double> eldest) {
    return size() > 1000;
  }
};

long startTime = System.nanoTime();
long maxTime = 0;
long lastTime = startTime;
for(int i = 0; i < 100000000; i++) {
  long time = System.nanoTime();
  maxTime = Math.max(maxTime, time - lastTime);
  lastTime = time;
  map.put(time/1e6, Math.random());
}
long endTime = System.nanoTime();

System.out.println("Zeit gesamt = " + ((endTime - startTime)/1e6) + "ms");
System.out.println("max Zeit pro Durchlauf = " + (maxTime/1e6) + "ms");
System.out.println("map.size() = " + map.size());

Bei mir gibt er das hier aus.

Zeit gesamt = 4958.320859ms
max Zeit pro Durchlauf = 17.581067ms
map.size() = 1000

Das heisst du kannst pro Sekunde 20 Millionen Einträge in die Map einfügen und wieder löschen. Für jeden Eintrag werden zwei neue Double Objekte erzeugt und ein Map.Entry Objekt. Trotzdem beträgt die längste GC Pause nur ca. 20ms.

 

[leon_20v]

Danke für deine Antwort,

das mit dem letzten Eintrag der Map ist so ne Sache, ich will nämlich nicht nur einen Eintrag auf die Platte schreiben, sondern Segmente (das sind alle Punkte der x-Sekunden). Das fällt also flach.


Das mit zwei Programmen wäre eine absolute Notlösung, weil ich dann mehrere dieser Programme starten müsste, weil es mehrere dieser graphen gibt..


Das mit der Netzwerkverbindung gefällt mir auch überhaupt nicht.. Zudem das ich auf den Endrechnern nicht zwingend ein IP-Protokoll installiert haben will. Das müsste dann eher über Pipes oder so laufen. Gemacht habe ich das aber noch nie.


Achso meine GC pausen sind 50ms und das ist zu lang und die kommen zu oft, weil der mitm aufräumen nicht nachkommt.. mein key ist n Double und meine Value hat intern weitere 3 objekte.

 

[Ruzmanz]

Tut mir leid, dass ich Performanceoptimierung nicht in zwei Sätzen erklären kann, aber das ist weiterhin unbrauchbar. Du sagst, dass der GC zu langsam ist. DrZoidberg ist so naiv, dass er dir dein „Konzept“ abkauft und beweist, dass Map<Double, Double> schnell genug ist. Nun spezifiziert du deine Anforderung auf Map<Double, Object> und hoffst auf eine weitere Antwort. Ein Object kann ALLES und NICHTS sein. Wenn in dem Object ein Double als Klassenvariable gespeichert wird, dann läuft das wahrscheinlich mit einer ähnlichen Geschwindigkeit. Sind da drei weitere Objekte mit 50 weiteren Klassenvariablen vom Typ „Godlike“ gespeichert, dann dauert das etwas länger … Optimierungspotential? Gibt es nicht, da im Worst-Case ein Object den gesamten RAM und Festplattenspeicher einnimmt. Beim Optimieren geht man immer vom Worst-Case aus! Also musst du Einschränkungen machen. Zum Beispiel:

Map<Double, Value> werte;
public class Value {A a1, a2, a3;}
public class A{int x, y, z;}

Jetzt kann man zumindest abschätzen, wie groß ein Value ist. Ungefähr 127byte (20byte ein Objekt und 4 byte ein Integer). Dann kann man anhand des RAM (z.B. 2,5 Gigabyte) ausrechnen, wie viele Values ungefähr aufgenommen werden können. In diesem Fall sind das ungefähr 20.000. Aber der RAM ist nicht das Problem! Da du die einzelnen Values [genau so???] auf der Festplatte abspeichern möchtest, darfst du maximal die Schreibgeschwindigkeit deiner Festplatte erreichen (z.B. 600mb/s), d.h. 5000 Values in der Sekunde. Hiermit ist die Anforderung von 16.000 Values in der Sekunde (Spitzenwert) hoffnungslos verloren. Festplatte kommt nicht hinterher und das Programm muss warten. Daraus resultiert, dass ein potentieller Flaschenhals die Schreibgeschwindigkeit der Festplatte ist. Handelt es sich um eine 1tb Festplatte kannst du dein Programm 28 Minuten laufen lassen, bevor die Festplatte voll ist … An dieser Stelle bietet es sich an ein Programm zu schreiben, dass den maximalen Durchsatz für eine bestimmte Zeit simuliert. Ich wette es scheitert hierbei nicht am GC. Wenn das doch der Fall sein sollte, muss man halt OO-Konzepte verwerfen und die Datenstruktur abspecken:

public class Value {int x1; x2, x3, y1, y2, y3, z1, z2, z3;}

*Die Rechnung ist nicht ganz korrekt, weil ich den Key vergessen habe. Es soll aber dennoch das Prinzip verdeutlichen. Nachdem der Durchsatz von 5000 Values / Sekunde und die Hardware (1tb Festplatte mit 600 mb/s Schreibgeschwindigkeit und mind. 600mb RAM) bestimmt wurde, kann man an der Antwortzeit optimieren, indem man z.B. den restlichen RAM nutzt …

PS: Klingt übrigens nach simplen Big Data. Viel schreiben, viel Lesen, kaum/nichts ändern. Keine Ahnung was für Datenbanken ihr / dein Chef ausprobiert hat.

 

[leon_20v]

Vielen Dank für deine Ausführliche Antwort.

Ich habe 10h mitgelockt. Ich habe den Double Key = 8 byte und das Objekt hat 3 Doubles und 1 int = 28byte --> 36byte reine Daten hat ein Punkt.

Meine Datei wird dabei 250mb groß. Das ist aber immer verschieden. Ich hab auch schon mitgelockt da wurden es nur 100mb und dann wurden es 1gb. Jenachdem wieviel daten kommen.


Das Problem ist, das der GC immer das hier macht:

xxx.xxx: [CMS-concurrent-mark-start]
xxx.xxx: [CMS-concurrent-mark: 0.055/0.055 secs] [Times: user=0.06 sys=0.00, real=0.05 secs] 
xxx.xxx: [CMS-concurrent-preclean-start]
xxx.xxx: [CMS-concurrent-preclean: 0.001/0.001 secs] [Times: user=0.00 sys=0.00, real=0.00 secs]

Immer bei so einer Ausgabe stoppt das Program kurz und das nervt extrem.

 

[DrZoidberg]

Um die Zahlen mal etwas zu korrigieren - eine 1 TB Festplatte schafft ca. 100 MB/s sequentiell, wenn man Glück hat. Das macht dann 100Mio / 127 = 787000 Values/Sekunde.
2,5 GB RAM / 127 sind ca. 20Mio.

das mit dem letzten Eintrag der Map ist so ne Sache, ich will nämlich nicht nur einen Eintrag auf die Platte schreiben, sondern Segmente (das sind alle Punkte der x-Sekunden). Das fällt also flach.

Wieso muss das unbedingt in Segmenten geschehen?

Das mit zwei Programmen wäre eine absolute Notlösung, weil ich dann mehrere dieser Programme starten müsste, weil es mehrere dieser graphen gibt..

Nein, du brauchst nur ein einziges Datenbank Programm, das dann von allen Graphen gemeinsam verwendet werden kann.

Das mit der Netzwerkverbindung gefällt mir auch überhaupt nicht.. Zudem das ich auf den Endrechnern nicht zwingend ein IP-Protokoll installiert haben will.

Was sind denn das bitte für Rechner, die kein IP Protokoll installiert haben? Jedes moderne Betriebssystem unterstützt IP Verbindungen. Da muss man nichts installieren.

Übrigens - wieso sind Pausen von 50ms ein Problem? Loggt er dann die Daten in dem Zeitraum nicht?

 

[leon_20v]

Ja erstens dieses, zweitens werden die Lücken mit der Zeit größer. Dann habe ich teilweise viel längere Pausen und vorallem, das Programm stockt merkbar dann.

Ich hab gestern das Programm so umprogrammiert, das alle Elemente im Arbeitsspeicher bleiben, es wurde als nichts auf die Platte geschrieben.


Um einen Datensatz zu haben, der immer gleich ist, habe ich mir vor zwei Tagen ein Tesprogramm geschrieben, das mir alle 20ms, 20 Punkte erstellt und mir an meine Datenbeschaffung schickt.

Das Programm ist so eingestellt, das es max 1gb vom Arbeittspeicher haben darf. Leider kann ich nicht genau sagen, wann der heute nacht voll war. Als ich nach 14h wieder gekommen bin, war er zumindest voll.

Wenn ich auf die Platte schreibe, habe ich nur 570mb an Rohdaten nach 14h. Ein Punkt hat 20byte Rohdaten. Also der Overhead muss schon ziemlich groß sein.



Ich vermute, dass das marken so lange braucht, umsomehr Objekte ich habe. Kann ich das irgendwie Prüfen?

 

[Joose]

Wenn es um solche Sachen geht einfach mal Memory Profiler und Perfomance Profiler einsetzen!

Ich würde zuerst das Memory Problem lösen und danach schauen was man an der Performance noch drehen kann.

 

[DrZoidberg]

Du kannst auch ganz ohne das Erstellen von neuen Objekten auskommen. Wenn du alles in ein grosses Array oder besser noch ByteBuffer schreibst.
Auf die Weise benötigst du nur 28 Byte RAM pro Eintrag und du hast nie irgendwelche GC Pausen.
Dieses Programm schreibt alle 20ms 20 Einträge in einen ByteBuffer und schreibt alles ein mal pro Sekunde auf Festplatte. Abgesehen von dem Thread.sleep(20) gibt es keine Pausen, die länger als ein paar ms sind.
Das Programm demonstriert ausserdem auch noch wie eine binäre Suche in diesem Buffer funktioniert, was du benötigst da du jetzt keine Map mehr hast.

import java.nio.ByteBuffer;
import java.util.Random;
import java.io.IOException;
import java.nio.file.Path;
import java.nio.file.Paths;
import java.nio.file.Files;
import java.nio.channels.FileChannel;
import static java.nio.file.StandardOpenOption.*;

public class Memory {
  static ByteBuffer buffer;
  static double[] array = new double[4];
  
  static void writeEntry(double key, double n1, double n2, int n3) {
    buffer.putDouble(key);
    buffer.putDouble(n1);
    buffer.putDouble(n2);
    buffer.putInt(n3);
  }
  
  static void readEntry(int index, double[] result) {
    int pos = buffer.position();
    buffer.position(index * 28);
    result[0] = buffer.getDouble();
    result[1] = buffer.getDouble();
    result[2] = buffer.getDouble();
    result[3] = buffer.getInt();
    buffer.position(pos);
  }
  
  static double readKey(int index) {
    return buffer.getDouble(index * 28);
  }
  
  static int findKey(double key) {
    //binäre Suche
    int min = 0, max = buffer.position()/28;
    while(max > min) {
      int m = (min + max)/2;       
      double k = readKey(m);
      if(k == key) return m;
      else if(k < key) min = m + 1;
      else max = m;
    }
    return -1;
  }
  
  static void writeToFile(Path path) {
    try {
      FileChannel ch = FileChannel.open(path, CREATE, WRITE, APPEND);
      while(buffer.position() > 0) {
        buffer.flip();
        ch.write(buffer);
        buffer.compact();
      }
      ch.close();
      buffer.clear();
    } catch(IOException e) {
      e.printStackTrace();
    }
  }
  
  static void printEntry(int index) {
    readEntry(index, array);
    System.out.println("key = " + array[0]);
    System.out.println("n1 = "  + array[1]);
    System.out.println("n2 = "  + array[2]);
    System.out.println("n3 = "  + ((int)array[3]));
  }
  
  public static void main(String[] args) throws Exception {
    Random rand = new Random();
    buffer  = ByteBuffer.allocate(1000000);
    Path path = Paths.get("test.bin");
    long startTime = System.currentTimeMillis();
    long currentTime = startTime;
    long lastTime = currentTime;
    long lastWriteTime = currentTime;
    long maxTime = 0;
    while(currentTime - startTime < 10000) {
      currentTime = System.currentTimeMillis();
      for(int i = 0; i < 20; i++) {
        writeEntry(i, rand.nextDouble(), rand.nextDouble(), rand.nextInt());
      }
      
      if(currentTime - lastWriteTime > 1000) {
        lastWriteTime = currentTime;
        writeToFile(path);
      }
      maxTime = Math.max(maxTime, currentTime - lastTime);
      lastTime = currentTime;
      Thread.sleep(20);
    }
    
    System.out.println("maxTime = " + maxTime);
  }
}

 

[leon_20v]

Vielen Dank für deine große Mühe :toll::applaus:


Ich hatte mir schon so etwas ähnliches überlegt, aber bei einem Array hab ich ein riesen Problem. Um Binäre suche ausführen zu können, brauch ich ein sortiertes Array.


Der User kann wenn er will, einfach auf den Anfang zugreifen, also schreibt er Teile des Anfangs in das Array. Jetzt ist nichts mehr sortiert.Das Array jedesmal zu sortieren wenn ich von der Platte nachlade (weil ich auf den anfang zugreife), wäre viel zu aufwendig. Das habe ich aber bereits schon in einigen Posts zuvor geschrieben ;(

Wenn es um solche Sachen geht einfach mal Memory Profiler und Perfomance Profiler einsetzen!

Ich würde zuerst das Memory Problem lösen und danach schauen was man an der Performance noch drehen kann.

Welchen Profiler würdest du nehmen? Ich hatte mal den JProfiler aber nu keine Lizenz mehr. Der VM Profiler finde ich nicht gut...

 

[DrZoidberg]

Ich vermute mal die Daten in der Datei sind sortiert. Wenn du jetzt also z.B. 1000 Einträge nachlädst, verschiebst du den Inhalt des Arrays um 1000 Elemente und schreibst dann die geladenen Daten an den Anfang. Dann ist es doch wieder sortiert.
Abgesehen davon ist es nicht all zu aufwendig ein Array zu sortieren. java.util.Arrays.sort ist sehr schnell, vor allem, wenn die Daten schon teilweise sortiert sind.