Ett kort TDD-inlägg
Jag är ett fan av TDD sedan ungefär ett år tillbaka. Men ibland diggar jag det inte; det passar inte allt utvecklingsarbete en programmerare gör vid datorn.
Problemet
Igår ställdes jag inför problemet att försöka sortera ett antal punkt i något slags sick-sack ordning, nerifrån och upp, rad för rad. Algoritmen ska klara att börja i alla fyra hörn av den omslutande boxen kring punkterna, och dessutom "röra sig" antingen horisontellt eller vertikalt. En ytterligare komplikation är att den förutom sicksackmönstret ska klara av att röra sig "radvis" dvs. starta om istället för att "vända" när den påbörjar en nyrad.
Försök till exempel i ASCII-art:
* *
* * *
* *
.. skulle ge, med start i neder vänster hörn, horisontell rörelse och sicksackmönster:
+-->
|__,
>--+
Det är ett ganska inprecist ställt problem och är (tyvärr?) ganska lättlöst för det mänskliga ögat. En förenklande åtgärd är att anta att man alltid börjar i nedervänster hörn och alltid rör sig horisontellt; alla andra fall kan lösas med hjälp av en sådan algoritm plus speglingar/rotationstransformationer av punkterna.
Försök ett
Min kollega och jag diskuterade en "enkel lösning" först av allt. Idén gick ut på att dela upp problemet i en optimeringsdel och en "arbetshäst"; arbetshästen delade upp punkterna i N antal mängder mha. jämnt fördelade linjer från botten till toppen av den omslutande rektangeln. Optimeringsdelen testade sedan alla möjliga sådana delningar för N=3 till 50 eller liknande fixa konstanter, och valde helt enkelt den "orm" som var kortast.
Entusiastisk inför uppgiften satte jag mig och började skissa på olika hjälpklasser jag skulle använda mig av för att implementera algoritmen. Till att börja med ville jag göra klassificeringen av punkterna enkel, och den blir väldigt enkel om man skalar om punkternas y-värden till heltal, i en skala som bestäms med hjälp av N och den omslutande boxen. Det problem som verkade enklast att börja med var också icke-sicksack-mönstret, dvs. radvis ordning. Då slapp jag tänka på exakt när och hur "ormen" skulle vända. Jag byggde tre miniklasser för detta delproblem:
RowByRowOrder: givet en lista med punkter, klassificeras punkterna efter (int)y dvs heltalsdelen på sin y-koordinat och därefter x. Snabbt och lätt alltså.
SupportLine: kunde givet en omslutande rektangel och ett N beräkna ymin, ystep för linjärt positionerade stödlinjer.
Scaler: kunde omvandla från y i världskoordinater till RowByRowOrder-anpassat y.
Att utveckla och få rätt på dessa klasser tog kanske en eftermiddag. De funkade som tänkt, och jag kunde påbörja den omslutande optimeringsdelen.
Käppar i hjulet
Här uppstod problem. Med tex. en 9x3 grid av punkter som var något ojämnt utplacerade, valde optimeringsdelen hellre N=27 än det mer naturliga N=8, något det mänskliga ögat utan vidare såg. Men optimeringsalgoritmen följde endast vad jag bett den om: minimera ormens längd. Den hittade helt enkelt en orm som splittade en punktrippel i två delar, så att ormen kunde ta sig "rakt upp" istället för att röra sig diagonalt till nästa rad. Smart, men inte riktigt vad jag var ute efter.
Så jag började fundera på vad som var en bättre kriterie, var kort inne på minimera N men det är dödfött eftersom det alltid gick att hitta en orm oavsett N. Tredje försöket blev att minska övre gränsen 50 ner till något rimligt, hastade ihop gränsen N = antal punkter / 2, efter som det på något sätt är rimligt att anta att varje rad innehåller åtminstone 2 punkter. Då hittade algoritmen N=12 istället för N=8 i ovan beskrivna exempel.
Alphasort
Det slog mig plöstligt hur jag kunde splitta punkterna med hänsyn taget endast till deras y-värde och ett bra kriterie som löst baseras på två på varandra följande punkters y-koordinat. Jag ska inte avslöja exakt hur, men jag kan säga att den algoritmen kodade jag på mindre än 10 minuter och den ger riktigt övertygande resultat, inte bara i 9x3-fallet utan i alla andra "trovärdiga" fall jag kunnat hitta på! Jag kallade algoritmen Alphasort. Dessutom klarar den både sicksack och rad-för-rad-mönstret utan någon komplicerad logik.
Jag kunde skrota alla tre hjälpklasser och använda min mindre-än-en-kodsida-alphasort. Den utvecklade jag utan TDD medan de övriga utvecklades minutiöst med TDD.
Slutsats
Nå, vad är sensmoralen? Jo det är att prototypning / efterforskning bäst görs INNAN TDD stadiet - jag visste inte vad jag ville ha förrän jag prövat flera metoder.
TDD när man har en klar bild av matematiken i huvudet; efterforskning, prototypkod innan dess!
Problemet
Igår ställdes jag inför problemet att försöka sortera ett antal punkt i något slags sick-sack ordning, nerifrån och upp, rad för rad. Algoritmen ska klara att börja i alla fyra hörn av den omslutande boxen kring punkterna, och dessutom "röra sig" antingen horisontellt eller vertikalt. En ytterligare komplikation är att den förutom sicksackmönstret ska klara av att röra sig "radvis" dvs. starta om istället för att "vända" när den påbörjar en nyrad.
Försök till exempel i ASCII-art:
* *
* * *
* *
.. skulle ge, med start i neder vänster hörn, horisontell rörelse och sicksackmönster:
+-->
|__,
>--+
Det är ett ganska inprecist ställt problem och är (tyvärr?) ganska lättlöst för det mänskliga ögat. En förenklande åtgärd är att anta att man alltid börjar i nedervänster hörn och alltid rör sig horisontellt; alla andra fall kan lösas med hjälp av en sådan algoritm plus speglingar/rotationstransformationer av punkterna.
Försök ett
Min kollega och jag diskuterade en "enkel lösning" först av allt. Idén gick ut på att dela upp problemet i en optimeringsdel och en "arbetshäst"; arbetshästen delade upp punkterna i N antal mängder mha. jämnt fördelade linjer från botten till toppen av den omslutande rektangeln. Optimeringsdelen testade sedan alla möjliga sådana delningar för N=3 till 50 eller liknande fixa konstanter, och valde helt enkelt den "orm" som var kortast.
Entusiastisk inför uppgiften satte jag mig och började skissa på olika hjälpklasser jag skulle använda mig av för att implementera algoritmen. Till att börja med ville jag göra klassificeringen av punkterna enkel, och den blir väldigt enkel om man skalar om punkternas y-värden till heltal, i en skala som bestäms med hjälp av N och den omslutande boxen. Det problem som verkade enklast att börja med var också icke-sicksack-mönstret, dvs. radvis ordning. Då slapp jag tänka på exakt när och hur "ormen" skulle vända. Jag byggde tre miniklasser för detta delproblem:
RowByRowOrder: givet en lista med punkter, klassificeras punkterna efter (int)y dvs heltalsdelen på sin y-koordinat och därefter x. Snabbt och lätt alltså.
SupportLine: kunde givet en omslutande rektangel och ett N beräkna ymin, ystep för linjärt positionerade stödlinjer.
Scaler: kunde omvandla från y i världskoordinater till RowByRowOrder-anpassat y.
Att utveckla och få rätt på dessa klasser tog kanske en eftermiddag. De funkade som tänkt, och jag kunde påbörja den omslutande optimeringsdelen.
Käppar i hjulet
Här uppstod problem. Med tex. en 9x3 grid av punkter som var något ojämnt utplacerade, valde optimeringsdelen hellre N=27 än det mer naturliga N=8, något det mänskliga ögat utan vidare såg. Men optimeringsalgoritmen följde endast vad jag bett den om: minimera ormens längd. Den hittade helt enkelt en orm som splittade en punktrippel i två delar, så att ormen kunde ta sig "rakt upp" istället för att röra sig diagonalt till nästa rad. Smart, men inte riktigt vad jag var ute efter.
Så jag började fundera på vad som var en bättre kriterie, var kort inne på minimera N men det är dödfött eftersom det alltid gick att hitta en orm oavsett N. Tredje försöket blev att minska övre gränsen 50 ner till något rimligt, hastade ihop gränsen N = antal punkter / 2, efter som det på något sätt är rimligt att anta att varje rad innehåller åtminstone 2 punkter. Då hittade algoritmen N=12 istället för N=8 i ovan beskrivna exempel.
Alphasort
Det slog mig plöstligt hur jag kunde splitta punkterna med hänsyn taget endast till deras y-värde och ett bra kriterie som löst baseras på två på varandra följande punkters y-koordinat. Jag ska inte avslöja exakt hur, men jag kan säga att den algoritmen kodade jag på mindre än 10 minuter och den ger riktigt övertygande resultat, inte bara i 9x3-fallet utan i alla andra "trovärdiga" fall jag kunnat hitta på! Jag kallade algoritmen Alphasort. Dessutom klarar den både sicksack och rad-för-rad-mönstret utan någon komplicerad logik.
Jag kunde skrota alla tre hjälpklasser och använda min mindre-än-en-kodsida-alphasort. Den utvecklade jag utan TDD medan de övriga utvecklades minutiöst med TDD.
Slutsats
Nå, vad är sensmoralen? Jo det är att prototypning / efterforskning bäst görs INNAN TDD stadiet - jag visste inte vad jag ville ha förrän jag prövat flera metoder.
TDD när man har en klar bild av matematiken i huvudet; efterforskning, prototypkod innan dess!
Kommentarer
Trackback
