Meditaties over Algoritmiek

 
23 februari 2009

In deze post reageer ik op de Algoritmiek post van André Boonzaaijer. Ik laat zien dat efficiente algoritmen en object orientatie samen gaan.

André Boonzaaijer toont zich een ware meester van Sogyodo, de weg van innovatie. In zijn post Algoritmiek spreekt André over efficiënte algoritmen. Hij is van mening dat een bekend probleem een bekende oplossing verdient. Wanneer een probleem minder bekend is loont het de moeite een object georiënteerde oplossing te zoeken.

André geeft een bijzonder voorbeeld. Hij bespreekt het probleem van sorteren. Dit probleem is bekend en heeft veel verschillende oplossingen. Daarnaast schetst André een object georiënteerde oplossing. Objecten die zichzelf weten te ordenen, als je ze dat vraagt. Was het niet zo dat voor bekende problemen, bekende oplossingen gekozen moesten worden? En was het niet de bedoeling efficiënte algoritmen te verzinnen?

De post van André heeft mij aan het denken gezet. Mijn naïeve gedachten zagen niet in hoe sorteren aan objecten zelf overlaten een efficiënte oplossing bood. Lang dacht ik dat het tot Bubble Sort zou leiden en dit is niet het meest efficiënt. Na meditatie heb ik het licht gezien. Hieronder staan mijn gedachten. Ik ben benieuwd wat André er van vindt.

Uiteenzetting
De situatie is als volgt. Er is een collectie van objecten die je gesorteerd wil hebben. Ik ga niet de collectie pas sorteren wanneer dat nodig is. Ik kies ervoor de collectie gesorteerd te houden. Dit kan met een binaire boom.

Een binaire boom is een data structuur. Er zijn nodes die met elkaar verbonden zijn. Een node heeft hoogstens één ouder en hoogstens twee kinderen. Iedere boom heeft een wortel-node. Bij iedere node begint een boom. Deze bomen worden sub-bomen genoemt. De sub-bomen die geworteld zijn bij de kinderen van een node heten de linker sub-boom en rechter sub-boom. Hieronder staat een voorbeeld. Hierin is de wortel groen omrand en de rechter sub-boom met rood aangegeven.

Een binaire boom

Voorbeeld van een binaire boom

Deze datastructuur kan gebruikt worden om een collectie van objecten gesorteerd te houden. Iedere node stelt een groep dezelfde objecten voor. Alle objecten die kleiner zijn dan deze groep vormen op dezelfde manier de linker sub-boom. Alle objecten die groter dan die groep zijn vormen zo weer de rechter sub-boom. Zelfs wanneer een object wordt toegevoegd aan de boom kan deze gesorteerd blijven. Dat gaat als volgt:

Het object vergelijkt zichzelf met de wortel. Afhankelijk daarvan onderneemt het object één van de volgende acties:

  • Als het object kleiner is dan de wortel: laat het object zich vergelijken met de wortel van de linker sub-boom.
  • Als het object groter is dan de wortel: laat het object zich vergelijken met de wortel van de rechter sub-boom.
  • Als het object even groot is als de wortel: voeg het object toe aan deze node.

Het object zich laten vergelijken met een sub-boom gaat op dezelfde manier. Het is een recursieve oplossing. Het kan gebeuren dat een node geen linker of rechter sub-boom heeft. In dat geval wordt het object de nieuwe linker, dan wel rechter sub-boom van die node.

Enige meditatie levert het inzicht dat de boom na het toevoegen van een object nog steeds gesorteerd is. Donald Knuth schrijft in The Art of Computer Programming uitgebreid over binaire bomen. Knuth laat daar ook zien dat het gebruik van binaire bomen voor het sorteren erg efficiënt is.

Illustratie
Ter illustratie heb ik dit geïmplementeerd in Java. Ik wil rechthoeken sorteren. Ik heb dus een Rectangle klasse gemaakt. Deze klasse implementeert de interface Comparable<Rectangle> Een rechthoek is groter dan een andere rechthoek wanneer deze ook een grotere oppervlakte heeft. Ik override hiertoe compareTo(Rectangle) op de volgende manier:

@Override
public int compareTo(Rectangle rectangle) {
 
	return this.getArea().compareTo(rectangle.getArea());
}

