Speicherplatz sparen

[Schreiber]

Hallo,

ich soll eine Klasse implementieren, welches sogenannte sparse vektoren als objekte besitzt.
Das sind vektoren, welche grob gesagt viele Nullen behalten.
Nun sollen nur die Einträge ungleich null gespeichert werden, um Speicherplatz zu sparen.

Ich frage mich, wann genau Speicherplatz gespart wird. Wenn ich z.B. vektoren als arrays darstelle, dann haben die arrays/vektoren doch in Java eine fixe länge.

Java benötigt sicher speicherplatz, um das objekt array anzulegen. Aber verbraucht java auch schon speicherplatz, wenn ich die länge setze?
Oder nur dann, wenn man auch wirklich in die einzelnen "Fächer" etwas "hineingibt" also speichert.

Danke

 

[Runtime]

Durch das Schlüsselwort new wird immer der ganze des Objekts benötigte Speicher angefordert. Also wenn du ein Array definierst, wird kein Speicherplatz angefordert, aber wenn du es initialisierst, benötigst du 'new'.

 

[Schreiber]

Danke, d.h. man würde dadurch gar keinen Speicherplatz sparen.

Dann müsste man vermutlich die Daten einlesen und dann die Werte ungleich 0 Zwischenspeichern und gleichzeitig den zugehörigen Index sich merken.
Um anschließend einen passenden array erstellen zu können.

Wäre das der richtige weg?

Güße

 

[ralfz]

Hallo,

also alle Elemente belegen irdendwie Platz. In den Java Büchern werden i.d.r nur die primitiven Datentypen beschrieben, so z.B. verbraucht ein int halt fix 4 Byte und ein long 8 Byte.

Für Objekte gilt dann z.B. dass jedes Objekt mind 8 Byte verbraucht. Ein Array ist auch ein Objekt, somit verbraucht dieses 8 Byte. Hinzu wird die Länge in int angegeben, also +4 Byte=12 Byte für ein leeres Array.

Initialisiert man ein Array mit einer bestimmten Größe z.B. 1000, also int[] liste = new int[1000] liegt die Größe bei 8+4+ (1000*4) Byte; Hat man ein Array von Objekten, dann belegt jede Stelle ebenfalls 4 Byte als Objekt-Referenz.

In folgenden Artikeln wird auf Java und Speicherverbrauch eingegangen: (Unterscheiden sich in der Interpretation ein wenig )
[1] Determining Memory Usage in Java - java tutorial
[2] Memory usage of Java objects: general guide

Ich finde [2] etwas plausibler...

Gruß
Ralf

 

[ralfz]

Nachtrag

Ob du nun Array, ArrayList oder Vektor nimmst, intern nutzen die alle ein Array. Es kommt nur lediglich für die Zusatzfunktionen etwas Speicherverbrauch hinzu...

Ich verstehe aber dein Problem noch nicht ganz. Willst du einen Sparse Vektor abspeichern (auf Platte) oder nur effizienter darstellen, indem du die nullen eliminierst? In letzterem Fall würde ich auch einfach die Positionen der Dateneinträge und Daten speichern, da die zusätzlichen 4 Byte für die jeweiligen int Positionen immer noch günstiger sind als viele Nullen, die ja auch Speicher belegen.

Gruß
Ralf

 

[Schreiber]

Hallo ralfz,

vielen Dank für deine Hilfe, du hast mir schon sehr weitergeholfen.
Also ich möchte gerne einen Vektor speichern und damit rechnen. Aber es sollen nur die Einträge ungleich Null gespeichert werden.

Das ist glaube ich genau das, was als zweites auflistest. Ich erstelle ein Array und lasse die einträge bzw. positionen, in welchen Nullen stehen einfach leer. Dann spart man die 0.

Aber später möchte ich auch gerne den sparse vektor darstellen. Könnte man das einfach durch println..?

Meinst du, das wäre in Ordnung?

Vielen Dank nochmal!

 

[Landei]

Eine Möglichkeit wäre eine Map, am besten TreeMap (damit man leicht einen Iterator erstellen kann).

Ungefähr so:

import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
import java.util.TreeMap;

public class SparseVector implements Iterable<Double> {

    private final Map<Integer, Double> map = new TreeMap<Integer, Double>();
    private final int size;

    public SparseVector(int size) {
        assert size > 0;
        this.size = size;
    }

    public double get(int index) {
        assert index < size;
        return map.containsKey(index) ? map.get(index) : 0.0;
    }

    public void set(int index, double value) {
        assert index < size;
        if (value == 0.0) {
            map.remove(index);
        } else {
            map.put(index, value);
        }
    }

    public int getSize() {
        return size;
    }

