Beste Datenstruktur für große Datenmengen?

Question

Einlesen vieler Daten aus einer Datei. Es kann 100 verschiedene Datenobjekte mit den notwendigen Überschriften geben, aber es können weit über 300.000 Werte in jedem dieser Datenobjekte gespeichert sein. Die Werte müssen in der gleichen Reihenfolge gespeichert werden, dass sie in gelesen werden Dies ist der Konstruktor für das Datenobjekt ist.

public Data(String heading, ArrayList<Float> values) { 
    this.heading = heading; 
    this.values = values; 
} 

Was wäre der schnellste Weg sein, diese Werte sequentiell im RAM zu speichern und abzurufen?

Answer 1

Sie könnten eine RedBlack BST verwenden, die eine äußerst effiziente Möglichkeit zum Speichern/Abrufen von Daten sein wird. Dies beruht auf Knoten, die mit anderen Knoten verbunden sind, so dass die Größe der Eingabe nicht begrenzt ist, solange Sie über genügend Speicher für Java verfügen.

Answer 2

Obwohl Sie in Ihren Kommentaren "Schnelligkeit" erwähnen, ohne anzugeben, welche Operation "schnell" sein muss, scheint Ihr Hauptanliegen der Speicherverbrauch zu sein.

Nehmen wir an 100 Gruppen von 300.000 Nummern (Sie haben Wörter wie "vielleicht" und "weit über" verwendet, aber dies wird als ein Beispiel).

Das sind 30.000.000 zu speichernde Zahlen plus 100 Überschriften und ein struktureller Mehraufwand für die Gruppierung.

Ein primitives Java float ist 32 Bits, das sind 4 Bytes. Also auf ein absolutes Minimum, werden Sie 30.000.000 * 4 Bytes == 120MB benötigen.

Ein Array von Primitiven - float[30000000] - ist nur alle Werte in einem zusammenhängenden Stück Speicher verkettet, so wird dieses theoretische Minimum von 120MB verbrauchen - plus ein paar Bytes von einmal pro Array Overhead, die ich nicht werde gehe hier ins Detail.

Ein Java Float Wrapper-Objekt ist 12 Bytes. Wenn Sie ein Objekt (anstatt eines Grundelements) in einem Array speichern, beträgt die Referenz selbst 4 Byte. Ein Array von Float - Float[30000000] wird also 30.000.000 * (12 + 4) == 480MB verbrauchen.

So können Sie die Speicherbelegung um mehr als die Hälfte reduzieren, indem Sie primitive statt Wrapper verwenden.

---

Ein ArrayList ist ein ziemlich Licht Wrapper um ein Array von Object und hat so zu den gleichen Speicherkosten. Die Overheads pro Listeneintrag sind bei diesen Listengrößen zu klein, um Auswirkungen gegenüber den Elementen zu haben. Aber es gibt einige Einschränkungen:

• ArrayList können nur Objekte speichern, nicht Primitiven, wenn Sie also eine List wählen bist du mit dem stecken 12-Byte-pro-Element-Overhead von Float.
  • Es gibt einige Bibliotheken von Drittanbietern, die Listen von Primitiven liefern - siehe: Create a List of primitive int?
• Die Kapazität eines ArrayList ist dynamisch, und um dies zu erreichen, wenn Sie die Liste wachsen größer zu sein als sein Array sichern, wird es:
  • ein neues Array erstellen, 50% größer als das alte Array
  • kopieren sie den Inhalt des alten Array in das neue Array (das klingt teuer, aber Hardware ist sehr schnell auf diese Weise)
  • verwerfen die alte Array
  • Dies bedeutet, dass, wenn die Träger Array 30 Millionen Elementen haben, geschieht, und ist voll, ArrayList.add() wird das Array mit einer von 45 Millionen Elemente, auch wenn Ihr List braucht nur 30.000.001 zu ersetzen.
  • Sie können dies vermeiden, wenn Sie die erforderliche Kapazität im Voraus kennen, indem Sie die Kapazität im Konstruktor bereitstellen.
  • Sie können ArrayList.trimToSize() verwenden, um nicht benötigte Kapazität zu löschen und etwas Speicher zurückzunehmen, nachdem Sie die ArrayList gefüllt haben.

---

Wenn ich so wenig Heap-Speicher wie möglich verwenden strebe, würde ich will meine Listen von Zahlen als Arrays von Primitiven speichern:

class Data { 
    String header; 
    float[] values; 
} 

... und Ich würde diese einfach in eine setzen.

Mit dieser Struktur haben Sie O (1) Zugriff auf beliebige Werte, und Sie können Arrays.binarySearch() (wenn die Werte sortiert sind) nach Wert innerhalb einer Gruppe suchen.

Wenn möglich, würde ich die Größe jeder Gruppe vor dem Lesen der Werte herausfinden und das Array auf die richtige Größe initialisieren. Wenn Sie können, Ihre Eingabe-Dateiformat diese machen erleichtern:

while(line = readLine()) { 
    if(isHeader(line)) { 
      ParsedHeader header = new ParsedHeader(line); 
      currentArray = new float[header.size()]; 
      arrayIndex = 0; 
      currentGroup = new Group(header.name(), currentArray); 

      groups.add(currentGroup); 
    } else if (isValue(line)) { 
      currentArray[arrayIndex++] = parseValue(line); 
    } 
} 

Wenn Sie nicht das Eingabeformat ändern kann, sollten zwei Durchgänge durch die Datei zu machen - einmal Gruppenlängen zu entdecken, noch einmal Ihre Arrays zu füllen.

Wenn Sie müssen die Datei in einem Durchgang konsumieren, und das Dateiformat kann keine Gruppenlängen vor Gruppen bieten, dann müssen Sie etwas tun, das eine "Liste" beliebig wachsen lässt. Es gibt mehrere Möglichkeiten:

• Verbrauchen jede Gruppe in eine ArrayList<Float> - wenn die Gruppe vollständig ist, wandelt es in ein array[float]:

  float[] array = new float[list.size()]; 
  int i = 0; 
  for (Float f : list) { 
      array[i] = f; // auto-unboxes Float to float 
  } 
  

• Verwenden Sie ein Drittanbieter-list-of-Float-Bibliothek Klasse
• Kopieren Sie die von Arraylist verwendet Logik Array mit einer größeren zu ersetzen, wenn erforderlich - http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java#ArrayList.ensureCapacity%28int%29
• können beliebig viele Ansätze in der Informatik Lehrbüchern diskutiert, beispielsweise eine verknüpfte Liste von Arrays.

---

jedoch nichts davon hält Ihre Gründe für die in erster Linie all diese Zahlen in den Speicher Schlürfen, noch, ob dieser Speicher Ihre Bedürfnisse erfüllt, wenn es darum geht, die Zahlen zu verarbeiten.

Sie sollten zurücktreten und überlegen, was Ihre eigentliche Datenverarbeitungsanforderung ist und ob das Einschlafen in den Speicher der beste Ansatz ist.

Sehen Sie, ob Sie Ihre Verarbeitung durchführen können, indem Sie nur eine Scheibe von Daten auf einmal speichern, anstatt die ganze Sache im Speicher zu speichern. Um beispielsweise Max/Min/Mittelwert zu berechnen, müssen Sie nicht jede Zahl im Speicher haben - Sie müssen nur eine laufende Summe behalten.

Oder überlegen Sie sich, eine leichtgewichtige Datenbankbibliothek zu verwenden.