Belegt "null" Speicher?

[Patneu]

Hallo zusammen,

ich weiß nicht ob die Frage schonmal gestellt wurde, wenn ja habe ich sie nicht finden können.

Meine Frage ist, ob / wie viel Speicher (heap space - was stellt man sich darunter eigentlich genau vor?) eine Referenz auf "null" benötigt (abgesehen vom Bezeichner der Variablen etc.)?

Hintergrund der Frage ist, dass ich in einem Programm ein int-Array habe, welches ziemlich groß ist, wobei die Größe vom Benutzer festgelegt wird. Es ist ein zweidimensionales Array, wobei die Größe der ersten Dimension nach oben offen ist (aber vermutlich nicht höher als 100 liegen wird) und die zweite Dimension maximal 9999 Felder hat.

Problematisch dabei ist, dass viele (eigentlich die meisten) Felder des Arrays wahrscheinlich "leer bleiben" werden. Nun habe ich bei der bisherigen Recherche im Forum gelesen, dass int-Werte prinzipiell erstmal "0" sind, wenn ihnen kein anderer Wert zugewiesen wird. Da eine 0 ja den selben Speicher verbraucht, wie jeder andere int-Wert, ist das natürlich, wenn die meisten Felder gar keinen Wert haben müss(t)en, sehr unpraktisch.

Deshalb habe ich überlegt, anstatt eines int-Array ein Integer-Array zu verwenden, da die nicht benötigten Felder dann auf "null" verweisen könn(t)en. Wie ich das verstanden habe, sollten sie das standard-mäßig auch tun?



Meine Frage ist also im Prinzip: Bringt das etwas bzw. das, was ich mir davon erhoffe? Spare ich so wirklich Speicher und wenn ja, wie viel?
Und falls mir das nichts bringen sollte: Wie könnte ich hier sonst Speicher gewinnen? Oder muss ich zwingend den Speicher erhöhen?

Danke schon im Voraus für alle antworten. =)

 

[HoaX]

Nö, bringt dir nix.
Benutz doch eine/mehrere Maps, z.B. HashMap.

 

[thorstennn]

ein int belegt höchstwahrscheinlich 32 Bit, eine Referenz, egal ob null oder nicht, wird auch soviel Bit belegen

 

[Volvagia]

Wenn du ein Array aus 999.900 Feldern hast, von denen du nur kleine Teile benutzt, solltest du vermutlich dringend dein Design überdenken.

 

[Patneu]

Wenn es nur so einfach wäre... *seufz*

Leider ist es so, dass allen Feldern des Arrays prinzipiell Werte zugewiesen werden könnten, das hängt von den Eingaben des Benutzers ab. Praktisch wird aber meist nur ein sehr geringer Anteil der Felder Verwendung finden - das werden aber immer unterschiedliche Felder sein.

Bis jetzt ist mir leider noch keine brillante Idee gekommen, wie ich das anders lösen könnte, deshalb hatte ich gehofft, ich könnte irgendwie den Speicherbedarf reduzieren. Aber wenn das nicht möglich ist, heißt es wohl wieder: Zurück ans Zeichenbrett.

 

[nrg]

mach dir doch ne HashMap<Integer, Integer> oder sowas. was du mit dem array willst, verstehe ich grad überhaupt nicht.

 

[Patneu]

HashMap hatte ich mir bis jetzt noch gar nicht angeschaut. Habe das grade mal kurz überflogen und sieht tatsächlich so aus, als könnte es das sein, was ich suche. =) Muss mich da mal genauer reinlesen, auf jeden Fall schonmal danke für die Hilfe.

 

[thorstennn]

HashMap hat alle Vorteile von Arrays und minimiert gleichzeitig deren Nachteile - es ist die masterLoesung - ich würde davon abraten

 

[fastjack]

ich würde davon abraten

hm. warum denn? Erklär' mal bitte.

 

[Landei]

Wenn es um sehr viele Werte geht, würde ich anstatt von [c]HashMap[/c] eine auf [c]int[/c] spezialisierte Lösung vorschlagen, etwa TIntIntHashMap (GNU Trove for Java API v2.1.0)

 

[faetzminator]

Ganz abgesehen von den Lösungsvorschlägen der anderen, hier noch eine direkte Antwort auf deine Frage.
Eine Referenz auf [c]null[/c] ist genau gleich wie eine auf ein existierendes Objekt. Ein int benötigt 4 Bytes (32bit), eine Referenz je nach Implementierung mehr oder weniger Speicher. IMHO ist dies bei den Sun JVMs bei 32bit Systemen (logischerweise) 32bit und bei 64bit Systemen dementsprechend 64bit.

 

