[JAVA] collectie en registreren van elementen

[Verwijderd]

Hallo allemaal,

Ik ben een collectie (een priority queue, die het efficient verwijderen van een element (log n) en het efficient verlagen/verhogen van de key van een element (log n) ondersteunt) aan het implementeren. Ik geef even een fragment van de implementatie (een aantal dingen zijn weggelaten, voor de eenvoud):

Java:

interface Element <E> {
    E getElement();
}

class MijnCollectie <E> {
    private MijnCollectieElement[] elements;
    private int size = 0;

    public MijnCollectie(int size) {
        elements = new MijnCollectieElement[size];
    }

    public Element<E> add(E element) {
        MijnCollectieElement e = new MijnCollectieElement(element);
        elements[size++] = e;
        return e;
    }

    public void remove(Element<E> element) {
        /* controleer of element aangemaakt is door deze collectie */
        if (!(element instanceof MijnCollectieElement)) {
            throw new RuntimeException(); // niet aangemaakt door deze collectie
        }
        MijnCollectieElement e = (MijnCollectieElement) element;
        if (e.getCollectie() != this) {
            throw new RuntimeException(); // niet aangemaakt door deze collectie
        }
        // ...
    }

    private class MijnCollectieElement implements Element {
        private E element;

        public MijnCollectieElement(E element) {
            this.element = element;
        }

        public E getElement() {
            return element;
        }

        public MijnCollectie getCollectie() {
            return MijnCollectie.this;
        }
    }
}

De gebruiker voegt dus een willekeurig object toe aan de collectie, en krijgt een Element-object terug, hetgeen zijn gegeven object bevat. Vanaf dan moet de gebruiker verder werken met het Element-object. Op die manier kan ik efficient verwijderen ondersteunen.

Hoewel dit allemaal perfect werkt, heeft deze implementatie één groot nadeel: MijnCollectieElement is niet static. Dit betekent dat een element (MijnCollectieElement) impliciet een referentie heeft naar zijn collectie (MijnCollectie). Wanneer de gebruiker zijn referentie naar de collectie op null zet, maar nog ergens (minstens) 1 referentie naar een element heeft, wordt de collectie nooit opgeruimd door de garbage collectie: het element bevat nog steeds een bereikare referentie naar de collectie. Dit toon ik even in volgend fragment:

Java:

MijnCollectie<EenGrootObject> c = new MijnCollectie<EenGrootObject>(10000);
for (int i = 0; i < 10000 - 1; i++) {
        c.add(new EenGrootObject());
}
Element<EenGrootObject> e = c.add(new EenGrootObject());
c = null;
/* de collectie wordt niet opgeruimd door de garbage collectie, omdat er nog een
referentie naar de collectie bestaat via e */

Waarom is MijnCollectieElement niet static? Ik moet kunnen controleren of een gegeven Element wel degelijk door de collectie in kwestie is aangemaakt. Het is natuurlijk niet de bedoeling dat de gebruiker een element aangemaakt door collectie A als parameter aan een functie van een collectie B kan gegeven. Zie remove() in MijnCollectie.

Ik heb hiervoor een oplossing gevonden: WeakReference. Ik maak MijnCollectieElement static, en hou een referentie naar de collectie bij aan de hand van een WeakReference. Wanneer de gebruiker zijn referentie naar de collectie verliest, wordt de collectie nu wel opgeruimd door de garbage collector. Hier zijn de aanpassingen:

Java:

class MijnCollectie <E> {
    private MijnCollectieElement[] elements;
    private int size = 0;

    public MijnCollectie(int size) {
        elements = new MijnCollectieElement[size];
    }

    public Element<E> add(E element) {
        MijnCollectieElement<E> e = new MijnCollectieElement<E>(element, this);
        elements[size++] = e;
        return e;
    }

    public void remove(Element<E> element) {
        /* controleer of element aangemaakt is door deze collectie */
        if (!(element instanceof MijnCollectieElement)) {
            throw new RuntimeException(); // niet aangemaakt door deze collectie
        }
        MijnCollectieElement e = (MijnCollectieElement) element;
        if (e.getCollectie() != this) {
            throw new RuntimeException(); // niet aangemaakt door deze collectie
        }
        // ...
    }

