Auf ArrayList Elemente referenzieren?

[Cal]

Hey,
ich bin auf der Suche nach einem geeigneten Datentyp für folgendes Problem: ich möchte eine ungeordnete Liste (die dynamisch vergößerbar ist) die ich iterativ durchlaufen kann, in der ich in O(1) einfügen und löschen kann. Dazu muss ich noch auf die einzelnen Elemente referenzieren können.
Ich dachte eigentlich zuerst, dass dafür eine ArrayList gut geeignet ist. Kann ich da auf die einzelnen Elemente per Referenz zugreifen? Falls ja, wie kriege ich den Index des zuletzt eingefügten Elements heraus? (Suchen erscheint mir zu teuer)

naja ...ich hoffe mir kann jmd weiterhelfen

Gruß
Cal

 

[maki]

ich möchte eine ungeordnete Liste (die dynamisch vergößerbar ist) die ich iterativ durchlaufen kann, in der ich in O(1) einfügen und löschen kann. Dazu muss ich noch auf die einzelnen Elemente referenzieren können.

Wenn du keine Indexbasierten Zugriffe (zB. get(2)) vorhast, solltest du LinkedList verwenden.
Am besten für Referenzen nur List verwenden, dann kannst du auch mit anderen Implementierungen expirementieren.

wie kriege ich den Index des zuletzt eingefügten Elements heraus?

Verstehe die Frage nicht..

add

public boolean add(E o)

Appends the specified element to the end of this list.

 

[Cal]

Hey, erstmal danke für deine Antwort.
Also ich möchte per Index auf die Elemente zugreifen. deswegen dachte ich an eine ArrayList.

Ich habe also eine ArrayList in die ich Elemente einfügen möchte. Gleichzeitig habe ich mehrere Arrays in denen ich die Indizes dieser Elemente einfüge. D.h. ich möchte ein Element in die Arraylist einfügen und gleichzeitig seinen Index in ein anderes Array schreiben

Allerdings habe ich keine ArrayList Methode gefunden mit der ich herausbekommen kann, welchen Index das Element hat welches ich gerade eingefügt habe. (Bis auf die methode IndexOf(Object), mit der ich nach meinem gerade eingefügten Element suchen könnte. was aber ganz sicher nicht in linearzeit passiert)

Hoffe das ist jetzt verständlicher

 

[maki]

Index eines Elementes merken ist ein Indiz dafür, dass du dir mal die Maps des Collection Frameworks ansehen solltest.

Aber wenn du weisst dass du mit add(o) ein Element am Ende der Liste einfügst, dann könntest du auch nach der Größe der Liste fragen um deinen Index herauszufinden, oder?

 

[Cal]

Index eines Elementes merken ist ein Indiz dafür, dass du dir mal die Maps des Collection Frameworks ansehen solltest.

Ah, das hört sich gut. Ich werd mir das mal genauer ansehen

Aber wenn du weisst dass du mit add(o) ein Element am Ende der Liste einfügst, dann könntest du auch nach der Größe der Liste fragen um deinen Index herauszufinden, oder?

Ja, du hast recht. size würde klappen. ich dachte der dtaentyp funktioniert etwas anders.
Ich hab gerade nochmal in der Java API nachgelesen und gesehen, dass ArrayList wohl ungeeignet ist für mein Problem, da die remove(i) Operation einen index-shift nach sich zieht. Damit wäre dann auch mein Mapping im Eimer. :/

Haste vlt noch nen anderen Vorschlag wie ich das Problem lösen könnte?

 

[Marco13]

Hm. Sich präzise auszudrücken ist so eine Sache. :?

Mal der Reihe nach
ich möchte eine ungeordnete Liste
Was ein Widerspruch in sich ist.

(die dynamisch vergößerbar ist)

Bis hierhin gehe ich davon aus, dass du etwa sowas meinst wie
"Ich brauche eine Datenstruktur etwas, worin ich eine Menge von Objekten speichern kann. Die Reihenfolge der Objekte spielt keine Rolle (d.h. die Elemente können geordnet sein, aber es ist keine Anforderung)"