[fastjack]

@Landei genau, das schreit ja förmlich nach einer Map. Ich verstehe nur nicht, warum Thorstenn, obwohl er es für die "masterLoesung" hält, davon abrät.

 

[thorstenthor]

Es geht doch darum, etwas zu lernen, von daher greift man nicht zur Fertiglösung, sondern beschränkt sich vorerst erst mal nur auf Felder und Listen! Nur so kommt man weiter.

 

[Empire Phoenix]

Also erstmal solltest dud ir überlegen was du brachst:

Einige hundert x,y Korrdianen denen ein int zugeweisen ist.
Damit wäre die primitive lösung erstmal eine ArrayList mit XYInteger elementen
class XYInteger{
public int x;
public int y;
public int value;
}
dies spart schonmal allen platz den die nullen brauchen.
Nachteil beim zugriff auf ein bestimmtes Element müssen alle vorhandenen durchsucht werden, bis man das richtige findet.
-> Indexstructur
-> array aus x Hashmaps ( X weil x <= 100 und y<=9999 laut afugabe)
-> diese hashmaps leer lassen solange keine Daten eingetragen werden.
-> du brauchst nur add, get (und evtl remove)

public void add(int x,int y, int value){
yhashmap = xhashmap.get(x)
if(yhashmap == null){
yhashmap = new HAshmap();
xhasmap.put(x,yhashmap);
}
yhashmap.put(y,value);
}

public int get(x,y){
yhasmap = xhashmap.get(x)
if(yhashmap == null){
return 0;
}
return yhashmap.get(y);
}

Ungefähr so. jetzt bei bedarf noch ne clear funktion einbauen, die die XHasmap cleart, sowie die typen bei den hasmaps angeben,
und das alles in eine Klasse packen, dass du nicht direkt auf den hasmaps arbeiten musst,(und bei bedarf die unterliegende implementierung weiter anpassen kannst ohne das programm zu verändern)

Bei remove würde man die yhasmap suchen den wert killen, dann prüfen ob mehr als 0 drinnen sind, wenn nciht die yshamap aus der xhashmap killen

 

[thorstenthor]

Was hast du denn geraucht? :roll:

 

[Landei]

@EmpirePhoenix: Diese Idee gibt es auch konsequent zuende gedacht: Quadtree ? Wikipedia

 

[fastjack]

Es geht doch darum, etwas zu lernen, von daher greift man nicht zur Fertiglösung, sondern beschränkt sich vorerst erst mal nur auf Felder und Listen! Nur so kommt man weiter.

Hier steht nix davon das er noch lernen will, er beschreibt ein Problem und dessen Lösung ist nun mal der Einsatz einer Map, die ja wohl auch zu den Grunddatenstrukturen gehört.

Was hast du denn geraucht?

EmpirePhoenix gibt wenigstens Vorschläge, was man bei deinen Beiträgen vermißt (wenn Du vorher thorstennn warst).

 

[Patneu]

Also ich würde nie so vermessen sein, zu denken, ich müsste nichts mehr lernen. Ich habe bisher 100%ig erst einen winzigen Ausschnitt dessen gesehen, was Java so alles kann.

Unter anderem ist das auch der Grund, warum ich mit Arrays zu arbeiten versucht habe und nicht mit Hashmaps. Ich wusste schlicht nicht, dass es die überhaupt gibt und dass sie sich für mein Problem eignen könnten.

Nach allem, was ich mir nun darüber angelesen habe, scheinen mir Hashmaps ideal um mein Speicher-Problem zu lösen, insbesondere, da ich auch noch weitere solcher "Verzeichnisse" brauchen werde, die aller Wahrscheinlichkeit noch mehr Dimensionen und/oder potenzielle Felder haben werden.

Das einzige, was mir noch nicht ganz klar ist, ist ob es nötig sein wird, die Hashmaps zu synchronisieren und wie genau man das macht. Es wird ja ausdrücklich empfohlen, wenn mehrere "Threads" auf die Hashmap zugreifen. Was genau versteht man aber unter einem Thread? Muss ich die Hashmap bereits synchronisieren, wenn mehrere Methoden darauf zugreifen können oder nur dann, wenn mehrere Instanzen des Programms darauf zugreifen?

 

[Landei]