    private static /* ADDED */ class MijnCollectieElement<E>
            extends WeakReference<MijnCollectie> /* ADDED */ implements Element<E> {
        private E element;

        public MijnCollectieElement(E element, MijnCollectie c) {
            super(c);
            this.element = element;
        }

        public E getElement() {
            return element;
        }

        public MijnCollectie getCollectie() {
            return get();
        }
    }
}

Wat is het probleem nu? In principe is er helemaal geen probleem: het werkt perfect! In het voorbeeld hierboven wordt de collectie nu wel opgeruimd. Maar ik ben niet helemaal zeker of dit een goede en mooie oplossing is. Ik vind het 'verdacht' dat ik MijnCollectieElement static heb moeten maken, en expliciet een referentie naar zijn collectie moet bijhouden. Daarom had ik graag van de java experts op dit forum geweten wat zij van deze oplossing vinden

Ik ben dus op zoek naar een oplossing waarmee:

- we kunnen weten of een element aangemaakt is door de collectie waaraan het element gegeven wordt; en
- de collectie door de garbage collectie kan opgeruimd worden, zonder dat eerst alle elementen zelf opgeruimd moeten worden.

Opmerking: Ik heb er ook aan gedacht om in MijnCollectie een HashSet<MijnCollectieElement> bij te houden, die de geldige/actieve elementen bijhoudt. Op die manier kan ik ook snel controleren of een gegeven Element geldig is. Ik ben tegen deze oplossing, omdat:

- een HashSet aardig wat geheugen gebruikt, en de bedoeling van mijn eigen implementatie is om het geheugengebruik zo laag mogelijk te houden; en
- het in principe onwaarschijnlijk is dat de gebruiker elementen aan een andere collectie gaat geven dan diegene die het element gemaakt heeft.

hopelijk was ik duidelijk genoeg bedankt voor de hulp

[Glimi]

Ik kan het even niet testen hier, maar werkt het niet gewoon als je ipv WeakReference te extenden gewoon een member maakt van het type WeakReference<MijnCollectie<E>> ?

Trouwens welke datastructuur gebruik je hier eigenlijk? Een binary heap?

[Verwijderd]

Glimi schreef op maandag 23 mei 2005 @ 15:09:
Ik kan het even niet testen hier, maar werkt het niet gewoon als je ipv WeakReference te extenden gewoon een member maakt van het type WeakReference<MijnCollectie<E>> ?

Dat werkt ook, maar alleen als MijnCollectieElement static blijft. Vanaf het moment ik MijnCollectieElement non-static maak, bevat deze impliciet een referentie naar de collectie, en zit ik dus met het probleem dat de collectie niet gewist kan worden vooraleer alle elementen gewist zijn.

Trouwens welke datastructuur gebruik je hier eigenlijk? Een binary heap?

Een binaire heap ja. MijnCollectieElement bevat de index in de array (de heap), en op die manier kan ik snel verwijderen/keys verhogen en verlagen.

[RSchellhorn]

Volgens mij zit er in de standaard api al een priorityqueue. Ook deze heeft op de nette queue operaties add(E element), remove() etc ook O(log(n)) volgens de specs. Zelf maken is natuurlijk leuk, maar als het niet hoeft....

Bovendien zou ik altijd AbstractQueue extenden of in ieder geval de Queue interface implementeren, zodat je dit kan schrijven:

Java:

Queue<?> theQueue = new MijnCollectie<?>(100);

[Verwijderd]

Slayer08 schreef op maandag 23 mei 2005 @ 17:00:
Volgens mij zit er in de standaard api al een priorityqueue. Ook deze heeft op de nette queue operaties add(E element), remove() etc ook O(log(n)) volgens de specs. Zelf maken is natuurlijk leuk, maar als het niet hoeft....

Inderdaad, die is er, maar die voldoet niet. Het wissen is O(n + log(n)) = O(n), en het laat niet efficiënt toe om de priority/key van een element te verlagen. Voor dit laatste kan je alleen het element wissen en opnieuw toevoegen: O(2n + log(n)) = O(n).

In feite kan je beide operaties (wissen + verlagen) nooit ondersteunen als je de positie van je elementen in de queue niet bijhoudt. Daarom dat ik in mijn implementatie dat wel doe. De Element-objecten (MijnCollectieElement) bevat intern de positie van het element in de array.