Falls dem so ist, würde bisher glaubich noch fast alles funktionieren, was eine Collection ist: http://java.sun.com/docs/books/tutorial/collections/interfaces/collection.html

Weiter geht's

die ich iterativ durchlaufen kann
Ja, Collection tut's immernoch...

in der ich in O(1) einfügen und löschen kann
Aha - jetzt wird's interessant. Wenn du z.B. eine geordnete Menge hättest und (nur am Anfang) oder (nur am Ende) entfernen wolltest, würde es eine List tun
http://java.sun.com/docs/books/tutorial/collections/interfaces/list.html

Dazu muss ich noch auf die einzelnen Elemente referenzieren können.
Das klingt jetzt aber, als wolltest du NICHT ((nur am Anfang) oder (nur am Ende)) löschen, sondern auch mittendrin, Elemente deren Index du nicht kennst, und deren Index du auch nicht raussuchen willst. Dann käme eigentlich nur eine Set in Frage.
http://java.sun.com/docs/books/tutorial/collections/interfaces/set.html
Diese ist nichtmehr geordnet (außer bei einer TreeSet, wenn die ELemente Comparable sind oder ein Comparator angeboten wird)

Aber dann sowas
Ich dachte eigentlich zuerst, dass dafür eine ArrayList gut geeignet ist. Kann ich da auf die einzelnen Elemente per Referenz zugreifen? Falls ja, wie kriege ich den Index des zuletzt eingefügten Elements heraus? (Suchen erscheint mir zu teuer)
Wenn man ein Element hat, das in einer ArrayList liegt, und man kennt den Index nicht, dann kann man den index NUR durch Suchen herausfinden.

Bisher wäre die Antwort also gewesen: Ein Set http://java.sun.com/docs/books/tutorial/collections/interfaces/set.html erfüllt deine Anforderungen.

Aber dann kommt im nächsten Beitrag
Also ich möchte per Index auf die Elemente zugreifen. deswegen dachte ich an eine ArrayList.

Jo, womit die Set wieder rausfliegt. :roll:

Weiter...
Ich habe also eine ArrayList...
das steht jetzt fest? ???:L
... in die ich Elemente einfügen möchte. Gleichzeitig habe ich mehrere Arrays in denen ich die Indizes dieser Elemente einfüge. D.h. ich möchte ein Element in die Arraylist einfügen und gleichzeitig seinen Index in ein anderes Array schreiben.
Allerdings habe ich keine ArrayList Methode gefunden mit der ich herausbekommen kann, welchen Index das Element hat welches ich gerade eingefügt habe.
Wenn du das Element mit "list.add(element)" einfügst, dann ist der Index des eingefügten Elementes gerade "list.size()-1". Wenn du das element mit "list.add(index,element)" einfügst, dann ist der Index des eingefügten Elementes gerade 'index'.

(Bis auf die methode IndexOf(Object), mit der ich nach meinem gerade eingefügten Element suchen könnte. was aber ganz sicher nicht in linearzeit passiert)
Linear schon, aber nicht konstant. Und das war ja mal irgendwann irgendwo aus irgendeinem Grund irgendeine Anforderung.


Ich hab gerade nochmal in der Java API nachgelesen...
:shock: Wie kommst du denn auf die verrückte Idee, in der API Doku nachzulesen, obwohl du erst so wenigen Leute so wenige Tage lang mit widersprüchlichen, wirren Fragen beschäftigt hast? Also, mach' die Doku zu. In der Doku steht nichts, was nicht auch hier im Forum beantwortet werden könnte. (jaja, Sarkasmus und so, sonst nimmst du das noch ernst.... :roll: )

...und gesehen, dass ArrayList wohl ungeeignet ist für mein Problem, da die remove(i) Operation einen index-shift nach sich zieht. Damit wäre dann auch mein Mapping im Eimer.