Interessanter is de klasse BinaryTree<E extends Comparable<E>>. Dit is een generieke klasse. Het kan dus meer dan alleen rechthoeken sorteren. Het hart van deze klasse is de add(E) methode. Dit voert alle stappen uit die hierboven zijn besproken. Hieronder vind je het recursieve geval:

...
/* Compare with a represantative */
int comparison = this.getRepresentative().compareTo(element) ;
if (comparison &lt; 0) {
 
    /* element is greater then this nodes representative */
    if (this.getRightBranch() == null) {
 
        this.setRightBranch(new BinaryTree&lt;E&gt;());
    }
    this.getRightBranch().add(element);
} else if (comparison == 0) {
 
    /* element equals this nodes representative */
    this.takeElement(element);
} else {/* comparison &gt; 0 */
 
    /* element is less then this nodes representative */
    if (this.getLeftBranch() == null) {
 
        this.setLeftBranch(new BinaryTree&lt;E&gt;());
    }
    this.getLeftBranch().add(element);
}
...

Merk het gebruik van getRepresentative() op. Het komt voor dat verschillende objecten even groot zijn. Een voorbeeld is het vergelijken van een rechthoek van 4 bij 9 en een rechthoek van 6 bij 6. Beide rechthoeken hebben een oppervlakte van 36. Een node heeft daarom een lijst met elementen die even groot zijn. Een representant is een van de elementen uit deze lijst. De methode takeElement(E) voegt een element aan deze lijst toe.

Er is ook een methode asList() die een lijst van gesorteerde elementen terug geeft. Dit gebeurt ook weer met recursie. In het voorbeeld wat ik heb meegeleverd wordt deze methode gebruikt om over de rechthoeken te itereren.

Conclusie
Ik heb laten zien dat een bekende efficiënte oplossing van een probleem en object oriëntatie elkaar niet in de weg hoeven te staan. De scheiding die André aanbrengt om tot een algoritme te komen is dus niet hard. Ik wil dan ook aanraden om altijd na te gaan of een object georiënteerde oplossing mogelijk is.


Werken met ?
Kijk dan bij onze mogelijkheden voor starters en/of ervaren IT'ers.


Categorieën: Development

Tags: , ,


