A 2013/2014-es Informatika OKTV verseny 3. szám feladatának forráskódját fogjuk átalakítani tiszta és egyszerű kóddá. Letölthető a feladatlap, és a javítási-értékelési útmutató.
Miért OKTV-s versenyfeladaton?
Ezek a feladatok szándékosan olvashatatlan és bonyolult módon vannak megírva, hogy a versenyzőknek nehezebb legyen a kódot megérteniük.
A feladat
3. feladat: Adatok (48 pont)
Az alábbi algoritmus N nemnegatív adatot kap bemenetként (N>2, X(1)=0, X(N)=0, X(i)≥0) az X vektorban, amelyekből több értéket számol ki:
Valami(N,X,A,B,C): A:=0; D:=0; E:=0 Ciklus i=2-től N-ig Ha X(i-1)=0 és X(i)>0 akkor D:=0; E:=0 Ha X(i)>0 akkor D:=D+1 Ha X(i)>E akkor E:=X(i) Ha X(i)=0 és X(i-1)>0 akkor A:=A+1; B(A):=D; C(A):=E Ciklus vége Eljárás vége.
Ez Tiszta és Egyszerű kódnak tűnik, nem az?
Igen elsőre tisztának és egyszerűnek tűnik, a valóságban azonban nem az. Talán nem is a legjobb szó a tiszta (clean) és az egyszerű (simple), ha helyettük inkább az olvasható és érthető kifejezéseket használjuk, akkor talán jobban megértjük ezen programozási módszerek tartalmát.
Tiszta (olvasható) a kód?
Sajnos nem nagyon! Nem lehet tudni, hogy mit jelentenek az N,X,A,B,C,D,E jelek. Azt sem, hogy az eljárásunknak mik a bemenő, mik a kimenő paraméterei. Az olvashatóság szempontjából a pozitívum csupán a rövidsége és a formázása.
Egyszerű (érthető) a kód?
Sajnos ez sem igaz! Rengeteg az eljárásban a módosuló változó (mutable variable), ezek állapotait nehéz követni (fejben tartani). Rengeteg a hibalehetőség az eljárásban. 7 helyen is gond lehet a vektorok indexelésével, X(i) és X(i-1), könnyen indexelhetünk olyan vektor elemre, ami nem létezik és olyankor hibával le fog állni a program. A bemeneti értékekre előfeltevés van, ami fontos az eljárás szempontjából, ha azok nem igazak, akkor hibásan fog futni a program. Ezekre a feltételekre az eljárás nem ellenőriz rá.
Első kísérlet (Scala nyelven)
case class IntervalLengthAndMax(length: Int, max: Int) { def add(value: Int) = IntervalLengthAndMax(length + 1, math.max(max, value)) } private val emptyInterval = IntervalLengthAndMax(0, 0) def calcIntervals(values: List[Int]): (List[IntervalLengthAndMax]) = { val initState = (List.empty[IntervalLengthAndMax], emptyInterval) val (intervals, currentInterval) = values.foldLeft(initState) { case ((intervals, currentInterval), value) => (currentInterval, value) match { case (`emptyInterval`, 0) => (intervals, currentInterval) case (_, 0) => (currentInterval :: intervals, emptyInterval) case _ => (intervals, currentInterval.add(value)) } } if (currentInterval != emptyInterval) (currentInterval :: intervals).reverse else intervals.reverse }
Tiszta (olvasható) a kód?
Igen! :) Minden azonosítónak (változónak, eljárásnak, osztálynak) szép, beszédes neve van. Pontosan lehet tudni, hogy a függvényünknek mik a bemenő, mik a kimenő paraméterei. A függvény viszonylag rövid és formázott.
Egyszerű (érthető) a kód?
Ez is nagyjából igaz! Egyetlen módosuló változónk sincs (mutable variable). Egyetlen hibalehetőség sincs a programban. Nincs a bemeneti értékekre semmilyen előfeltevés. A program működése viszonylag könnyen megérthető.
Tudunk ezen még egyszerűsíteni? Igen, az állapotváltozást megadó részt kiemelhetjük egy külön függvénybe, így a két függvény megértése külön-külön sokkal egyszerűbb lesz, mint így együtt. Egy mélységgel kisebb is lesz a fő függvényünk, ami az olvashatóságot tovább fogja javítani.
Végeredmény
case class IntervalLengthAndMax(length: Int, max: Int) { def add(value: Int) = IntervalLengthAndMax(length + 1, math.max(max, value)) } private val emptyInterval = IntervalLengthAndMax(0, 0) private def calcNextState( state: (List[IntervalLengthAndMax], IntervalLengthAndMax), value: Int) = { val (intervals, currentInterval) = state (currentInterval, value) match { case (`emptyInterval`, 0) => state case (_, 0) => (currentInterval :: intervals, emptyInterval) case _ => (intervals, currentInterval.add(value)) } } def calcIntervals(values: List[Int]): (List[IntervalLengthAndMax]) = { val initState = (List.empty[IntervalLengthAndMax], emptyInterval) val (intervals, currentInterval) = values.foldLeft(initState)(calcNextState) if (currentInterval != emptyInterval) (currentInterval :: intervals).reverse else intervals.reverse }
Tiszta (olvasható) a kód?
Igen! :) Minden azonosítónak (változónak, eljárásnak, osztálynak) szép, beszédes neve van. Pontosan lehet tudni, hogy a függvényünknek mik a bemenő, mik a kimenő paraméterei. A függvények rövidek és jól formázottak.
Egyszerű (érthető) a kód?
Ez is igaz! :) Egyetlen módosuló változónk sincs (mutable variable). Egyetlen hibalehetőség sincs a programban. Nincs a bemeneti értékekre semmilyen előfeltevés. A függvények működése könnyen megérthető.
Állapotváltozást megadó rész:
- Ha az aktuális intervallum üres és a vizsgált érték 0, akkor nincs változás az állapotban
- Különben, ha a vizsgált érték 0, akkor az intervallumok elejére beszúrjuk az aktuális intervallumot és az új aktuális intervallumot üresre állítjuk
- Különben az intervallumok nem változnak és az aktuális intervallumhoz hozzáadjuk az értéket
Fő függvényünk:
- Kiindulási állapotunk egy üres intervallum listából és egy üres intervallumból áll
- Az értékeket (values) a kiindulási állapot és az állapotváltozást megadó rész alapján összesíti (foldLeft)
- Az így megkapott állapot alapján, ha az aktuális intervallum nem üres, akkor azt is hozzáadja, majd megfordítja a listát, mert fordított sorrendben gyűjtöttük.
A teljes forrás kód itt elérhető.