[ALG/Java/Patterns] specifieke algoritme gegevens - Softwareontwikkeling

zondag 6 februari 2005 20:06

Acties:

Verwijderd

Topicstarter

Hallo.

Ik ben wat aan het piekeren om op een mooie en handige manier (tijdelijke) informatie van algoritmes bij te houden, zonder dat je de gebruiker van het algoritme verplichtingen oplegt over de definitie van zijn classes. Laat ik het uitleggen ahv. een theoretisch voorbeeldje.

Stel je hebt volgende interface & implementatie:

Java:

interface SomeInterface
{
    public int getSomething();
}

class MyClass implements SomeInterface
{
    private int value;
    
    MyClass(int value) { this.value = value; }
    public int getSomething() { return value; }
}

Stel nu dat je een (maakt niet uit wat het doet) algoritme hebt dat werkt op een List<SomeInterface>, en stel dat het algoritme moet bijhouden welke elementen uit de lijst hij reeds behandeld heeft (en dus ook welke niet).

Nu kan je in principe elk element uit de lijst in een Map<SomeInterface, Boolean> steken. Deze map houdt dus per element bij welk element het algoritme reeds behaldend heeft (true) en welke niet (false). Deze aanpak heeft volgens mij minstens de volgende problemen:

- In een List kunnen dubbels (volgens .equals()) voorkomen, maar in een Map niet.
- Ook al heb je geen dubbels, de tijdcomplexiteit van het algoritme kan stijgen, aangezien een lookup in de Map niet noodzakelijk in O(1)-tijd hoeft te verlopen. (bijvoorbeeld als de gebruiker een slechte hashcode-functie geïmplementeerd heeft)
- SomeInterface is een interface, en List<SomeInterface> is dus een lijst van willekeurige implementaties van SomeInterface (in het voorbeeld hierboven heb ik er eentje gegeven: SomeClass). Het is (volgens mij) niet gebruikelijk dat verschillende implementaties van een interface vergeleken kunnen worden met elkaar. Hiermee bedoel ik: de meeste programmeurs implementeren de equals(Object o) van een class Foo implements EenInterface als volgt:

Java:

public boolean equals(Object o)
{
    if (!(o instanceof Foo))
    {
        return false;
    }
        
    MyClass foo = (Foo) o;
    ...
}

Een object van het type Foo kan je dus niet vergelijken met bijvoorbeeld een object van het type Foo2, met Foo2 gedefinieerd als class Foo2 implements EenInterface. Een lookup in de Map zou dus ook foutlopen.

Samengevat: een Map is no-go!

Toen kwam ik op het idee om het Decorator pattern te gebruiken, op de volgende manier: ik maak een speciale implementatie van SomeInterface (laat ik hem SomeInterfaceDecorated noemen), waarmee ik kan aangeven of een element (SomeInterface-element) al dan niet behandeld is. De functies uit SomeInterface stuur ik door naar het SomeInterface-element dat gedecoreerd wordt. Deze class declareer ik private in mijn algoritme klasse:

Java:

class Algorithm
{
    private class SomeInterfaceDecorated implements SomeInterface
    {
        private boolean done = false;
        private SomeInterface myClass;
        
        public SomeInterfaceDecorated(SomeInterface myClass) { this.myClass = myClass; }
        public boolean isDone() { return done; }
        public void setDone() { done = true; }
        public int getSomething() { return myClass.getSomething(); }
        public boolean equals(Object o) { return myClass.equals(o); }
        public int hashCode() { return myClass.hashCode(); }
        public String toString() { return myClass.toString(); }
    }
    
    public Algorithm(List<SomeInterface> input)
    {
        List<SomeInterfaceDecorated> inputDecorated = new ArrayList<SomeInterfaceDecorated>();
        
        for (SomeInterface someClass : input)
            inputDecorated.add(new SomeInterfaceDecorated(someClass));
        
        // run algoritme op inputDecorated, ipv. input
    }
}

In plaats van dat mijn algoritme runt op een List<SomeInterface>, laat ik hem runnen op een List<SomeInterfaceDecorated>.

In principe ben ik nu klaar: ik kan aangeven of elementen uit de lijst reeds behandeld zijn, zonder dat ik de gebruiker verplicht om zijn classes/interfaces aan te passen.