Ja, jetzt geht es auf einmal um ein "Mapping". Wie sich eine "Map" zu einer anderen "Collection" verhält, sieht man ja auf dem Bild auf dieser Seite: http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html - sie haben NICHTS miteinander zu tun!

Also.

Beschreib' nochmal, was du machen willst.
- Bemühe dich, keine falschen Aussagen zu machen
- Mache keine ungerechtfertigten Annahmen
- Versuche, nicht zu vergessen, spezielle Anforderungen an die gesuchte Datenstruktur zu nennen

 

[Ark]

Kann ich da auf die einzelnen Elemente per Referenz zugreifen?

Du kannst immer auf ein Objekt zugreifen, wenn du die Referenz kennst. Ich glaube, du hast etwas grundlegendes nicht verstanden: In einer List (oder anderen Datenstrukturen) werden nicht die Objekte selbst aufbewahrt, sondern nur Referenzen auf diese. Ein Objekt kann in einer List referenziert sein und gleichzeitig in einer Map, und trotzdem gibt es dieses Objekt nur einmal!

Wenn du nun die Referenz auf ein Objekt in einer List haben möchtest, musst du wissen, das wie vielte Element es ist. Eine List speichert zudem ihre eigene Größe, von daher sollte es kein Problem sein, den Index auf das letzte Element zu ermitteln,

Wenn die Reihenfolge keine Rolle spielt und ein Element nur einmal in der Datenstruktur vorhanden ist, spricht man von einer Menge (Set) und nicht von einer Folge (List). Du solltest dir hier noch mal Gedanken darüber machen, was genau du eigentlich willst. (Vielleicht willst du ja einen Stack? Who knows ...)

Ark

EDIT: Ich würde vorschlagen, dass du mal ganz konkret wirst und sagst, was genau du erreichen willst und worum es geht.

Ark

 

[Cal]

Also gut... Du hast recht meine Aussagen sind zum Teil widersprühlich und wirr, weil ich wohl immernoch in der "Problemformulierungsphase" war und ich noch nicht ganz klar über meine Anforderungen war. Ich versuche einfach nochmal mein Problem möglichst simpel und allgemein zu formulieren (Referenz bitte nicht im Java oder Pointer Sinn interpretieren):

Ich habe eine Menge M von Objekten die ich zentral ungeordnet abspeichere (das wäre dann wohl ein Set?!). Diese Menge muss ich erweitern können (am Ende), Elemente entfernen können (mittendrin) und iterativ durchlaufen können. Ausserdem möchte ich auf die Elemente über einen Index zugreifen können.

Als zweites habe ich nun mehrere Arrays A1,...An, welche auf bestimmte Elemente in M referenzieren sollen.

Wenn ich also in M ein neues Element einfüge, soll gleichzeitig in z.b. A1 eine Referenz auf das eingefügte Element in M geschrieben werden.
Wenn ich aus M ein Element entferne, soll gleichzeitig die Referenz in Ax gelöscht werden.

Und nochmal mein Problem praktisch (und noch allgemeiner) formuliert:
Ich habe eine Menge an Entitäten, die ich in Gruppen einteilen möchte. Ich möchte sowohl auf einzelne Entitäten zugreifen können, als mir auch eine Liste aller zu einer Gruppe gehörenden Entitäten ausgeben lassen. Ausserdem möchte ich Entitäten hinzufügen, löschen, und ihre Gruppenzugehörigkeit ändern können.
Und das mit möglichst kurzer Laufzeit, weil es für eine Echtzeitsimulation verwendet wird. (häufigste Operationen sind Gruppenwechsel,auflisten von Gruppen und auf einzelne Elemente zugreifen)

Also ich hoffe das ist jetzt wiederspruchsfrei und klarer formuliert. Im übrigen entschuldige ich mich für meine Unwissenheit über einige Java Klassen... Meine Mama hat mir leider nicht jeden abend aus der Java API Doku vorgelesen als ich noch klein(er) war. Deswegen muss mir das alles selber erarbeiten.

 

