Hallo!
Ich habe gerade ein gewaltiges Problem: ICh mache ein Programm, dass eine gewaltige Hexkarte darstellt. Dies ist über eine Linked List gelöst, die in jeweils vier Richtungen verweist. Das Problem das ich nun allerdings habe ist, dass diese Hexkarte eine größe von über 1000 x 1000 feldern haben soll. Allerdings bekomme ich schon bei 100x100 ernste probleme mit dem Speicherplatz.
Diese Karte ist allerdings nur für das Anzeigen gedacht, also ist es egal, ob das was nicht am bildschirm ist (da passen ungefähr 40x80 von diesen Hexfeldern darauf) geladen ist oder nicht. Das problem ist nur, dass ich ja nicht alles, was nicht am Bildschirm ist, auf die Festplatte lagern kann - das würde ja zu lange zum scrollen dauern, oder?
Hat jemand eine idee wie man das Problem lösen könnte?

[sparrow]

Ich habe ein ähnliches Problem unter J2ME gehabt, Handys haben nie besonders viel Heap (es sei denn man kommt gleich mit s60v2 Kanonen *g*)
Ich habe das damals so gelöst, dass ich einfach nur die Bilder im Speicher halte die wirklich angezeigt werden, + 2 oder 3 Felder über den Bildschirmrand hinaus. Scrollt man dann wird die nächste Reihe nachgeladen. Dadurch, dass ja bereits einige Feldreihen mehr schon im Speicher sind fällt das nachladen nicht auf.