Mijn vraag is nu: is dit een goede manier? Kan het beter? Volgens mij is dit een mooie toepassing van het Decorater pattern, maar ik weet niet goed of het op zijn plaats is. Ik vind het o.a. 'jammer' dat ik elk element uit de input-lijst moet kopiëren in een nieuwe lijst (uiteraard kopieer ik de reference, maar dat telt ook), wat misschien problemen kan geven indien de input-lijst erg groot is. Sterker nog, omdat ik elk element moet kopiëren, verloopt het algoritme vanaf nu in minstens O(n) tijd, terwijl het theoretisch mogelijk kan zijn om het algoritme te runnen in O(log n) tijd (ik heb met opzet vermeld dat het een willekeurig algoritme is). Al bij al geen goede oplossing dus. Bestaan hier betere standaardoplossingen voor?

bedankt, en excuses voor de lange post, ik wou zo duidelijk mogelijk zijn

edit: Ik ben dus eigenlijk op zoek naar een oplossing waarmee ik de elementen NIET hoef te kopiëren, en daardoor de tijdcomplexiteit van het algoritme dus niet minstens O(n) bedraagt.

[ Voor 3% gewijzigd door Verwijderd op 06-02-2005 20:08 ]

zondag 6 februari 2005 20:19

Acties:

Soultaker

Als je per element wil kunnen aangeven of je een element al verwerkt hebt, dan zal het waarschijnlijk toch al minimaal een O(n) algoritme zijn, anders heb je maximaal log N) elementen op 'true' staan.

Zelf zou ik in dit geval gewoon een eigen array van booleans gebruiken (of een ArrayList, als je echt wil), waarbij elke waarde correspondeert met een waarde in de lijst. Jouw oplossing is wel mooi object-georienteerd, maar volgens mij is het ook nogal omslachtig en dat staat een efficiente implementatie van het algoritme in de weg. Bovendien is het niet nodig om OO-patterns te gebruiken voor data die heel erg beperkt zichtbaar is (alleen binnen de methode, in je voorbeeld). Daar voldoet een arraytje ook wel.

zondag 6 februari 2005 20:27

Acties:

Alarmnummer

-= Tja =-

Verwijderd schreef op zondag 06 februari 2005 @ 20:06:
Hallo.

Ik ben wat aan het piekeren om op een mooie en handige manier (tijdelijke) informatie van algoritmes bij te houden, zonder dat je de gebruiker van het algoritme verplichtingen oplegt over de definitie van zijn classes. Laat ik het uitleggen ahv. een theoretisch voorbeeldje.

Stel je hebt volgende interface & implementatie:
Java:
1
2
3
4
5
6
7
8
9
10
11
12
interface SomeInterface
{
    public int getSomething();
}

class MyClass implements SomeInterface
{
    private int value;
    
    MyClass(int value) { this.value = value; }
    public int getSomething() { return value; }
}

Dat ziet eruit als een strategy

Een stategy is een oplossing voor een gebrek aan java: functies kun je niet als parameter meegeven.

- In een List kunnen dubbels (volgens .equals()) voorkomen, maar in een Map niet.

yep. Maar je kunt ook werken met een identity hashmap.. Dan heb je geen equals op basis van de equals methode.. maar wordt gewerkt via een adres vergelijking.

- Ook al heb je geen dubbels, de tijdcomplexiteit van het algoritme kan stijgen, aangezien een lookup in de Map niet noodzakelijk in O(1)-tijd hoeft te verlopen. (bijvoorbeeld als de gebruiker een slechte hashcode-functie geïmplementeerd heeft)

Hmm tja... pas op met het : laat ik lief zijn. Jij maakt een contract en jouw contract zegt: maak een goeie hash anders krijg je een slechte performance. Ik zou me er dus niet druk om maken. Eventueel met koeieletters erbij zetten: let op een goeie hash.

- SomeInterface is een interface, en List<SomeInterface> is dus een lijst van willekeurige implementaties van SomeInterface (in het voorbeeld hierboven heb ik er eentje gegeven: SomeClass). Het is (volgens mij) niet gebruikelijk dat verschillende implementaties van een interface vergeleken kunnen worden met elkaar. Hiermee bedoel ik: de meeste programmeurs implementeren de equals(Object o) van een class Foo implements EenInterface als volgt:
Java:
1
2
3
4
5
6
7
8
9
10
public boolean equals(Object o)
{
    if (!(o instanceof Foo))
    {
        return false;
    }
        
    MyClass foo = (Foo) o;
    ...
}
Een object van het type Foo kan je dus niet vergelijken met bijvoorbeeld een object van het type Foo2, met Foo2 gedefinieerd als class Foo2 implements EenInterface. Een lookup in de Map zou dus ook foutlopen.