[Cal]

ähh... jetzt nachdem ich euch das Problem erläutert habe und nochmal durchgegangen bin, glaube ich es wäre das beste einfach die Gruppenzugehörigkeit in der Entität zu speichern (nur ein Set anlegen).
Dann muss ich die komplette Entitäten Liste zwar mehrfach durchlaufen mit jeweils n Vergleichen, aber da die Gruppenanzahl konstant bleibt. und der ganze Rest (bis auf löschen) in O(1) geht. Wäre die (naheliegenste) Variante wohl auch die sinnvollste... :/

 

[Marco13]

OK. Wie der indizierte Zugriff genau aussehen soll, ist noch nicht ganz klar. Also, welche indizes sollen das sein? Sollen sie fortlaufend von 0 bis elementAnzahl sein? Wenn ja, was soll passieren, wenn man ein Element mittendrin löscht? Soll innerhalb der Gruppen auch indiziert zugeriffen werden können?

Trotzdem mal ein grober(!) Versuch (!) das ganze zusammenzufassen....

class Data
{
    // Map für "indizierten" Zugriff
    private Map<Integer, Element> elements = new HashMap<Integer, Element>();

    // Speicherung der Indizes der Elemente
    private Map<Element, Integer> indices = new HashMap<Element, Integer>();

    // Gruppen
    private Set<Element> groups[] = new Set<Element>[NUM_GROUPS];

    // Fügt ein Element mit dem gegebenen zu den Elementen und zur angegebenen Gruppe hinzu - O(1)
    public void add(Element element, int index, int groupIndex)
    {
        elements.put(index, element);
        indices.put(element, index);
        groups[groupIndex].add(element);
    }

    // Löscht das gegebene Element aus der Menge aller Elemente, und aus allen Gruppen - O(1)
    public void remove(Element element)
    {
        Integer index = indices.get(element);
        elements.remove(index);
        indices.remove(element);
        for (Set<Element> group : groups) group.remove(element);
    }

    // Gibt das Element mit dem angegebenen Index zurück - O(1)
    public Element get(int index)
    {
        return elements.get(index);
    }

    // Ändert die Gruppe des gegebeben Elements - O(1)
    public void changeGroup(Element element, int oldGroupIndex, int newGroupIndex)
    {
        groups[oldGroupIndex].remove(element);
        groups[newGroupIndex].add(element);
    }

    // Gibt eine Set zurück, die eine Ansicht auf die angegebene Gruppe darstellt - O(1)
    public Set<Element> getGroup(int groupIndex)
    { 
        return Collections.unmodifiableSet(groups[groupIndex]);
    }
}

Je nachdem, wie der indizierte Zugriff genau sein soll, könnte eine andere Modellierung auch "sinnvoller" sein, etwa das ganze als eine "HierarchicalIndexedSet" zu implementieren, der man im Konstruktor mitgibt, wie viele Untergruppen sie haben soll - und die Untergruppen sind wieder HierarchicalIndexedSets ... Aber... erstmal abwarten, ob die Anforderungen so erfüllt sind, wie du sie gemeint hast....

 

[Marco13]

Vielleicht noch als Nachtrag: Du hattest gemeint, dass die Gruppe in den Elementen gespeichert werden könnte. Das könnte einiges "einfacher" machen, aber man sollte sich überlegen, ob die Gruppenzugehörigkeit wirklich eine Eigenschaft des Elements ist - oder ob ein und dasselbe Element vielleicht mal in verschiedenen "Data"-Sets liegen könnte, und dort dann verschiedenen Gruppen angehören muss....

 

[Murray]

Liegt nicht hier

Ich habe eine Menge M von Objekten die ich zentral ungeordnet abspeichere (das wäre dann wohl ein
Set?!). Diese Menge muss ich erweitern können (am Ende), Elemente entfernen können (mittendrin) und iterativ durchlaufen können. Ausserdem möchte ich auf die Elemente über einen Index zugreifen können.