    public Iterator<Double> iterator() {
        return new Iterator<Double>() {

            private int index = 0;
            private Iterator<Map.Entry<Integer, Double>> it = map.entrySet().iterator();
            private Map.Entry<Integer, Double> entry = it.hasNext() ? it.next() : null;

            public boolean hasNext() {
                return index < size;
            }

            public void remove() {
                throw new UnsupportedOperationException();
            }

            public Double next() {
                if (! hasNext()) {
                    throw new NoSuchElementException();
                }
                index++;
                if(entry != null && entry.getKey() == index-1) {
                   double d = entry.getValue();
                   entry = it.hasNext() ? it.next() : null;
                   return d;
                } else {
                   return 0.0;
                }
            }
        };
    }
}

Der Iterator-Part ist etwas haarig, aber ich denke, es ist wesentlich effizienter, mit dem Map-Iterator zu arbeiten, als jeden Wert einzeln abzufragen.

 

[Gastredner]

Das ist glaube ich genau das, was als zweites auflistest. Ich erstelle ein Array und lasse die einträge bzw. positionen, in welchen Nullen stehen einfach leer. Dann spart man die 0.

Nein, dann sparst du womöglich gar nichts.
Der Speicherplatz für ein Array wird am Stück komplett reserviert. Legst du ein Array von 100 int-Werten an, so wird Platz für 100 int-Werte reserviert, selbst wenn du nur drei int hineinpackst (und auch Nullen fänden sich im Array, denn wie Werte werden auf den Standardwert initialisiert - und der ist für int 0).
Das gilt nicht nur für Primitive, sondern auch für Referenzen auf Objekte. Willst du Speicher sparen, so vergiss Array-basierte Datenstrukturen (bzw. Datenstrukturen mit durchlaufendem Index, wenn du nicht jede dieser Positionen nutzt) und verwende eine Map, wie von Landei vorgeschlagen.

 

[Marco13]

Für Vektoren und Matrizen gibt es etliche verschiedene "sparse" Formate, siehe Sparse Matrix Storage Formats   J. Dongarra oder (eigene ) Websuche.

Dabei wird der Speicherplatz nicht dadurch gespart, dass irgendwelche Einträge [c]null[/c] sind und dadurch "keinen Speicher belegen" (was ja ohnehin nicht direkt der Fall ist: Die Referenz ist da), sondern vielmehr wird explizit gemacht, welche Elemente Einträge enthalten und welche nicht.

Die ganzen verschiedenen Formate haben natürlich Vor- und Nachteile für bestimmte Operationen. Jedenfalls sollte man vorsichtig sein, dort eine eigene Implementierung (z.B. auf Basis eine Map) aus dem Ärmel zu schütteln, wenn das ganze später auch nur ansatzweise effizient sein soll.

Du solltest dir mal UJMP Universal Java Matrix Package » About ansehen. Das ist KEINE Empfehlung für diese Bibliothek (aber auch nicht das gegenteil: Ich habe lediglich noch nicht damit gearbeitet). Die Seite soll nur ein Einsteigspunkt sein, weil diese Bibliothek Wrapper für COLT, JAMA und andere Matrix-Bibliotheken anbietet.

 

[ralfz]

Hi,

wie Gastredner schon bestätigt hat, ein Array mit Nullen spart dir gar nichts.

Abhängig vom Einsatzzweck würde ich die Elemente und deren Positionen als Key, Value Paare speichern, wobei der Key eben die Position eines Nicht-Null-Elements innerhalb des Vektors ist.

Fragt jemand nun eine Position ab, lieferst du entweder den vorhandenen Wert zurück oder eben null.

Realisieren lässt sich das auf verschiedene Arten, z.B. mit einem Dictonary (Map) oder einer doppelten Liste, die du mit den Informationen aus dem Sparse-Vektor fütterst.

ganz primitiv gedacht:

class MyVektor{
// liste für die Wert-Positionen
ArrayList<int> positionen;
// Liste für die Wert-Einträge
ArrayList<deinBenötigterWerttyp> werte;

public deinWertTyp getValue(int position){
  // irgendwie sowas (weiss gerade nicht, ob die Syntax stimmt ;) ):
  if (positionen.contains(position)) return werte.getValueAt(positionen.indexOf(position));
  else return 0;
}

public void setVektor(SparseVektor liste){
 //speichere die vorhandenen Werte und zugehörigen Positionen in die beiden Listen
}

}
[/Java]
Gruß
Ralf

 

[Marco13]

Nochmal: Wenn das ganze später effizient sein soll, sollte man mit List<Float> etc. vorsichtig sein: Das boxing/unboxing kann da richtig teuer werden. Oder anders formuliert: Wenn die Matrizen so groß sind, dass es sich lohnt, etwas "sparse" zu machen, dauert das Rechnen mit diesen Matrizen quasi "prinzipbedingt" so lange, dass man boxing/unboxing und Map-Lookups nach Möglichkeit vermeiden sollte...