Variablen Stringarrays mit wenig verschiedenen Zeichen effizienter speichern

ushit99

Mitglied
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?

Vielen Dank für eure Hilfe!
 

njans

Top Contributor
Huffman Encoding auf die String, wobei du, mal abgesehen davon, auch einfach 3 bit bräuchtest um jeden Buchstaben durch eien Zahl darzustellen.
 

ushit99

Mitglied
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?
 

CSHW89

Bekanntes Mitglied
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.

lg Kevin
 
Zuletzt bearbeitet:

ushit99

Mitglied
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?
 

CSHW89

Bekanntes Mitglied
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

stringPos[0] = 0 // immer 0
stringPos[1] = stringPos[0] + aufrunden(7/4) = 2
stringPos[2] = stringPos[1] + aufrunden(26/4) = 2 + 7 = 9
Größe des data-Array = stringPos[2] + aufrunden(8/4) = 9 + 2 = 11

lg Kevin
 

Thallius

Top Contributor
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.

Gruß

Claus
 

ushit99

Mitglied
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
 

nvidia

Bekanntes Mitglied
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Ü Eurobeträge in möglichst wenig Scheine/Münzen zerlegen (2D-Arrays) Allgemeine Java-Themen 27
SkyScreamer Java Spiel nutzt wenig Arbeitsspeicher Allgemeine Java-Themen 4
Master3000 Dateien zwischen verschiedenen Netzwerken senden Allgemeine Java-Themen 17
Drachenbauer Wie muss ein Konstructor aussehen, um dinge mit verschiedenen Zusätzen in den "<>" anzunehmen? Allgemeine Java-Themen 1
M Wie kann man eine void Methode mit Variablen von zwei verschiedenen Objekten ausführen? Allgemeine Java-Themen 15
A Classpath Library in verschiedenen Projekten Allgemeine Java-Themen 2
S Spielfeld aus verschiedenen Kacheln Allgemeine Java-Themen 35
M ArrayList mit verschiedenen Datentypen in String konvertieren Allgemeine Java-Themen 10
M Null byte in verschiedenen charsets Allgemeine Java-Themen 2
M Testen von verschiedenen Produktversionen Allgemeine Java-Themen 3
C Vigenere und Caesar in verschiedenen Alphabeten Allgemeine Java-Themen 1
A Threads Lock über mehrere Abschnitte in verschiedenen Methoden Allgemeine Java-Themen 5
T Datentypen Eine Liste - verschiedenen Klassen - eine Abstracte Klasse Allgemeine Java-Themen 3
P Objekt mit verschiedenen Datentypen Allgemeine Java-Themen 5
P Anzahl vo Einträgen in verschiedenen Sets Allgemeine Java-Themen 3
R Input/Output Dateizugriff aus verschiedenen Tools Allgemeine Java-Themen 3
J Druckprobleme bei verschiedenen Schriftarten/-größen Allgemeine Java-Themen 7
B File Seperator unter verschiedenen OS Allgemeine Java-Themen 2
G Gleiche Packages in verschiedenen JAR Dateien - Welches Package wird verwendet? Allgemeine Java-Themen 5
K Programm mit verschiedenen Parametern starten Allgemeine Java-Themen 2
E Outputstream an verschiedenen Positionen beschreiben Allgemeine Java-Themen 4
N Dateizugriff in verschiedenen Ordnern Allgemeine Java-Themen 2
S Fragen zu verschiedenen Themen vom JCreator Allgemeine Java-Themen 2
S Frage zu verschiedenen Java Projekten Allgemeine Java-Themen 6
D Logger mit verschiedenen Ausgabezielen Allgemeine Java-Themen 2
H2SO3- sichtbarkeit in verschiedenen paketen Allgemeine Java-Themen 2
R Kann ich die jars eines Applets auf verschiedenen Domains hosten? Allgemeine Java-Themen 2
T DataFrame (Matrix mit mit verschiedenen Typen pro Spalte) Allgemeine Java-Themen 4
R Aktuelle Kompatibilitätsliste für JRE auf verschiedenen OS´s Allgemeine Java-Themen 2
MQue Methoden in verschiedenen Klassen aufrufen Allgemeine Java-Themen 21
MQue JButton an verschiedenen Variablen Allgemeine Java-Themen 2
J parsen von verschiedenen dokument typen Allgemeine Java-Themen 3
D generischer Iterator mit verschiedenen Typen Allgemeine Java-Themen 3
S Arrayelemente in verschiedenen Variationen zurückgeben Allgemeine Java-Themen 12
T Herunterfahren oder Neustarten der verschiedenen OS Allgemeine Java-Themen 11
C Sichbarkeit von Objekten / Methoden in verschiedenen Files Allgemeine Java-Themen 7

Ähnliche Java Themen

Neue Themen


Oben