bereits ein Widerspruch vor? Wenn eine Menge inhärent ungeordnet ist, dann kann man doch die Postion, an der ein neues Element eingefügt wird, nicht beeinflussen - eigentlich haben die Elemente wohl überhaupt keine sinnvolle Positionseigenschaft Und ein Index-Zugriff setzt doch wohl irgendeine Ordnung voraus... ???:L

 

[Marco13]

Wie auch immer - wenn der Post mit dem "Jetzt hab ich's endlich!" kommt, ist hoffentlich Code dabei, damit man mal sieht, was eigentlich gemeint war, und exemplarisch schreiben könnte, was hätte gefragt werden müssen, um gleich die richtige Antwort zu bekommen... :wink:

 

[Ark]

Liegt nicht hier

Ich habe eine Menge M von Objekten die ich zentral ungeordnet abspeichere (das wäre dann wohl ein
Set?!). Diese Menge muss ich erweitern können (am Ende), Elemente entfernen können (mittendrin) und iterativ durchlaufen können. Ausserdem möchte ich auf die Elemente über einen Index zugreifen können.

bereits ein Widerspruch vor? Wenn eine Menge inhärent ungeordnet ist, dann kann man doch die Postion, an der ein neues Element eingefügt wird, nicht beeinflussen - eigentlich haben die Elemente wohl überhaupt keine sinnvolle Positionseigenschaft Und ein Index-Zugriff setzt doch wohl irgendeine Ordnung voraus... ???:L

In einer Folge (List) kann man klar sagen, dass ein bestimmtes Element unmittelbarer Vorgänger oder Nachfolger eines anderen Elements ist (darauf baut z.B. vor allem eine LinkedList). In einer Menge (Set) spielt die genaue Zuordnung von Vorgänger bzw. Nachgänger keine Rolle. Es reicht, falls es sich um eine geordnete Menge (SortedSet) handelt, wenn man sagen kann, dass ein Element "größer" bzw. "kleiner" ist (Comparable), unter Umständen existiert eine solche Ordnung aber nicht (oder sie ergibt keinen Sinn).

Ark

 

[Cal]

Hey, ersteinmal danke für die wirklich gute Hilfe hier.
Ich habe dieses Problem jetzt ersteinmal kurz beseite geschoben und einfach nur - wie schon beschrieben - mit einer einzigen ArrayList und jeweiligem bruteforce "Herausfiltern" der Gruppen, druch ein Gruppenattribut in jeder Entität realisiert. Sobald ich den rest der Simulation implementiert habe (es handelt sich übrigens um die Simulation von großen Menschenmengen, wie sich realistisch gegenseitig ausweichen, linien formen, usw...) , werde ich dann nochmal versuchen die Stelle mit deinem Tipp zu optimieren. Und dann meld ich mich auch nochmal obs funktioniert hat.

OK. Wie der indizierte Zugriff genau aussehen soll, ist noch nicht ganz klar. Also, welche indizes sollen das sein? Sollen sie fortlaufend von 0 bis elementAnzahl sein? Wenn ja, was soll passieren, wenn man ein Element mittendrin löscht? Soll innerhalb der Gruppen auch indiziert zugeriffen werden können?

der indizierte Zugriff muss nur global erfolgen. innerhalb einer Gruppe ist das egal. Fortlaufende Numerierung ist auch unwichtig. Allerdings muss ich die Menge halt itartiv durchlaufen können.

Ich verstehe Marco13s Ansatz allerdings nicht ganz. Geht bei changeGroup nicht die Zuordnung zwischen dem Set und den Maps verloren? und habe ich etwa jedes Objekt dreifach abgespeichert?! :/ kenne mich leider nicht mit der Java Hashmap aus. [/quote]

 

[Marco13]

