Meditaties over Algoritmiek

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.

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 < 0) {

    /* element is greater then this nodes representative */
    if (this.getRightBranch() == null) {
        
        this.setRightBranch(new BinaryTree<E>());
    }
    this.getRightBranch().add(element);
} else if (comparison == 0) {
    
    /* element equals this nodes representative */
    this.takeElement(element);
} else {/* comparison > 0 */
    
    /* element is less then this nodes representative */
    if (this.getLeftBranch() == null) {
        
        this.setLeftBranch(new BinaryTree<E>());
    }
    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.