Ik snap niet wat er fout kan gaan.. Als je werkt met een equals dan hoef je niet bang te zijn dat het fout gaat bij verschillende classes.. het resultaat van de equals is dan false... precies wat je wilt.

Samengevat: een Map is no-go!

Map is geen probleem.. check verder de identityhashmap.

Mijn vraag is nu: is dit een goede manier? Kan het beter? Volgens mij is dit een mooie toepassing van het Decorater pattern, maar ik weet niet goed of het op zijn plaats is. Ik vind het o.a. 'jammer' dat ik elk element uit de input-lijst moet kopiëren in een nieuwe lijst (uiteraard kopieer ik de reference, maar dat telt ook), wat misschien problemen kan geven indien de input-lijst erg groot is.

Het idee van de decorator is leuk.. maar verpak neit het algoritme in die decorator.. maar wat dacht je van die lijst die je gaat bewerken.. Dan weet je zeker dat je niet langs jouw decorator kan gaan.. en als je het uit wilt zetten... dan gewoon niet wrappen/

Sterker nog, omdat ik elk element moet kopiëren, verloopt het algoritme vanaf nu in minstens O(n) tijd, terwijl het theoretisch mogelijk kan zijn om het algoritme te runnen in O(log n) tijd (ik heb met opzet vermeld dat het een willekeurig algoritme is). Al bij al geen goede oplossing dus. Bestaan hier betere standaardoplossingen voor?

Als je die list gaat wrappen in een decorated list (met dus counters ed) dan zie ik het probleem niet. De complexiteit van het algoritme blijft hetzelfde.

[edit]
In deze decorator kan je dan gebruik maken van die identityhashmap. Verder hoef je ook niet alle elementen in de lijst erin te copieeren, om te controleren of die al is aangeroepen. Als het is aangeroepen zet je het in die identityhashmap (met een of ander onzin object als value). Als het niet is aangeroepen zit het ook niet in die list. Complexiteit van het registreren is dus O(c)..

[ Voor 8% gewijzigd door Alarmnummer op 06-02-2005 20:42 ]

zondag 6 februari 2005 21:27

Acties:

Verwijderd

Topicstarter

Soultaker schreef op zondag 06 februari 2005 @ 20:19:
Als je per element wil kunnen aangeven of je een element al verwerkt hebt, dan zal het waarschijnlijk toch al minimaal een O(n) algoritme zijn, anders heb je maximaal log N) elementen op 'true' staan.

Hier heb je inderdaad gelijk in. Ik was mij aan het concentreren op een puur willekeurig algoritme, zodat ik hierover niet nagedacht had.

Zelf zou ik in dit geval gewoon een eigen array van booleans gebruiken (of een ArrayList, als je echt wil), waarbij elke waarde correspondeert met een waarde in de lijst.

Als ik het goed snap, bedoel je dat ik een boolean-array (laat ik hem booleanArray noemen) van lengte input.size() moet aanmaken, en dat een element op index i in input reeds behandeld is als geldt dat booleanArray[i] == true. Dit alles kan aan de hand van de Collection.toArray()-functie.

Dit is een goede oplossing! Het aanmaken van zo'n array gaat in constante tijd, dus dat zit goed. Maar hoe doe ik het dan als de input geen List is, maar een Set, en ik dus niet elementen op hun index kan opvragen? (een Set heeft geen sortering)

Alarmnummer schreef op zondag 06 februari 2005 @ 20:27:
yep. Maar je kunt ook werken met een identity hashmap.. Dan heb je geen equals op basis van de equals methode.. maar wordt gewerkt via een adres vergelijking.

Aan een IdentityHashMap had ik ook gedacht, maar hier had ik een probleem mee: wat als in de List 2x hetzelfde element (dus hetzelfde object, met dezelfde reference) zit? In de List zijn dit aparte elementen, terwijl in de IdentityHashMap dit aanzien wordt als één element.

Hmm tja... pas op met het : laat ik lief zijn. Jij maakt een contract en jouw contract zegt: maak een goeie hash anders krijg je een slechte performance. Ik zou me er dus niet druk om maken. Eventueel met koeieletters erbij zetten: let op een goeie hash.

Heb je inderdaad wel gelijk in.