Bovendien zou ik altijd AbstractQueue extenden of in ieder geval de Queue interface implementeren, zodat je dit kan schrijven:

Java:

Queue<?> theQueue = new MijnCollectie<?>(100);

Dit is niet mogelijk, omdat bijvoorbeeld add() een boolean returnt, en ik moet hem een Element-object laten returnen. Ik kan dit natuurlijk via omwegen nog altijd bekomen, maar dan krijg je een implementatie die echt op niets meer trekt. De Queue-interface er niet bij betrekken vind ik helemaal niet erg.

Dit is ook de reden waarom ik in mijn voorbeelden over 'MijnCollectie' spreek, en niet over een implementatie van een priority queue ('PriorityQueue' of iets dergelijks). Ik bedoel het probleem heel algemeen. Ik kom het probleem nu tegen bij het implementeren van een priority queue, maar de datastructuur heeft niets met het probleem zelf te maken.

Ik wil gewoon op een goede en efficiënte manier bijhouden door welke collectie een element aangemaakt is (inderdaad, ik maak hier Element-objecten aan, ipv. ze te krijgen van de gebruiker: anders kan ik nooit de index van een element in de array (of wat dan ook, nu is het toevallig een array die de heap voorstelt) bijhouden). Verder wil ik niet dat het bestaan van een Element-object de garbage collector belemmert om de collectie zelf op te ruimen.

[ Voor 3% gewijzigd door Verwijderd op 23-05-2005 18:09 ]

[Verwijderd]

Ik denk dat ik een betere oplossing gevonden heb. In plaats van een referentie naar MijnCollectie bij te houden, houden MijnCollectie en MijnCollectieElement een referentie naar 1 of ander dummy-object bij. Op die manier vermijd ik de (eventuele) overhead van een WeakReference, en belemmer ik de garbage collector niet tot het verwijderen van de collectie.

Java:

class MijnCollectie <E> {
    private MijnCollectieElement[] elements;
    private int size = 0;
    private Object dummy = new Object();

    public MijnCollectie(int size) {
        elements = new MijnCollectieElement[size];
    }

    public Element<E> add(E element) {
        MijnCollectieElement<E> e = new MijnCollectieElement<E>(element, dummy);
        elements[size++] = e;
        return e;
    }

    public void remove(Element<E> element) {
        /* controleer of element aangemaakt is door deze collectie */
        if (!(element instanceof MijnCollectieElement)) {
            throw new RuntimeException(); // niet aangemaakt door deze collectie
        }
        MijnCollectieElement e = (MijnCollectieElement) element;
        if (e.getParent() != dummy) {
            throw new RuntimeException(); // niet aangemaakt door deze collectie
        }
        // ...
    }

    private static class MijnCollectieElement <E> implements Element<E> {
        private E element;
        private Object parent;

        public MijnCollectieElement(E element, Object parent) {
            this.parent = parent;
            this.element = element;
        }

        public E getElement() {
            return element;
        }

        public Object getParent() {
            return parent;
        }
    }
}

Ik heb het ook getest, en het werkt: de collectie wordt gewist vanaf het moment de referentie naar de collectie verdwenen is.

Wat vinden jullie hiervan? Het nadeel is natuurlijk wel dat ik voor elk element een extra referentie moet bijhouden (naar de parent), maar dat moest ik natuurlijk vroeger ook.

[RSchellhorn]

Verwijderd schreef op maandag 23 mei 2005 @ 18:08:
[...]
Het wissen is O(n + log(n)) = O(n)

Dat is alleen waar voor een willekeurig object, queues gebruik je "van buiten" alleen om het voorste element te verwijderen, en dat gaat gewoon in O(log(n)) staat in de API.

Hoe haal ik eigenlijk in je collectie het voorste element op, zonder er al een verwijzing naar te hebben ?

[ Voor 17% gewijzigd door RSchellhorn op 23-05-2005 19:48 ]

[Verwijderd]

Slayer08 schreef op maandag 23 mei 2005 @ 19:45:
[...]


