Kalenderluke 2: Syklomatisk kompleksitet


mandag 2. desember 2013 Julekalender

Luken for 2. desember dreide seg om syklomatisk kompleksitet. Jeg presenterte litt JavaScript-kode, og deltagerne skulle finne kompleksiteten. Det tok bare fem minutter før Bente C. Andorsen klarte oppgaven. Hun fikk 20 poeng, og med den tredje beste tiden fra i går inntar hun ledelsen med 28 poeng.

På delt andreplass med 19 poeng etter to luker ligger Magnar Sveen fra Kodemaker (som blogget for meg i fjorårets kalender) og Sebastian Holager fra CRM Norge AS.

Det var relativt bra trøkk på serveren da luken ble tilgjengelig akkurat klokken 9, men den klarte seg fint – jeg var litt usikker, men ser nå at en gratis-node på Heroku er mer enn godt nok for applikasjonen min.

Google_analytics_luke2

Oppgaven var litt vanskeligere denne gangen, og de første som forsøkte seg svarte feil. Her er en kjapp oversikt over de ulike svarene som ble gitt den første timen. X-aksen er antall svar:

luke2_svar

Fire stykker svarte også "O(n)", to svarte "n", og en svarte "n+1". Men det var altså 9 som var det riktige svaret.

For å bekrefte dette kan du lime koden inn i jscomplexity.org. Det finnes andre online analyseverktøy for JavaScript – også noen som sier at kompleksiteten er noe annet enn 9, noe som kan være forklaringen på den høye forekomsten av svaret 10. Jeg er derimot ganske sikker på at ut i fra det jeg har lært så er 9 det korrekte svaret. Hvis noen har lyst til å diskutere dette, og kanskje lære meg noe, så er det helt greit. Men de som svarte 9 får uansett poengene.

Nedenfor følger koden fra oppgaven. Jeg har markert alle steder i koden som representerer en "branch" i kontrollflyten - der hvor programmet må gjøre et valg. For å finne syklomatisk kompleksitet kan man telle antallet valg og plusse på 1. Merk at et if/else-valg teller som én, og default i en switch teller du ikke med av samme grunn.

var foo = function(a, b, c) {
  if (b.someField) b.doSomething();
  if (b && c) {
    switch (b.someField) {
    case 0:
      c.doSomething();
      break;
    case 1:
      c.doSomeOtherThing();
      break;
    default:
      c.someField ? c.doSomeThirdThing() : c.doSomethingElse();
    }
  } else if(c) {
    var a = a || [];
    while(a.length > 0) {
      var x = a.pop();
      c.doSomethingTo(x);
    }
  } else {
    console.log("Nothing to do");
  } 
};

Det som kan være de ekle fellene her er kondisjonaloperatoren ? : og det logiske OR-uttrykket hvor jeg sier a || []. Begge deler kan erstattes direkte med en if/else.

det var dag 2, og vi har 22 luker igjen og mange poeng å dele ut. I morgen vil førstemann få 30 poeng, og kan gå rett i ledelsen selv uten å ha svart på luke 1 eller 2. Så billetten til NDC 2014 donert av Programutvikling er fortsatt oppnåelig for hvem som helst!


comments powered by Disqus