Exempel på problemlösning - Ändra representatio

I denna artikeln bygger vi vidare på exempel 1, men nu ska vi ändra representation.

Roffe är förbannad. Han tycker att koden vi har byggt upp är för långsam. Ett exempel han ger är följande kod:

PHP - PHP: Hypertext Preprocessor
<?php // Inkludera alla funktioner include_once 'datumhanterare.php'; // Skapa datumet 2011-03-15 $datum = nyttDatum(2011, 3, 15); // Öka datumet med 1000 dagar $datum = ändraDatum(1000, $datum); // Skriv ut datumet echo datumTillSträng($datum); ?>

Nu är det upp till oss att hitta vad det är som tar lång tid och förbättra det, så vi börjar analysera koden. Att köra funktionen nyttDatum kommer inte ta lång tid, allt den gör är att skapa en array och skicka tillbaka den. Att köra funktionen datumTillSträng borde inte heller ta lång tid, där bygger vi bara upp en sträng. Att köra funktionen ändraDatum tar nog däremot lite längre tid att köra. Där har vi en loop som (i detta fallet) kommer köras 1000 gånger, och det är här vi kan optimera. Men hur kan vi undvika loopen? Om det var så enkelt som att addera $datum['dag'] med 1000 skulle vi ju slippa loopen, men så enkelt är det inte. Men kan vi på något sätt göra det så enkelt?

Vi börjar tänka för oss själva. Just nu representerar vi ett datum som en associativ array med året, månaden och dagen i månaden. Kan vi på något sätt representera ett datum med enbart dagar? Det borde gå. Om vi istället representerar ett datum som antalet passerade dagar sedan tidsräkningens början (0000-00-00) så kan vi uttrycka ett datum i enbart dagar. Då slipper vi loopen i funktionen ändraDatum, men funktionerna nyttDatum och datumTillSträng blir visserligen lite krångligare, men förhoppningsvis kommer koden bli snabbare överlag att exekvera. Så vi börjar om från början med vår nya representation.

PHP - PHP: Hypertext Preprocessor
<?php // Funktion som skapar ett nytt datum function nyttDatum($år, $månad, $dag){ // Räkna ut hur många dagar som passerat i föregående år $passeradeÅrIDagar = 365*$år // Räkna ut hur många dagar som passerat föregående månader detta året $passeradeMånaderIDagar = 0; for($i=0; $i<$månad; $i++){ $passeradeMånaderIDagar += antalDagarIMånad($i); } // Räkna ut hur många dagar som passerat totalt fram tills datumet $passeradeDagarTotalt = $passeradeÅrIDagar + $passeradeMånaderIDagar + $dag; // Och skicka tillbaka det return $passeradeDagarTotalt; } // Funktion som returnerar antalet dagar i angiven månad function antalDagarIMånad($månad){ $antalDagarIMånader = array( 1 => 31, 2 => 28, 3 => 31, 4 => 30, 5 => 31, 6 => 30, 7 => 31, 8 => 31, 9 => 30, 10 => 31, 11 => 30, 12 => 31 ); return $antalDagarIMånader[$månad]; } // Skapar det nya datumet 2011-04-13 $datum = nyttDatum(2011, 4, 13); ?>

Som du ser får vi en loop i funktionen nyttDatum. Är det ok? Vi ändrade ju representationen just för att slippa loopar! Men det är faktiskt lugnt. Den här loopen kommer att köra max 11 varv. Loopen vi hade i funktion ändraDatum skulle köras lika många varv som antalet dagar vi ville ändra datumet med, så den tar längre och längre tid på sig ju fler dagar vi vill ändra, så den har ingen max-gräns. Loopar med begränsade varvtal är att föredra framför loopar som inte har det, så vi kör på det som vi har.

Nästa funktion att implementera är datumTillSträng. Om vi bara hade en funktion som gjorde om dagar till år, månad och dag i månad skulle vi i princip kunna använda samma funktion som vi hade innan.