Dat is alleen waar voor een willekeurig object, queues gebruik je "van buiten" alleen om het voorste element te verwijderen, en dat gaat gewoon in O(log(n)) staat in de API.

Dan bedoel jij iets anders dan mij. Ik bedoelde dus het verwijderen van een willekeurig object, en dus niet zozeer het object met de laagste priority. Ja ik heb dit nodig voor mijn applicatie

De priority queue van java ondersteunt dit niet efficiënt: hij itereert over de hele collectie O(n) tot het element gevonden is, verwijdert het element uit de array O(1), plaatst een element met hoogste prioriteit ('het laatste' element in de array) in de plaats O(1), en werkt dit element vervolgens terug naar beneden in de heap O(log(n)) = O(n + log(n)). Als je op voorhand die positie al weet (en dat weet ik dus, dankzij het Element-object), dan vermijd je de O(n) kost.

Maar opnieuw: priority queue is louter per voorbeeld.

Slayer08 schreef op maandag 23 mei 2005 @ 19:45:Hoe haal ik eigenlijk in je collectie het voorste element op, zonder er al een verwijzing naar te hebben ?

Gewoon zo:

Java:

class MijnCollectie <E> {
    public Element<E> extractMinimum() {
        Element<E> min =  elements[0];
        /* vervang elements[0] door elements[size - 1] en werk dit
           element omlaag in de heap */
        return min;
    }
}

edit: nu snap ik je opmerking. De remove()-methode hierboven is dus voor het verwijderen van een willekeurig element, niet voor het opvragen en verwijderen van het element met laagste prioriteit.

[ Voor 40% gewijzigd door Verwijderd op 23-05-2005 20:10 ]

[Glimi]

Verwijderd schreef op maandag 23 mei 2005 @ 19:25:
Ik heb het ook getest, en het werkt: de collectie wordt gewist vanaf het moment de referentie naar de collectie verdwenen is.

Wat vinden jullie hiervan? Het nadeel is natuurlijk wel dat ik voor elk element een extra referentie moet bijhouden (naar de parent), maar dat moest ik natuurlijk vroeger ook.

Ik kan even niets testen hier (Local Search loopt hier te stampen) dus als ik niet kloppende dingen zeg, dan moet je het me maar even vergeven ok?

1) Het punt waarom je MijnCollectieElement<E> niet static kan zijn in je orginele oplossing komt doordat het een inner class is van je MijnCollectie<E>. Het makkelijkste is dan natuurlijk om ervoor te zorgen dat het geen inner class meer is maar bijv een package local Class. Door vervolgens in het MijnCollectieElement<E> een WeakReference<MijnCollectie<E>> op te nemen naar Je MijnCollectie<E>, lijkt het me dat het zou moeten werken.
Eigenlijk vind ik dit mooier dan een inner class, omdat je de class ook naar buiten de class lekt.

2) Waarom een verwijzing naar het dummy-object? Als je wilt testen of het MijnCollectieElement<E> hoort bij je MijnCollectie<E> is een kwestie van de positie opzoeken in de MijnCollectie<E> (wat je toch nodig zult hebben in de remove) en om daarna een equality-test te doen op de twee elementen. Dan heb je heel die getCollection() niet nodig (aangezien je daar toch niet op mag vertrouwen, buiten de class)

[Verwijderd]

Glimi schreef op maandag 23 mei 2005 @ 21:03:
[...]

Ik kan even niets testen hier (Local Search loopt hier te stampen) dus als ik niet kloppende dingen zeg, dan moet je het me maar even vergeven ok?

1) Het punt waarom je MijnCollectieElement<E> niet static kan zijn in je orginele oplossing komt doordat het een inner class is van je MijnCollectie<E>.

Waarom zouden inner classes niet static kunnen zijn?

Het makkelijkste is dan natuurlijk om ervoor te zorgen dat het geen inner class meer is maar bijv een package local Class. Door vervolgens in het MijnCollectieElement<E> een WeakReference<MijnCollectie<E>> op te nemen naar Je MijnCollectie<E>, lijkt het me dat het zou moeten werken.
Eigenlijk vind ik dit mooier dan een inner class, omdat je de class ook naar buiten de class lekt.

