34 |
Klinisk Biokemi i Norden · 2 2013
Med denna algoritm måste vi ”genom” alla data två
gånger, och en sådan algoritm kan kallas därför ”two-
pass algorithm”.
I dataspråk ser algoritmen ut så här (lägg märke till
att det finns två ”for”-loopar):
def two_pass_variance(data):
n = 0
sum1 = 0
sum2 = 0
for x in data:
n = n + 1
sum1 = sum1 + x
mean = sum1/n
for x in data:
sum2 = sum2 + (x - mean)*(x - mean)
variance = sum2/(n - 1)
return variance
Sedan några år tillbaka finns det en bättre algoritm
(uttänkt av multigeniet Donald Knuth) som bara måste
genom alla data en enda gång, en så kallad ”single-pass
algorithm”.
I dataspråk ser denna algoritm ut så här (med bara
en ”for”-loop):
def single_pass_variance(data):
n = 0
mean = 0
M2 = 0
for x in data:
n = n + 1
delta = x - mean
mean = mean + delta/n
M2 = M2 + delta*(x - mean)
variance = M2/(n - 1)
return variance
Sådana single-pass-algoritmer finns t.ex. för genom-
snitt, standardavvikelse, skevhet, kurtos och approxi-
mativa medianer. En single-pass-algoritm är exakt, och
detta betyder att äldre ”two-pass”-algoritmer för stan-
dardavvikelse nu är utdaterade, det finns ingen anled-
ning att använda dem längre. Single-pass-algoritmerna
är snabbare och de är också på andra sätt överlägsna
äldre algoritmer. Om de används på dataflöden kan
de hela tiden ge uppdaterade värden och man kan
lätt kombinera beräkningar av flera algoritmer i en
funktion.
Optimering
Till sist några ord om optimering. Optimering kan
väl beskrivas som ändringar i programkod som får ett
fungerande program till att bli snabbare. Optimering
är ett stort ämne. Enkla råd är väl att man först försöker
att åstadkomma ett program som fungerar (men som
kan vara långsamt). Därefter lägger man in klockfunk-
tioner, d.v.s. man tar tid på de olika operationerna i
programmet. Ofta finner man att en enstaka funktion
tar större delen av tiden, och om man sålunda klarar
att förbättra denna enda funktion, så blir programmet
avsevärt raskare. Man kommer oftast ganska långt med
små ändringar, av egen erfarenhet så blir program-
met snabbare om man undviker att skriva kod själv
och lånar kod eller funktioner som andra har skrivit.
Man bör också skriva programmet som andra skulle
ha gjort det, d.v.s. man skall använda så standardise-
rade lösningar sommöjligt. Omman nu ändå inte når
fram, kan man göra sommina matematikervänner gör,
skriva om den funktion som är kritisk i ett snabbare
programspråk (gärna C eller Python).
Många av oss använder icke-förkompilerade script-
språk, som R eller Perl. Dessa är mer användarvänliga,
men inte lika snabba som förkompilerade program
skrivna i C, C++ eller Python. De senaste åren har
dock användningen av Just-In-Time-kompilatorer
(JIT) ökat. Om man använder JIT till sina R-script så
ser JIT till att spara och återanvända kompilerad kod.
Användning av JIT kan ofta öka hastigheten på icke-
förkompilerade scriptspråk avsevärt.
XXXIV Nordic Congress in Clinical Chemistry
16-19 Sep 2014, Göteborg Sweden