Mit Threads kommst du nur in Berührung, wenn du selbst damit anfängst, oder hin und wieder bei grafischen Oberflächen wie Swing (wo die Threading-Probleme meistens leicht zu lösen sind), also mache dir darüber erst mal keinen Kopf.

 

[thorstenthor]

Und wenn dann verwendeste eben java.util.Collections.html#synchronizedMap(java.util.Map)

Aber die Wurzel allen Übels liegt bei der Optimierung von Programmen

Anders als fastjack würde ich nicht behaupten, HashMap gehöre zu den "Grunddatenstruckturen - mit kleinen Schritten kommst du eher zum Ziel

 

[faetzminator]

Anders als fastjack würde ich nicht behaupten, HashMap gehöre zu den "Grunddatenstruckturen [..]

Arrays sollte man am Besten - sobald man .lenth und [index] kennt - in den Wind schiessen, ausser man muss eine neue Collection bauen.

Zweitens denke ich, dass man alle Collections (List, Set, Queue, ...) kennen und diese auch einsetzen sollte. Warum das Rad neu erfinden? Wenn man sich für die Logik dahinter interessiert, muss man die Klasse nicht nachbauen, sondern kann einfach im Source (von J2SE) nachschauen.

 

[fastjack]

Datenstruktur ? Wikipedia

@thorstenthor unter "Grundlegende Datenstrukturen" kannst Du nachlesen, was man so im Allgemeinen kennen sollte, eben die Basics.

@PatNeu natürlich sollst Du lernen Die Map ist aber nun mal die beste Lösung für Dein Problem, ob Du Dir sie jetzt selbst baust oder eine vorhandene nutzt (Map ist auch nur das Interface).

 

[thorstennn]

Arrays sollte man am Besten - sobald man .lenth und [index] kennt - in den Wind schiessen, ausser man muss eine neue Collection bauen.

ich denken, man kann sagen, weit mehr als die Hälfte anderer Datenstruckturen beruhen auf Feldern. Solch Essentielles zu vernachlässigen wäre für mich nicht der richtige Weg.

Datenstruktur ? Wikipedia

@thorstenthor unter "Grundlegende Datenstrukturen" kannst Du nachlesen, was man so im Allgemeinen kennen sollte, eben die Basics.

Grunddatenstrucktur finde ich dort gar nicht, hast du dir das etwa ausgedacht? Oder kombinierst du gerade irgendwelche Fachbegriffe, die du mal in einer Vorlesung gehört hast, neu? Jedenfalls ist deine Argumention für mich nicht überzeugend.

 

[faetzminator]

ich denken, man kann sagen, weit mehr als die Hälfte anderer Datenstruckturen beruhen auf Feldern. Solch Essentielles zu vernachlässigen wäre für mich nicht der richtige Weg.

Arrays in Java sind zwar insofern essentiell, dass eben diese Typen darauf beruhen. Aber wenn du etwas Erfahrung hast, dann weisst du genau so gut wie ich, dass die Integration von Arrays (bzw. der Umgang mit dessen) in Java einfach sche*sse ist. Als Beispiele wären da Autoboxing und Generics zu nennen...

 

[Tomate_Salat]

Es wird ja ausdrücklich empfohlen, wenn mehrere "Threads" auf die Hashmap zugreifen. Was genau versteht man aber unter einem Thread? Muss ich die Hashmap bereits synchronisieren, wenn mehrere Methoden darauf zugreifen können?

Ergänzend zu dem gesagten: Ein Thread kann nicht mehrere Methoden gleichzeitig ausführen, dafür bräuchtest du schon 2..* . Solange du keine eigenen Threads erstellst, bist du i.d.R auf der sicheren Seite (auch wenn eine GUI im Spiel ist)

... zu Thorsten* brauche ich nichts zu sagen. Wie sinnvoll sein Vorschlag der eigenen Implementierung ist, sieht man schon daran, dass er mit der Meinung anscheinend komplett alleine steht.

 

[thorstennn]

... zu Thorsten* brauche ich nichts zu sagen. Wie sinnvoll sein Vorschlag der eigenen Implementierung ist, sieht man schon daran, dass er mit der Meinung anscheinend komplett alleine steht.

ROFL Welcher Vorschlag? Ich hab lediglich gesagt, welche Lernstrategie am ehesten zum Erfolg führt. Das Reininterpretierte von dir kann mir sicher keiner als Fehler anrechnen. Wäre ja noch schöner

Im Übrigen ist man bei der GUI-Programmierung schnell in dem Fall, 2..* Threads zu haben. Aber ach was - mit nem Pubertierling zu argumentieren bringt eh nichts