Dit lijkt mij puur een kwestie van voorkeur. Persoonlijk vind ik dat classes die toch maar door één enkele andere class gebruikt worden, beter een private (static) inner class kunnen zijn, dan een local package class. Een ander voordeel van een (static) inner class is dat je geen getters en setters moet implementeren, omdat je outer class rechtstreeks toegang heeft tot de (private/protected en public) member fields van een (static) inner class.

2) Waarom een verwijzing naar het dummy-object? Als je wilt testen of het MijnCollectieElement<E> hoort bij je MijnCollectie<E> is een kwestie van de positie opzoeken in de MijnCollectie<E> (wat je toch nodig zult hebben in de remove) en om daarna een equality-test te doen op de twee elementen. Dan heb je heel die getCollection() niet nodig (aangezien je daar toch niet op mag vertrouwen, buiten de class)

Ik had gehoopt dat niemand op dit idee zou komen, want inderdaad, je hebt gelijk Dit is mijn probleem, ik had helemaal niet het voorbeeld van de priority queue mogen aangeven. Mijn implementatie is een beetje anders zoals ik ze hier verteld heb, maar ik kan niet aan de hand van de member fields van MijnCollectieElement weten tot welke MijnCollectie hij behoort (hetgeen jij terecht opmerkt). Mijn vraag is een beetje slecht overgekomen omv. het concrete voorbeeld.

---

Voor de volledigheid zal ik mijn vraag dan to-the-point stellen: ik zoek een goede en efficiënte methode om bij te houden door welk object een object is aangemaakt.

Ik ben begonnen met een eerste oplossing:

Java:

class Collectie {
    public Element createElement(Object o) {
        return new CollectieElement(o);
    }

    public boolean isMember(Element element) {
        if (!(element instanceof CollectieElement)) {
            return false;
        }
        return ((CollectieElement) element).getCollectie() == this;
    }

    public class CollectieElement implements Element {
        private Object element;

        public CollectieElement(Object element) {
            this.element = element;
        }

        public Object getElement() {
            return element;
        }

        public Collectie getCollectie() {
            return Collectie.this;
        }
    }
}

Het nadeel van deze oplossing is dat de inner class CollectieElement impliciet een referentie houdt naar Collectie, en een Collectie-object nooit opgeruimd zal kunnen worden zolang de gebruiker nog een referentie vasthoudt naar een Element-object aangemaakt door de collectie in kwestie.

Ik heb hiervoor 2 oplossingen gegeven: CollectieElement static maken èn ofwel gebruik maken van WeakReference ofwel gebruik maken van een dummy object (ik heb even generics terzijde gelaten, dat was ook niet echt relevant):

Java:

class Collectie {
    public Element createElement(Object o) {
        return new CollectieElement(this, o);
    }

    public boolean isMember(Element element) {
        if (!(element instanceof CollectieElement)) {
            return false;
        }
        return ((CollectieElement) element).getCollectie() == this;
    }

    public static class CollectieElement extends WeakReference implements Element {
        private Object element;

        public CollectieElement(Collectie c, Object element) {
            super(c);
            this.element = element;
        }

        public Object getElement() {
            return element;
        }

        public Collectie getCollectie() {
            return (Collectie) get();
        }
    }
}

Java:

class Collectie {
    private Object dummy = new Object();

    public Element createElement(Object o) {
        return new CollectieElement(dummy, o);
    }

    public boolean isMember(Element element) {
        if (!(element instanceof CollectieElement)) {
            return false;
        }
        return ((CollectieElement) element).getParent() == dummy;
    }

    public static class CollectieElement implements Element {
        private Object element;
        private Object parent;

        public CollectieElement(Object parent, Object element) {
            this.element = element;
            this.parent = parent;
        }

        public Object getElement() {
            return element;
        }

        public Object getParent() {
            return parent;
        }
    }
}

Mijn vraag is nu: wat vinden jullie de beste oplossing? zijn er betere oplossingen? een goede oplossing moet aan deze voorwaarde voldoen: de garbage collector niet in de weg staan.

sorry voor de onduidelijkheid, het concrete voorbeeld maakte mijn vraag te onduidelijk

MOD: misschien is het een goed idee om het topic onder de streep hierboven af te splitsen, de vorige posts zijn eigenlijk niet meer zo relevant.

[Glimi]

