2010-03-15

Träd, gräs och stenar

Det blir en del programmering här just nu, men jag kanske är periodare. Eftersom jag är periodare så skriver jag inte kod tillräckligt ofta för att vara speciellt bra på det. Därför kan jag bli entusiastisk över idéer som smarta människor, som DU, tycker är bisarrt uppenbara.

Idag skulle jag skriva en funktion för att kolla hur djupt och brett ett träd är, där varje nod i trädet kan ha ett godtyckligt antal barn. Enligt KISS-principen så delade jag upp den i två, och skrev den enklaste först. Det enklaste är djupet, där man helt enkelt gör en rekursiv djupet-först-sökning (ah, direktöversättningar av datatermer, jag borde söka jobb på IDG) och adderar ett till djupet för varje steg i rekursionen och returnerar det största värdet.

Sen skulle jag göra bredd-funktionen (the bread function), och då tänkte jag först breadth first search. Det är lite jobbigt, man måste hålla i listor med noder så att man inte doppar tårna för djupt innan man har promenerat igenom alla syskon, kusiner, sysslingar, bryllingar, tremänningar etc. Och loopar i koden, känns inte det som att det ökar den cyklomatiska komplexiteten och är allmänt 60-tal sådär? Jo.

Alltså gjorde jag så här istället: jag skrev en rekursiv djupet-först-funktion, till vilken jag skickade med en noll-initialiserad int-array och det aktuella djupet. För varje nod som besöks så ökar jag numret på djupets index i arrayen med ett, och för varje rekursivt anrop så ökar jag djupet med ett. När det första rekursiva anropet returnerar så har jag en array med antalet noder på varje djupnivå, så det är bara att gå igenom den och plocka det största numret i arrayen, som är trädets största bredd. Eller på ren svenska:

void checkBreadthRec(Node node, int currDepth, int breadths[])
Node curr = GetFirstChild(node)

breadths[currDepth]++

while(curr)
checkBreadthRec(curr, currDepth+1, breadths)
curr = GetNextSibling(curr)

Det mest komplicerade i den här funktionen är typ att jag använde ordet "breadth" som det är lite jobbigt att skriva och uttala. Om jag har gjort något misstag i pseudo-koden så blir det extra pinsamt, eftersom det här är så sjukt enkelt.

5 kommentarer:

hjon sa...

Det känns ändå roligt att du kan bli entusiastisk över idéer som smarta människor, som JAG, tycker är bisarrt uppenbara. Kids In Satan's Service-principen?

puterman sa...

Keep it simple, stupid!

Och jag tror att förkortningen som förekommer i rockbandets namn står för Knights in Satan's Service, precis som W.A.S.P. står för We Are Satan's People.

Olof sa...

Snyggt, men varför skriver du dina egna trädrutiner? Det här är inget skämt syftande på rasterinterrupt och liknande; det är bara det att det finns så mycket bra GNU-bibliotek för allt möjligt, så varför inte använda ett sådant?

Tacksam för svar. Häj!

WV: gyphylop (låter som en forntida antilop med gälar)

JackAsser sa...

Bara för att skriva så där äckligt kryptisk C-kod så kan du slänga ihop djupmätaren och pekaren till arrayn:

void checkBreadthRec(Node node, int breadths[])
{
Node curr = GetFirstChild(node)

*breadths++

while(curr)
checkBreadthRec(curr, breadths+1)
curr = GetNextSibling(curr)
}

Tillförde ju såklart inget egentligen mer än att det gjorde koden mera oläsbar och opraktisk, men även oportbar till t.ex. Java. Bra va? :D

puterman sa...

Olof: Det är jobbkod. Vi har egen kod för datastrukturer som är mer specialiserad, minnessnål och optimerad än vad du hittar i t.ex. glib. Dessutom kan vi inte använda (L)GPL-kod, på samma sätt som ni inte kan använda det.

Andreas: Tummen upp, det är en viktig grundregel att OM man kan använda pekararitmetik, så SKA man göra det.