Algoritmiek

 
28 juli 2008

Algoritmiek is het ontwerpen van (efficiente) algoritmen. In deze tijd van buzzwords, patterns en frameworks zouden we bijna vergeten dat dit de basis van het werk van een programmeur is.

Een algoritme is een sequentie van instructies die gevolgd moeten worden om een bepaald doel te bereiken. Dit is dus breder dan  instructies voor processoren; ook een handleiding om een ikea kast in elkaar te zetten is een algoritme. Een algoritme is dus in feite een combinatie van 2 dingen; een bepaald doel dat we willen bereiken plus een lijst van stappen die we moeten ondernemen om dit doel te bereiken. Zo zijn er vaak tal van verschillende algoritmen om een bepaald doel te bereiken; een ieder die wel eens een Ikea kast in elkaar heeft gezet zal dat beamen. Meerdere wegen leiden naar Rome.

Terug naar de informatica is een van de meest genoemde de familie van sorteeralgoritmen. Bubble Sort, Selection Sort, Bucket Sort; er zijn er vele. Mocht je ooit in de situatie terechtkomen dat je zelf een sorteeralgoritme dient te schrijven kan het lonen om hier eens naar te zoeken. Ik neem hier geen bronnen op omdat er simpelweg teveel zijn; weinigen zitten nog op wikipedia links te wachten gok ik.

Dat zijn bekende voorbeelden, maar een gebied waar de keuze voor een juist en efficient algoritme essentieel is is parallelle verwerking. Hoe ga ik een bepaalde workload handig over een aantal processing nodes verdelen? Hoe regel ik communicatie in een point-to-point gekoppelde event gedreven architectuur? Hoe synchroniseer ik twee sets aan gegevens efficient die onafhankelijk van elkaar zijn gemuteerd?

Feit is dat er gigantisch veel uitwerkingen zijn van verschillende algoritmes; de moeite waard om daar eens in te duiken als dat van toepassing is. Maar hoe pak je nou een probleem aan dat nog niet zo vaak bij de hand gehad is, of waar geen standaard oplossingen van te vinden zijn? Met andere woorden, hoe ontwerp en implementeer ik zelf een goed algoritme? In mijn optiek zijn er grofweg twee stijlen om een algoritme uit te werken.

Je kunt een algoritme in eerste instantie het meest natuurlijk beschrijven in een lange sequentie van acties; het wordt echter lastiger als er veel branches en loops nodig zijn. Helemaal in het geval dat een algoritme groeit en groeit naarmate er meer uitzonderingsgevallen bekend worden. Dit verschijnsel wordt wel ‘lava flow’ genoemd en kan erg vervelend worden om te debuggen.
Desalniettemin is dit probleem met technieken als Dijkstra’s structured programming wel te voorkomen en is de procedurele benadering in bepaalde gevallen zeker een goede en natuurlijke manier van uitwerken van algoritmes.

Een andere benadering is de object georienteerde; je creeert een sequence diagram van de acties en probeert hierin steeds de bal over te spelen naar een ander object. Een mooie bijkomstigheid van deze truc is dat je wat meer vanuit het doel van het algoritme kunt rederneren. Er is een bepaald object dat aan het einde van de rit een bepaalde stateverandering moet ondergaan; neem bijvoorbeeld een lijst die gesorteerd moet worden. Je begint dan met de stap door tegen de lijst te zeggen dat deze zichzelf dient te sorteren. De lijst gaat vervolgens aan alle objecten die hij/zij bevat vragen of ze zichzelf met een buurman/vrouw willen vergelijken (object: vergelijk jezelf met dit object). Op deze manier kan bepaald worden of een tweetal objecten omgedraaid moeten worden of niet. Als je de vergelijking encapsuleert en overlaat aan de objecten zelf win je ook nog eens gigantisch in flexibiliteit – dit heeft immers niets meer te maken met met je sorteeralgoritme!
Op deze manier ontstaat een netwerk van kleinere objecten die samen het probleem gaan oplossen door zoveel mogelijk van het werk steeds door te geven en alleen het werk dat betrekking heeft op de eigen fields uit te voeren. Een aantal zeer goede artikelen over dit onderwerp zijn te vinden op deze site.

Wat is nu de moraal van dit verhaal? Bij welke complexiteit is het raadzaam om niet meer procedureel aan de gang te gaan maar object georienteerd?

Mijn antwoord zou zijn: als je zelf een (complex) algoritme moet ontwerpen, probeer hier dan eens een keer object georienteerde technieken op toe te passen. Verdiep je in de sequence en het doel van het algoritme, en je zult op een gegeven moment zien dat de oplossing ‘ontstaat’ door een samenwerking van potentieel vele objecten.
Heb je echter een ‘standaard’ probleem, probeer dan eens uit te vinden wat hier niet al over gepubliceerd is. Wellicht is dan een stukje procedurele code veel handiger.


Werken met ?
Kijk dan bij onze mogelijkheden voor zowel starters als ervaren engineers.


Categorieën: Development

Tags: , ,


Trackback & Pingback (1)

  1. Van Meditaties over Algoritmiek | Software Innovators op 23 februari 2009 at 11:07

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