Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
VariablenStringarrays mit wenig verschiedenen Zeichen effizienter speichern
Ich habe folgendes Problem: Ich muss ein sehr großes Stringarray (bis zu 100.000 Einträge) speichern. Jeder Eintrag ist ein String mit ebenfalls 100.000 Zeichen. Der RAM-Verbrauch von diesem Array wäre sehr hoch (über 30GB). Da diese Datenmengen kein System verkraften kann, möchte ich diese Daten gerne etwas effizienter speichern. Ein Vorteil ist, das jeder String nur aus 4 verschiedenen Zeichen besteht. Gibt es eine Möglichkeit, diese Daten wesentlich effizienter zu speichern?
Danke für die schnellen Antworten! Könnt ihr mir jetzt vlt. noch sagen, wie ich das implementieren kann? Weil ich glaube eine Java-Boolean brauch ja ein ganzes Byte an Speicherplatz. Außerdem vermute ich, dass irgendwelche Metadaten den RAM-Verbrauch drastisch erhöhen. Habt ihr da noch irgendwelche Tipps?
Ja ein Stringarray hat ein nicht zu unterschätzenden Overhead. Jeder String besitzt ein Array, und jedes Array hat noch zusätzlichen Speicher für interne Zwecke. Du hast 100001 Arrays.
Wenn alle Strings (annähernd) gleich groß sind, und du die (maximale) Größe der Strings am Anfang kennst, brauchst du nur ein einziges byte-Array für alle Strings. Ich würde das dann so machen:
Java:
class StringData {
private byte[] data;
private int stringLength; // sollte durch 4 teilbar sein. Wenn nicht einfach zum nächsten Teiler aufrunden (also 997 -> 1000)
public char getChar(int string, int pos) {
return (data[string * stringLength/4 + pos/4] >> ((pos%4)*2)) & 3 + 'A'
}
public void setChar(int string, int pos, char c) {
if (c >= 'A' && c < 'A'+4) {
data[string * stringLength/4 + pos/4] |= (c - 'A') << ((pos%4)*2)
}
}
}
Um die set-Methode nicht noch weiter zu komplizieren, habe ich jetzt die Möglichkeit vernachlässigt, die Character im String zu überschreiben. Wenn das nötig ist, muss man sie noch etwas modifizieren.
Wenn nicht klar ist, was da passiert, kann ichs nochmal im Detail erklären.
DANKE! Ich glaube, das ist genau das, was ich brauche. Aber ich muss zugeben, dass ich nucht ganz verstehe, was in der set un der get Methode passiert. Könntet du mir das vlt. erklären? Außerdem: Du sagtest, die Strings müssen annähernd gleich lang sein. Das ist bei mir leider nicht so. Ich habe Strings von 1 - 100000 Zeichen länge. Allerdings weiß ich die länge von jedem String schon vorher. Kann man mit diesem Wissen noch mehr RAM sparen?
Ok, das Array 'data' speichert alle Strings einfach hintereinander. Wenn ich die einzelnen Character setzen oder haben will, muss ich wissen, wo jeder String startet. In meinem Code weiß ich das durch die konstante Stringlänge. Jeder String hat 'stringLength' Character, jedes Byte (8 bit) speichert 4 Character, da du nur vier verschiedene Zeichen hast. Somit beansprucht jeder String 'stringLength/4' Bytes. Das heißt der Anfang des 2. Strings (Zählung fängt bei 0 an) ist an der Stelle (2 * stringLength/4). Nun müssen wir zur Position eines Characters springen. Da jedes Byte 4 Character speichert, müssen 'pos/4' Bytes übersprungen werden, um zum Byte zu gelangen, in dem der 'pos'te Character ist (bei pos=6 ist es das 2. Byte, also muss ein Byte übersprungen werden).
So ein Byte sieht dann z.b. so aus: 10 01 11 10. Jedes Zweierpäckchen representiert ein Character. Welches Päckchen nun betrachtet wird, entscheidet nun pos modulo 4 'pos%4', also ein Wert zwischen 0 und 3. Die Reihenfolge ist dann aber absteigend: 10(3) 01(2) 11(1) 10(0).
In der get-Methode wird das Byte nun manipuliert um genau den Character zu bestimmen (pos = 5):
10 01 11 10 >> ((5%4)*2)=2
00 10 01 11 & 3
00 00 00 11 + 'A' => Character 'D', da 'A'+0='A', 'A'+1='B', 'A'+2='C', 'A'+3='D'
Die set-Methode ver-oder-t einfach nur genau die zwei Bits, die den Character speichern.
So nun zu den verschiedenen Längen. Du bräuchtest dann ein weiteres Array, das die Positionen der einzelnen Strings speichert. Dann hast du ungefär sowas:
Java:
class StringData {
private byte[] data;
private int[] stringPos;
public char getChar(int string, int pos) {
return (data[stringPos[string] + pos/4] >> ((pos%4)*2)) & 3 + 'A'
}
public void setChar(int string, int pos, char c) {
if (c >= 'A' && c < 'A'+4) {
data[stringPos[string] + pos/4] |= (c - 'A') << ((pos%4)*2)
}
}
}
Das Array stringPos speichert die Positionen dann wie folgt:
Länge von string0 = 7
Länge von string1 = 26
Länge von string2 = 8
Die Frage ist doch wozu soll das eigentlich gut sein? Gut du schaffst es 30 GB Strings zu speichern. Aber wofür wenn du sie eh so nicht wieder einladen kannst ? Bzw wie schnell brauchst du die Informationen? Wo kommen die 30 GB überhaupt her? Die müssen ja schon irgendwo stehen. Also warum noch einmal speichern? Also für mich hört sich das stark nach einem komplett kaputten Konzept an.
Danke CSHW89!
Ich werde das gleich mal ausprobieren! Und Thallius: Mach dir keine Sorgen. Das Speichern/Einlesen der Strings kann von mir aus gerne mehrere Minuten/Stunden brauchen. Das Programm ist eh nicht für wirkliche Anwender gedacht. Der Algorithmus braucht so oder so ewig um die ganzen Strings auszuwerten
Die Frage ist doch wozu soll das eigentlich gut sein? Gut du schaffst es 30 GB Strings zu speichern. Aber wofür wenn du sie eh so nicht wieder einladen kannst ? Bzw wie schnell brauchst du die Informationen? Wo kommen die 30 GB überhaupt her? Die müssen ja schon irgendwo stehen. Also warum noch einmal speichern? Also für mich hört sich das stark nach einem komplett kaputten Konzept an.
Das Konzept ist nicht kaputt. Es wird sicher wieder so eine Bioinformatikaufgabe bzgl. DNA sein. Und anstelle Strings aus A,G,T,C zu verarbeiten ist es wesentlich effizienter das in eine anderes Format zu übertragen. Je mehr in den Cache und in den Speicher passt desto besser. Ich vermute auch, dass wenn lange Ketten 0,1 in so einer entstandenen Binärreihe vorhanden sind diese Reihe komprimiert wird, mit solchen Geschichten wie EWAH usw.
Davon abgesehen würde ich persönlich nicht mit byte rumspielen, man weiß nicht wie das Padding aussieht, im schlimmsten Fall erweitert die JVM das auf Integer-Größe. Deshalb würde ich auf int setzen. Aber wie byte-Arrays behandelt werden, dazu müsste man in der JVM-Spezifikation nachsehen ob zur Speicherung von byte-Feldern irgendwie optimiert werden muss.