PHP - PHP: Hypertext Preprocessor
<?php // Funktion som skapar ett nytt datum function nyttDatum($år, $månad, $dag){ // Räkna ut hur många dagar som passerat i föregående år $passeradeÅrIDagar = 365*$år // Räkna ut hur många dagar som passerat föregående månader detta året $passeradeMånaderIDagar = 0; for($i=0; $i<$månad; $i++){ $passeradeMånaderIDagar += antalDagarIMånad($i); } // Räkna ut hur många dagar som passerat totalt fram tills datumet $passeradeDagarTotalt = $passeradeÅrIDagar + $passeradeMånaderIDagar + $dag; // Och skicka tillbaka det return $passeradeDagarTotalt; } // Funktion som returnerar antalet dagar i angiven månad function antalDagarIMånad($månad){ $antalDagarIMånader = array( 1 => 31, 2 => 28, 3 => 31, 4 => 30, 5 => 31, 6 => 30, 7 => 31, 8 => 31, 9 => 30, 10 => 31, 11 => 30, 12 => 31 ); return $antalDagarIMånader[$månad]; } // Funktion som gör om antalet dagar till en sträng function datumTillSträng($dagar){ // Den här funktionen måste vi skapa $datum = dagarTillDatum($dagar); $sträng = $datum['år'].'-'; if($datum['månad'] < 10){ $sträng .= '0'; } $sträng .= $datum['månad'].'-'; if($datum['dag'] < 10){ $sträng .= '0'; } $sträng .= $datum['dag']; return $sträng; } // Skapar det nya datumet 2011-04-13 $datum = nyttDatum(2011, 4, 13); ?>

Som du ser behöver vi enbart skapa funktionen dagarTillDatum för att det ska fungera, och den funktionen är inte alltför svår att skapa, även om det krävs en del tänkande.

PHP - PHP: Hypertext Preprocessor
<?php // Funktion som skapar ett nytt datum function nyttDatum($år, $månad, $dag){ // Räkna ut hur många dagar som passerat i föregående år $passeradeÅrIDagar = 365*$år // Räkna ut hur många dagar som passerat föregående månader detta året $passeradeMånaderIDagar = 0; for($i=0; $i<$månad; $i++){ $passeradeMånaderIDagar += antalDagarIMånad($i); } // Räkna ut hur många dagar som passerat totalt fram tills datumet $passeradeDagarTotalt = $passeradeÅrIDagar + $passeradeMånaderIDagar + $dag; // Och skicka tillbaka det return $passeradeDagarTotalt; } // Funktion som returnerar antalet dagar i angiven månad function antalDagarIMånad($månad){ $antalDagarIMånader = array( 1 => 31, 2 => 28, 3 => 31, 4 => 30, 5 => 31, 6 => 30, 7 => 31, 8 => 31, 9 => 30, 10 => 31, 11 => 30, 12 => 31 ); return $antalDagarIMånader[$månad]; } // Funktion som gör om antalet dagar till en sträng function datumTillSträng($dagar){ $datum = dagarTillDatum($dagar); $sträng = $datum['år'].'-'; if($datum['månad'] < 10){ $sträng .= '0'; } $sträng .= $datum['månad'].'-'; if($datum['dag'] < 10){ $sträng .= '0'; } $sträng .= $datum['dag']; return $sträng; } function dagarTillDatum($dagar){ // Datumet vi ska skicka tillbaka $datum = array(); // Räkna ut vilket år $passeradeDagarIÅr = floor($dagar/365); $datum['år'] = $passeradeDagarIÅr; // Räkna ut hur många dagar som återstår $dagar = $dagar - $passeradeDagarIÅr*365; // Räkna ut vilken månad $passeradeDagarIMånader = 0; for($i=1; $i<=12; $i++){ // Om det är fler dagar kvar än det finns i denna månaden, // gå vidare i loopen och testa nästa månad if(dagarIMånad($i) < $dagar){ $dagar = $dagar - dagarIMånad($i); }else{ // Annars är det denna månden som ska vara i datumet $datum['månad'] = $i; break; // Avbryt loopen } } // Dagen i månaden är resterande dagar $datum['dag'] = $dagar; // Skicka tillbaka datumet return $datum; } // Skapar det nya datumet 2011-04-13 $datum = nyttDatum(2011, 4, 13); ?>