Ik snap niet wat er fout kan gaan.. Als je werkt met een equals dan hoef je niet bang te zijn dat het fout gaat bij verschillende classes.. het resultaat van de equals is dan false... precies wat je wilt.

Inderdaad, ik maakte het weer te moeilijk

Het idee van de decorator is leuk.. maar verpak neit het algoritme in die decorator.. maar wat dacht je van die lijst die je gaat bewerken.. Dan weet je zeker dat je niet langs jouw decorator kan gaan.. en als je het uit wilt zetten... dan gewoon niet wrappen/

Als je die list gaat wrappen in een decorated list (met dus counters ed) dan zie ik het probleem niet. De complexiteit van het algoritme blijft hetzelfde.

Het decoreren van de input List is een goed idee (ik veronderstel dat je met counters functies als isDone() bedoelt?), maar ik zie niet goed in hoe daardoor het probleem (hoe houd ik bij of een element behandeld is) opgelost is. Met andere woorden: hoe is isDone() dan geïmplementeerd?

[edit]
In deze decorator kan je dan gebruik maken van die identityhashmap. Verder hoef je ook niet alle elementen in de lijst erin te copieeren, om te controleren of die al is aangeroepen. Als het is aangeroepen zet je het in die identityhashmap (met een of ander onzin object als value). Als het niet is aangeroepen zit het ook niet in die list. Complexiteit van het registreren is dus O(c)..

Als ik het goed snap, bedoel je een soort lazy decorated List? Lazy in de zin dat ik de elementen pas toevoeg als ik er voor de eerste keer naar vraag (en dus false return: element is nog niet beschouwd). Dit zou een mooie oplossing zijn, behalve dat ik dan nog altijd met het probleem zit dat hetzelfde object meerdere malen in de List kan zitten.

PS: volgens mij kan ik ook een TreeSet ipv. IdentityHashMap gebruiken, waarbij de Comparator de referenties vergelijkt.

Bedankt beide, ik ben er bijna!

zondag 6 februari 2005 21:35

Acties:

Alarmnummer

-= Tja =-

Aan een IdentityHashMap had ik ook gedacht, maar hier had ik een probleem mee: wat als in de List 2x hetzelfde element (dus hetzelfde object, met dezelfde reference) zit? In de List zijn dit aparte elementen, terwijl in de IdentityHashMap dit aanzien wordt als één element.

Dan kan je altijd nog kijken naar een multimap. (Gewoon een lijst op de value plaats zetten) en daar dan een index plaatsen van het behandelde element.

Het decoreren van de input List is een goed idee (ik veronderstel dat je met counters functies als isDone() bedoelt?), maar ik zie niet goed in hoe daardoor het probleem (hoe houd ik bij of een element behandeld is) opgelost is. Met andere woorden: hoe is isDone() dan geïmplementeerd?

Hmm tja.. ik weet niet precies wat je wilt bereiken..

domme opmerking:
je kunt altijd de size van de gemarkeerde list vergelijken met die van de invoer list.

slimmere opmerking:
is het niet zaak van het algoritme om aan te geven als die klaar is?

Als ik het goed snap, bedoel je een soort lazy decorated List? Lazy in de zin dat ik de elementen pas toevoeg als ik er voor de eerste keer naar vraag (en dus false return: element is nog niet beschouwd). Dit zou een mooie oplossing zijn, behalve dat ik dan nog altijd met het probleem zit dat hetzelfde object meerdere malen in de List kan zitten.

Zie mijn opmerking over die multimap. Commons Collections van jakarta project heeft wel zoiets liggen (maar het is ook kinderlijk eenvoudig om zelf even iets te maken).

PS: volgens mij kan ik ook een TreeSet ipv. IdentityHashMap gebruiken, waarbij de Comparator de referenties vergelijkt.

Het ligt eraan.. als jij een hashcode kan maken is een tree een slechte structuur. Jij kan met een hash een O(c) krijgen.. en dat is kleiner dan die van een tree... die is O(log(n)) als ik me niet vergis. En verder kan het erg lastig zijn om een groter/kleiner dan betekenis aan objecten te geven.

Ik denk dat je trouwens ook beter kunt denken aan hele specifieke oplossingen en slecht kunt redereren over hele algemene structuren. Je zult zien dat de informatie behoefte vaak uniek is... en je daarom ook heel slecht generiek erover kunt redeneren.

[ Voor 10% gewijzigd door Alarmnummer op 06-02-2005 21:39 ]