Reacties (7)

  • @Daan

    Ik had de keuze om op elk van jouw punten te reageren of zelf weer een soort samenvatting te maken, waarin ik jouw punten ook terug laat komen. De eerste optie leek me onoverzichtelijk worden, dus ik zal dan ook proberen kort en bondig samen te vatten wat ik bedoel:
    – Als het het domeinmodel verandert, dan lijkt het me een command. Ik denk hierbij aan de situatie dat je method aanroept als volgt: MyCollection.Sort();
    – Als het een eigenschap is van een collection, dan zou ik verwachten dat de collection altijd gesorteerd is (bij opvragen). Of dit dan bij opvragen, toevoegen of enig ander moment gebeurt, lijkt me dan een implementatiedetail.
    – Als het puur een query is, dan zou ik verwachten dat het niets aan de originele collection aanpast. De objecten in de originele collection in een Binairy tree plaatsen valt volgens mij wel onder zo’n aanpassing.

    Geplaatst op 23 maart 2009 om 17:13 Permalink

  • Daan Wanrooy schreef:

    @Rick

    Interessant dat jij sorteren een command vind. Het feit dat sorteren een werkwoord is doet zoiets vermoeden. Hieronder ga ik dieper op mijn motivaties in om sorteren een query te noemen. Later kom ik graag terug op jou tegenwerpingen.

    In het artikel van Andre wordt Command-Query Separation als volgt uitgelegd. Een command veranderd de toestand van het systeem. Een query vraagt naar informatie over het systeem.

    Toen ik mijn antwoord gaf op de vraag van Andre had ik de volgende situatie in gedachten. Er zijn sorteerbare objecten. Dat wil zeggen dat de klasse waar deze objecten instanties van zijn zoiets als Comparable implementeren. (Of liever dat er een/meerdere Comparator(s) geimplementeert is/zijn.)
    Verder is er een collectie van deze objecten. De collectie hoeft niet gesorteerd te zijn. Deze collectie heeft een methode die een gesorteerde lijst van zijn objecten terug geeft.
    De vraag is nu of deze methode een command of een query is.

    De reden dat ik vind dat de methode een query is, is deze. De toestand van het systeem hoeft in principe niet te veranderen. De juiste volgorde van de objecten kan achterhaald worden door over de objecten te itereren, en ze met elkaar te vergelijken.

    Jouw tegenwerping dat het raar is om een TreeList te gebruiken als sorteermethode een query is, is in mijn ogen niet terecht. Ten eerste veranderd het systeem niet wanneer je de methode aanroept. Het systeem veranderd alleen bij het toevoegen van een object.
    Daarnaast is TreeList een implementatie detail. Bepaling of een methode een command of query is speelt zich af op een hoger niveau.

    Verder ben ik het met je eens met wat je zegt over de doorvoering van de Command-Query Seperation. Voor iedere sortering zou dan een kopie of index moeten bestaan.

    Geplaatst op 23 maart 2009 om 10:27 Permalink

  • Rick schreef:

    @ Daan

    Als sorteren alleen een query is, dan is het bijhouden van een TreeList wel een beetje raar, toch? Want dan heeft die sortering invloed op je manier van opslaan van de objecten. En veranderingen in je domeinmodel zouden alleen moeten kunnen als gevolg van een command.

    Ik denk dat sorteren een command zou zijn (het is een commando, nota bene). En dat een sortering een eigenschap van een collection kan zijn (geen query / geen command). Een collection in je domeinmodel kan een sortering hebben, maar dan zou er geen command ‘sorteren’ zijn, elke toevoeging gebeurt op volgorde. Het kan ook een eigenschap zijn van de collection die je opvraagt (in een query).

    Als je dan command-query separation volledig doorvoert, dan zou je van alle sorteringen van een collectie die je op zou willen vragen, een kopie of index bij moeten houden. Je kunt je afvragen waarom je verschillende sorteringen van dezelfde collection wilt hebben. Waarschijnlijk voor verschillende doelen. Maar goed, dat zal ik hier verder buiten laten.

    Geplaatst op 27 februari 2009 om 15:05 Permalink

  • Daan Wanrooy schreef:

    @Andre

    Na het lezen van jouw artikel en het bestuderen van enkele blogs over Command-Query Separation, ben ik gaan mediteren op jouw vraag. Ik ben tot het volgende inzicht gekomen.

    Het toevoegen van een object is een command. Het veranderd immers de toestand.
    Het opvragen van een gesorteerde lijst van objecten is een query. Er is (in principe) geen toestandsverandering nodig om deze informatie op te leveren.

    Geplaatst op 24 februari 2009 om 10:31 Permalink

  • Daan,

    Beter had ik het niet kunnen uitleggen :). Bijzonder mooi voorbeeld.

    Stomtoevallig ben ik dit weekend nog bezig geweest met een artikeltje dat hieraan raakt dat ik opgestuurd heb naar SDN Magazine voor publicatie.
    http://whiletrue.nl/blog/wp-content/andre-boonzaaijer-schaalbare-modellen.pdf

    Het betreft een tweetal vormen van modelleren en toevallig lijkt jouw benadering van een gesorteerd blijvende collectie van objecten veel op de tweede benadering die ik beschrijf. Ik denk dat dat een heel goed uitgangspunt is, gestoeld op het principe van Command-Query Separation van de maker van Eiffel, Bertrand Meyer.

    Wellicht een mooie om over te mediteren: is sorteren een command of een query?

    Geplaatst op 23 februari 2009 om 21:04 Permalink

  • Daan Wanrooy schreef:

    @Ivo

    Jij hebt gelijk dat de TreeMap gebruik maakt van binaire bomen voor het opslaan van de sleutels. Er is echter een verschil. TreeMap is een Map, terwijl het voorbeeld (meer) een List is.

    Je zou dan ook zoiets als een TreeList verwachten in Java SE. Waarom Sun in deze implementatie niet voorziet begrijp ik niet.
    Het apache commons project biedt wel een TreeList.

    Geplaatst op 23 februari 2009 om 13:26 Permalink

  • Ivo Limmen schreef:

    Daan,

    Volgens mij werkt de TreeMap class, die standaard in de Java Standard Edition, zit hetzelfde als je BinaryTree. Voor de rest deel ik je mening: een hoop algoritmen kunnen prima met OO opgelost worden.

    Geplaatst op 23 februari 2009 om 12:49 Permalink