Moin,
bin neu hier und frage nur mal so aus Interesse (ist also leider keine Idee, dich dich weiterbringen wird

Warum benutzt Du eine Liste und kein Array? Ist das nicht ein recht großer Haufen Referenzen, der da im Speicher gehalten wird? und die Zugriffszeit bei Arrays ist doch auch deutlich besser als bei Listen. Frage nur, um heraus zu bekommen, welche Gedanken sich andere so beim hacken machen.

[Hot-Thunder]

Also so wie ich das sehe, kann er für die Speicherung eines HEX-Wertes bestenfalls ein String-Objekt oder ähnliche Objekte nehmen.
Also ist es doch egal, ob er eine Liste oder ein Array nimmt. Die Anzahl der Referenzen dürfte sich doch eigentlich nicht großartig unterscheiden.

Zu deinem Problem matt:
Ich hatte mal ähnliches Problem bei einem Programm. Dort konnte ich das aber durch einfache Griffe wie z.B. ersetzen von verschiedenen Datentypen durch andere, also z.B. String durch StringBuffer usw. lösen.
Vielleicht findest du ja auch eine möglichkeit. Wie wäre es denn, wenn du den Hexwert in eine Dezimalzahl umwandelst und dann in einem Array, wie final_guy schon sagte, abspeicherst?

Zitat von Hot-Thunder

Also so wie ich das sehe, kann er für die Speicherung eines HEX-Wertes bestenfalls ein String-Objekt oder ähnliche Objekte nehmen.
Also ist es doch egal, ob er eine Liste oder ein Array nimmt. Die Anzahl der Referenzen dürfte sich doch eigentlich nicht großartig unterscheiden.

Moin,
ich glaube zwar, das es nicht hierher gehört (sondern eher in einen theoretischen Bereich, wenn es hier so einen geben würde), aber ich möchte nur schnell klar machen was ich meinte, denn ich wurde offenbar falsch verstanden.
Bei einem Array (egal welchen Datentyps) handelt es sich doch um eine quasi direkte Map in den Speicher. Daher eine konstante Zugriffszeit bei den Operationen und nur eine Referenz + Offset. Bei einer Liste, in der jedes Element vier Nachbarn hat, kommt zu dem Datenteil jedes Elements noch je eine Referenz auf jeden der Nachbarn hinzu. Daher ist der Speicherbedarf (in diesem konkreten Fall) eindeutig größer als bei der Verwendung eines entsprechenden Arrays.

Man erkauft sich diese Platz- und Zeitersparnis jedoch durch eine unflexible Struktur. Das sollte aber bei einer Map fester größe kein Thema sein.

Korrigiert mich bzw. widersprecht mir gerne, wenn ihr anderer Meinung seid oder ich da falsch gedacht habe.

Gruß final_guy

[edit]
Kleine Überschlagsrechnung: Wenn man vier Byte pro Adressreferenz annimmt (32bit-Architektur), dann hat jedes Listenelement min. 16Byte an Referenzdaten gespeichert. Bei 1000x1000 = 10^6 Elementen ergibt das grob 16*10^6 Byte = 16MB.

Na ja, ist auch nicht die Welt, aber immerhin.

Ich bin mir aber nicht ganz sicher, wie groß Java-Object Referenzen sind. Bin daher vom virtuellen Speicher ausgegangen.
[/edit]

[Sym]

@Final_guy: Ist das auch bei Java so? Ich dachte, da wird alles als Referenz behandelt, selbst arrays. Ich hätte jetzt nicht gedacht, dass das da so ins Gewicht fällt.

Zum Problem: Hast Du Dir schon mal überlegt, ob man die Daten geschickt codieren könnte um somit den Speicherbedarf zu verringern?

[pago]

Bei einer Liste, in der jedes Element vier Nachbarn hat, kommt zu dem Datenteil jedes Elements noch je eine Referenz auf jeden der Nachbarn hinzu. Daher ist der Speicherbedarf (in diesem konkreten Fall) eindeutig größer als bei der Verwendung eines entsprechenden Arrays.

Der Teil ist schonmal falsch.
In der rt.jar gibt es mehrere "List"-Implementationen. Die, die du ansprichst, ist die "LinkedList". Es gibt darüber hinaus aber auch noch die "ArrayList", die intern ein Array verwendet.

Moin pago,
na ja, eigentlich reden wir ja gerade über eine LinkedList, denn die wurde ja ursprünglich von matt verwendet. Und auch wenn die von Dir angesprochene java.util.ArrayList intern ein Array verwendet, dann ist sie halt im eigentlichen Sinne keine Liste sondern eben ein Array, dass nur von außen aussieht wie eine Liste und das bei Hinzufügen von Elementen stets komplett vergrößert wird.

Es geht doch um die grundlegende Eigenschaft von Listen, dass sie in jedem Element mindestens eine Referenz auf einen Nachfolger besitzen müssen. Und je dichter die Verkettung ist, desto mehr Referenzen müssen gespeichert werden.

Meine Kernaussage wollte daher lauten, dass Arrays diesen Datenoffset nicht brauchen und daher schneller und kleiner sind wohingegen Listen zwar Langsamer und geringfügig größer sind aber dafür weitaus flexibler.

[pago]

Ich werde jetzt auch einen Einspruch verzichten, da deine "Kernaussage" wohl richtig ist.

Generell gilt in Java ja folgendes:
Statische Menge an Elementen: Array
Dynamische Menge an Elementen: ArrayList

Eine LinkedList wird immer dann verwendet, wenn die Liste wirklich extrem dynamisch ist, d.h. ständig Elemente hinzugefügt und entfernt werden.
Eine ArrayList wird immer dann verwendet, wenn es primär um das auslesen der Elemente geht, d.h. nicht andauernd dinge wie "list.remove(3); list.add(new Dingsda());" gemacht werden.
Laut Java Tutorial ist die ArrayList die Liste, die in den meisten Fällen verwendet werden sollte.
Eine ArrayList ist nur minimal größer als ein Array und der Zugriff ist beinahe identisch.

also mal um ein bisschen klarheit zu schaffen. Es handelt sich nicht um hex werte die gespeichert werden soll, sondern ein spielfeld mit sechseckigen Feldern

Was der vorteil von einem Array ist ist schnell gesagt: Diese Liste soll sich in alle Richtungen beliebig ausdehnen können - und das sehr dynamisch.

Das Problem bei Arrays ist, dass man ihre größe nachträglich nicht mehr verändern kann. Das bedeuted, will man hinten was anhängen, muss man ein neues array erstellen, dass größer ist und die daten in das neue Array kopieren. Will man hingegen vorne was anhängen muss man ein neues Array erstellen, das größer ist, und die daten in das neue kopieren - an einen anderen platz damit vorne etwas frei ist.

Arrays haben natürlich den Vorteil, dass sie praktisch sind, wenn man direkt addressierbare Daten verwendet - wenn man also weiss: zuerst benötigt man den 4 eintrag, dann den 6 oder so. Wenn man allerdings alle einträge der Reihe nach benötigt bzw. alle einträge die um einen Eintrag herum liegen ist eine LinkedList schon sehr viel praktischer. Wenn man dann Datenstrukturen wie Stacks oder Queues verwendet, ist es dann auch tausendmal besser, eine linked list zu verwenden, anstelle eines arrays.

Zitat von matt

also mal um ein bisschen klarheit zu schaffen. Es handelt sich nicht um hex werte die gespeichert werden soll, sondern ein spielfeld mit sechseckigen Feldern

Das war soweit klar. Aber es ist immer gut zu klären, ob man überdie gleiche Sache spricht

Zitat von matt

Was der Vorteil von einem Array ist ist schnell gesagt: Diese Liste soll sich in alle Richtungen beliebig ausdehnen können - und das sehr dynamisch.

Hier meinst Du wahrscheinlich den Vorteil der Liste und bist nur durcheinander gekommen, oder?

Zitat von matt

Das Problem bei Arrays ist, dass man ihre größe nachträglich nicht mehr verändern kann. Das bedeuted, will man hinten was anhängen, muss man ein neues array erstellen, dass größer ist und die daten in das neue Array kopieren. Will man hingegen vorne was anhängen muss man ein neues Array erstellen, das größer ist, und die daten in das neue kopieren - an einen anderen platz damit vorne etwas frei ist.

Jupp, noch einmal in einfachen Worten das Konzept eines Arrays wiedergegeben.

Zitat von matt

Arrays haben natürlich den Vorteil, dass sie praktisch sind, wenn man direkt addressierbare Daten verwendet - wenn man also weiss: zuerst benötigt man den 4 eintrag, dann den 6 oder so. Wenn man allerdings alle einträge der Reihe nach benötigt bzw. alle Einträge die um einen Eintrag herum liegen ist eine LinkedList schon sehr viel praktischer.

Da Thema mit dem direkten Speicherzugriff hatten wir ja schon angesprochen. Was die Komplexität des Zugriffs angeht, so könntest Du auch einfach ein zweidimensionales Array verwenden und hättest damit mMn einen mindestens ebenso intuitiven Zugriff auf die Felder des Spielfelds.

Zitat von matt

Wenn man dann Datenstrukturen wie Stacks oder Queues verwendet, ist es dann auch tausendmal besser, eine linked list zu verwenden, anstelle eines arrays.

Das zieht auch (hoffentlich) keiner in Zweifel.

Zitat von pago

Eine ArrayList ist nur minimal größer als ein Array und der Zugriff ist beinahe identisch.

Ist ja auch logisch, da ja wie Du selbst sagtest, die ArrayList intern ein Array ist. Das reimt sich sogar.

matt:

Wieso benutzt du eine Karte mit sechseckigen Feldern? Wenn du in 4 Richtungen scrollen willst, reichen da nicht viereckige Felder? Bei sechseckigen Feldern wird beim Scrollen nach z.B. Norden die Zeile die nach Nordosten und Nordwesten führt übersprungen. Meist sind Karten mit viereckigen Feldern speicherärmer. Was ist für dich so wichtig an sechseckigen Feldern?

Seit Java 1.5 finde ich die ArrayList, wegen ihrer Typsicherheit, sehr interessant. Ihre Größe wächst oder schrumpft dynamisch und ihre Objekte sind direkt ansprechbar. Ob sie beim Scrollen zu lange braucht steht in der javadoc:

Javadoc -> ArrayList:

"[...] The size, isEmpty, get, set, iterator, and listIterator operations run in constant time. The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking). The constant factor is low compared to that for the LinkedList implementation. [...] The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost. [...]"

Deshalb denke ich, dass ein sauberes Scrollen ohne Zwischenspeichern funktionieren könnte.

Bitte schreibe mir, was du davon hälst.