Ilus vs. kiire kood

Mõni aeg tagasi oli meil vaja leida Spring Bean‘ide vahelisi ringsõltuvusi. Kuna ringsõltuvused tekitavad kohati probleeme, tuleks nendest tavaliselt hoiduda. Kui nad aga juba olemas on, siis tuleb nad kõigepealt üles leida, et vaadata mis neist edasi saab. Selleks kirjutas AK Ruby skripti, mis tuvastas Spring‘i konfiguratsioonifailis leiduvad ringsõltuvused ja kirjutas need graafina DOT faili. DOT failist oskab näiteks Graphviz renderdada visuaalse pildi.

Millegipärast selle Ruby skripti esimene versioon vajas lõpuni käimiseks paar tundi. XML teegi vahetusega REXML’ist Hpricot‘iks läks ajakulu paarilt tunnilt paarile minutile, aga minu sisetunne ütles, et Javas ei tohiks selline asi üle 10 sekundi võtta (arvestades faili suurust). Seega mõtlesin alguses kirjutada Javas sarnase programmijupi, et näha kuidas asi tegelikult on. Kuna parajasti õppisin ka sellist Java platvormil jooksvat keelt nagu Scala, mille jõudlus peaks olema Javaga peaaegu identne, siis otsustasin hoopis Scalat proovida. Tulemus üllatas mind ennastki: esimene versioon Scala skriptist jooksis umbes sekundi. Abiks oli ka natuke efektiivsem algoritm, mis tegi küll koodi keerulisemaks.

Lõpuks kasvas sellest katsetusest mõte teha põhjalikum võrdlus sarnase algoritmiga koodijuppidest erinevates programmeerimiskeeltes, rõhuga nn. “skriptimiskeeltel”. Võrdluses vaatan selliseid asju nagu koodi loetavus, abstraktsiooni tase ja kiirus. Abstraktsiooni taseme all mõtlen seda, et ideaalne oleks kui ma saaksin oma imperatiivsele pseudokoodile võimalikult täpselt vastava reaalse koodi ja boilerplate selle ümber läheneks nullile. Käesolevas postituses kirjeldangi algoritmi ja probleemi püstituse. Järgmis(t)es osa(de)s võrdlen konkreetseid keeli: esiteks Ruby, Scala ja Java, võib-olla hiljem võtan ette veel Python‘i, Groovy vms. Võite ka kommentaarides muid keeli pakkuda, aga suurt hulka ei ole plaanis ette võtta ja väga esoteerilisi ka mitte.

Kasutatud algoritm ringsõltuvuste leidmiseks ei ole kindlasti kõige efektiivsem ega pretendeeri millelegi, aga illustreerib mõningaid keelte ja teekide omadusi ning annab aimu nende kasutamismugavusest skriptimise jaoks ja kiirusest. Tegemist tuleb XML protsessimise ja listi või muu sarnase andmestruktuuri kasutamisega rekursiivses funktsioonis, selle struktuuri String’iks muutmisega. Muud nagu eriti polegi, sest algoritm on tegelikult üsna lihtne. Pseudokoodis võiks see välja näha umbes selline (XML’ile viitamiseks kasutan midagi XPath’i sarnast):

doc = readXmlFile "spring-beans.xml"

function findCircular(lastBean, dependencyPathSoFar) {
  if (dependencyPathSoFar contains lastBean/@id) {
    println '"' + (dependencyPathSoFar + lastBean/@id).toStringWithSeparator('" -> "') + '";'
  } else {
    for each (prop : lastBean/property) {
      findCircular(doc/beans/bean[@id = prop/@ref], dependencyPathSoFar + lastBean/@id)
    }
  }
}

println "digraph {[concentrate=true]"

for each (bean : doc/beans/bean) {
  findCircular(bean, EmptyList)
}

println "}"

Loodan, et see on enam-vähem arusaadav, sest paremini ma ei osanud seda algoritmi kirja panna. Ühe lausega kokku võttes: iga dokumendis leiduva bean’i puhul “kõnnitakse” rekursiivselt mööda tema sõltuvusi (lisades sõltuvused ahelasse), kuni jõutakse

  1. sellise bean’ini, mis juba üks kord esines sõltuvuste ahelas — järelikult on tegu ringsõltuvustega ja kogu ahel, mis ringsõltuvuses osales, kirjutatakse väljundisse;
  2. sellise bean’ini, millel enam sõltuvusi pole.

Spring’i konfiguratsiooni tugi ei ole täielik, sõltuvusteks loetakse ainult <property ref="..."/> elemendid, kus ref viitab mingi teise bean‘i id‘le. Kui see skripti käivitada järgmise lihtsustatud sisendfailiga:

<beans>
    <bean id="A">
        <property ref="C" />
    </bean>
    <bean id="B">
        <property ref="A" />
    </bean>
    <bean id="C">
        <property ref="B" />
    </bean>
    <bean id="D"></bean>
    <bean id="E">
        <property ref="D" />
    </bean>
</beans>

Siis väljund on selline:

digraph {[concentrate=true]
"A" -> "C" -> "B" -> "A";
"B" -> "A" -> "C" -> "B";
"C" -> "B" -> "A" -> "C";
}
Graafi näide

Nagu näha on algoritm veel ebaefektiivne ka selle poolest, et väljundis esineb korduvaid elemente, mida pole tegelikult vaja. Aga antud eksperimendi mõte polegi välja mõelda parimat algoritmi, see võib jääda huvilistele koduseks ülesandeks. Järgmises osas võrdlen selle algoritmi realiseerimist Rubys, Scalas ja Javas. Java pole küll eriti mõeldud skriptimiseks, aga kuna ka JVM-il jooksvad skriptimiskeeled on viimasel ajal popimaks muutunud, siis võib jõudluse ja koodi võrdlus olla huvitav. Jõudlustestid teen suurema sisendfailiga, mis obfuskeeritud kujul on siin olemas, juhul kui keegi tahab testi ise korrata.

1 thought on “Ilus vs. kiire kood”

Leave a Reply

Your email address will not be published. Required fields are marked *