Ik zou voor optie twee gaan, maar dan niet via overerving maar met een WeakReference member
1) Je hebt geen 'vage' constructies met een dummy object welke gedocumenteerd moeten worden
2) Je zit de gc niet voor de gek te houden, maar maakt gebruik van de methodes die er voor zijn

De versie zou dan worden:

Java:

import java.lang.ref.WeakReference;

class Collectie <E> {

    public Element<E> createElement(E element) {
        return new CollectieElement<E>(element, this);
    }

    public boolean isMember(Element<E> element) {
        if (!(element instanceof CollectieElement)) {
            return false;
        }
        return ((CollectieElement<E>)element).getCollectie() == this;
    }

    /**
     * Check if it is marked for deletion
     */
    public void finalize( ) {

        System.out.println( "Destroying the collection" );
    }

    private static class CollectieElement<E> implements Element<E> {

        WeakReference<Collectie<E>> _col;
        private E element;

        public CollectieElement(E element, Collectie<E> p_col) {
            this.element = element;
            _col = new WeakReference<Collectie<E>>( p_col );
        }

        public E getElement() {
            return element;
        }

        public Collectie<E> getCollectie() {

            return _col.get();
        }
    }
}

Testcode (ok, een vrij groot woord)

Java:

public class Main {

    public static void main( String[] args ) {

        Collectie<String> l_collection = new Collectie<String>( );

        Element<String> l_element = l_collection.createElement( "Whattup, whattup?");

        System.out.println( "Is member? " + l_collection.isMember( l_element ) );
        l_collection = null;

        System.gc();

        try {

            Thread.sleep( 5000 );
        } catch( InterruptedException l_irEx ) {

            l_irEx.printStackTrace();
        }

        System.out.println( l_element.getElement() );
    }
}

Output

code:

Is member? true
Destroying the collection
Whattup, whattup?

Echter ik blijf het een 'kunstgreep' vinden om de boel maar static te declareren als een inner class omdat je die impliciete reference naar het parent object niet wilt hebben(dat bedoelde ik bij je eerste quote). Een normale class zou er ook volstaan en dan is deze vervolgens ook nog over te erven door iemand anders, of jezelf later. Maarja dit is toch een beetje eigen smaak, maar ik blijf erbij dat een class die je naar buiten lekt liever geen inner class moet zijn.

[Verwijderd]

Sorry voor het late reply, had het gisteren wat te druk

Glimi schreef op dinsdag 24 mei 2005 @ 09:40:
Ik zou voor optie twee gaan, maar dan niet via overerving maar met een WeakReference member
1) Je hebt geen 'vage' constructies met een dummy object welke gedocumenteerd moeten worden

akkoord

2) Je zit de gc niet voor de gek te houden, maar maakt gebruik van de methodes die er voor zijn

Ik zie niet heel goed in hoe ik hier de GC voor de gek houd. Het is toch gewoon een referentie naar 1 of ander object, maar hier nu toevallig zonder een echte betekenis.

...

Misschien is een aparte 'weak'-member, ipv. het overerven van de WeakReference-klasse wel beter ja. Dat het ook inderdaad werkt, had ik reeds aangegeven . Maar het is zeker positief dat we tot dezelfde oplossing komen.

Echter ik blijf het een 'kunstgreep' vinden om de boel maar static te declareren als een inner class omdat je die impliciete reference naar het parent object niet wilt hebben(dat bedoelde ik bij je eerste quote). Een normale class zou er ook volstaan en dan is deze vervolgens ook nog over te erven door iemand anders, of jezelf later.

Het lijkt een kunstgreep, maar het is zo dat MijnCollectie voortdurend datastructuren van MijnCollectieElement aanspreekt en wijzigt. Omdat deze laatste inner is, kan MijnCollectie daar rechtstreeks aan. Als MijnCollectie echter 'package-private' is, dan moet ik de nodige getters (en eventueel setters) maken, met de nodige commentaren en ad-hoc oplossingen. MijnCollectieElement is dus niet zomaar een algemene implementatie voor een element, maar bevat specifieke datastructuren voor die implementatie (priority queue in dit geval).

Bedankt voor je hulp. Ik ga het op de hierboven gegeven manier (WeakRef. als private member) doen.