Die Objekte sind nicht mehrfach gespeichert, aber Referenzen auf die Objekte. (Das ist auch unschön, aber wenn man "für ALLES" eine Laufzeit von O(1) fordert, hat man nicht soooo viele Möglichkeiten - wie so oft: Der Tradeoff zwischen Laufzeit und Speicherplatz....). Irgendwelche Zuordnungen gehen da ber nicht verloren ... wüßte zumindest nicht, wo: In ChangeGroups wird die Referenz auf das Element aus einer Gruppe entfernt und zur anderen hinzugefügt.

Trotzdem ist das mit dem indizierten Zugriff nicht klar: Wozu brauchst du indizierten Zugriff, wenn du nicht weißt, welches Element an einem bestimmten Index stehen oder stehen kann, und sich der Index auch beliebig ändern kann? Ich würde jetzt nur die Möglichkeit sehen, dass du mit einer for-Schleife drüberlaufen willst, aber ... die braucht man ja häufig garnicht, wenn man mit einem Iterator drüberlaufen kann (d.h. wenn die Klasse zum Beispiel "Iterable" implementiert). Dann kann man ja statt

for (int i=0; i<10; i++) 
{
    Element element = data.getElement(i);
    element.doSomething();
}

einfach

for (Element element : data) element.doSomething();

schreiben... ???:L Aber vielleicht gibt's noch einen anderen Grund ... z.B. ein "echt zufälliges" Herauspicken von einzelnen (beliebigen) Elementen oder so... ???:L

 

[Cal]

Die Objekte sind nicht mehrfach gespeichert, aber Referenzen auf die Objekte. (Das ist auch unschön, aber wenn man "für ALLES" eine Laufzeit von O(1) fordert, hat man nicht soooo viele Möglichkeiten - wie so oft: Der Tradeoff zwischen Laufzeit und Speicherplatz....). Irgendwelche Zuordnungen gehen da ber nicht verloren ... wüßte zumindest nicht, wo: In ChangeGroups wird die Referenz auf das Element aus einer Gruppe entfernt und zur anderen hinzugefügt.

hmm... ja du hast wohl recht. Ich sollte wohl besser bei c++ bleiben, da werde refrenzen wenigstens eindeutig gekennzeichnet... bin da irgendwie durcheinander gekommen.

Trotzdem ist das mit dem indizierten Zugriff nicht klar: Wozu brauchst du indizierten Zugriff, wenn du nicht weißt, welches Element an einem bestimmten Index stehen oder stehen kann, und sich der Index auch beliebig ändern kann? Ich würde jetzt nur die Möglichkeit sehen, dass du mit einer for-Schleife drüberlaufen willst, aber ... die braucht man ja häufig garnicht, wenn man mit einem Iterator drüberlaufen kann (d.h. wenn die Klasse zum Beispiel "Iterable" implementiert). Dann kann man ja statt

das verstehe ich nicht, wieso ändern sich die Indices in deinem Beispiel denn beliebig? Die sollten doch eigentlich beibehalten werden durch die Hashmap?!

 

[Marco13]

Ich sollte wohl besser bei c++ bleiben, da werde refrenzen wenigstens eindeutig gekennzeichnet...
Bleib lieber bei Java: Da GIBT es (bei nicht-primitiven Datentypen) nur "Referenzen" :wink: (Wobei eine Java-Referenz eigentlich eher einem C++-Pointer entspricht - eine Analogie zu C++-Referenzen gibt es in Java nicht)

das verstehe ich nicht, wieso ändern sich die Indices in deinem Beispiel denn beliebig? Die sollten doch eigentlich beibehalten werden durch die Hashmap?!
In dem Beispiel ändern sie sich natürlich nicht. Das ist ja extra so geschrieben, dass es (soweit das möglich war) dem entspricht, was du an Anforderungen zusammengewüfelt hast. Dann hast du aber u.A. von einer "ungeordneten Liste" gesprochen, und davon, dass Elemente entfernt werden können, deren Index nicht bekannt ist. Wozu genau brauchst du also die Indizes bzw. den indizierten Zugriff?