Som du ser får vi även i funktionen dagarTillDatum en loop (som vi ville undvika!), men precis som i fallet med funktionen datumTillSträng så är den begränsad (i det här fallet till max 12 varv), så det är ingen fara.

Nu ska vi bara lägga till funktionen ändraDatum så är vi klara, och eftersom vi representerar datumet som antalet dagar sedan tidsräkningens början blir denna funktionen lekande lätt.

PHP - PHP: Hypertext Preprocessor
<?php // Funktion som skapar ett nytt datum function nyttDatum($år, $månad, $dag){ // Räkna ut hur många dagar som passerat i föregående år $passeradeÅrIDagar = 365*$år // Räkna ut hur många dagar som passerat föregående månader detta året $passeradeMånaderIDagar = 0; for($i=0; $i<$månad; $i++){ $passeradeMånaderIDagar += antalDagarIMånad($i); } // Räkna ut hur många dagar som passerat totalt fram tills datumet $passeradeDagarTotalt = $passeradeÅrIDagar + $passeradeMånaderIDagar + $dag; // Och skicka tillbaka det return $passeradeDagarTotalt; } // Funktion som returnerar antalet dagar i angiven månad function antalDagarIMånad($månad){ $antalDagarIMånader = array( 1 => 31, 2 => 28, 3 => 31, 4 => 30, 5 => 31, 6 => 30, 7 => 31, 8 => 31, 9 => 30, 10 => 31, 11 => 30, 12 => 31 ); return $antalDagarIMånader[$månad]; } // Funktion som gör om antalet dagar till en sträng function datumTillSträng($dagar){ $datum = dagarTillDatum($dagar); $sträng = $datum['år'].'-'; if($datum['månad'] < 10){ $sträng .= '0'; } $sträng .= $datum['månad'].'-'; if($datum['dag'] < 10){ $sträng .= '0'; } $sträng .= $datum['dag']; return $sträng; } function dagarTillDatum($dagar){ $datum = array(); $passeradeDagarIÅr = floor($dagar/365); $datum['år'] = $passeradeDagarIÅr; $dagar = $dagar - $passeradeDagarIÅr*365; $passeradeDagarIMånader = 0; for($i=1; $i<=12; $i++){ if(dagarIMånad($i) < $dagar){ $dagar = $dagar - dagarIMånad($i); }else{ $datum['månad'] = $i; break; } } $datum['dag'] = $dagar; return $datum; } // Funktion som ändrar datumet det angivna antalet dagar function ändraDatum($dagar, $ändraDagar){ // Räkna ut det nya antalet dagar... $dagar = $dagar + $ändraDagar; // ...och skicka tillbaka det return $dagar; } // Skapar det nya datumet 2011-04-13 $datum = nyttDatum(2011, 4, 13); ?>

Nu kommer koden som Roffe gav som exempel gå mycket snabbare att köra, men betyder det att den här koden är bättre? Det finns tyvärr inget tydligt Ja- eller Nej-svar på den frågan, utan allting handlar om kompromisser. Visst, funktionen ändraDatum går fortare att exekvera nu, men de andra funktionerna tar längre tid på sig. Om man anropar funktionen ändraDatum många gånger så tjänar man definitivt på att använda den här implementation istället.

Sedan är den här representationen mycket svårare att implementera. Visst, det mest avancerade vi använde var faktiskt en for-loop, men att veta vilka uträkningar som ska göras är svåra. Anta till exempel att vi ska ta hänsyn till skottår med denna representationen. Vad behöver vi ändra? När vi hade den andra representationen behövde vi bara ändra funktionen dagarIMånad, men nu behöver vi även ändra vid raderna 7 och 72, då vi räknar på hur många dagar det går på ett år (nu utgår vi från att alla år är 365 dagar, men skottår är ju 366 dagar).