torsdag 28. mars 2013 F# Jobb Ruby Wordle
I dagens blogpost går jeg gjennom litt F#-kode jeg skrev for en konkret oppgave på jobben. Oppgaven ble først løst i Ruby, men jeg trengte bedre ytelse, og kodet det derfor etterpå i F#. Er du en F#-nybegynner kan det godt tenkes du kan plukke med deg flere tips her. Jeg vil forsøke å trekke frem noen av de mer avanserte elementene i koden.
Hin dagen lagde jeg et lite script for å telle opp antall forekomster av ord i en tekstfil – altså gruppere resultatet på hvert ord i filen ("bil" forekom 17 ganger, "båt" forekom 5 ganger osv.). Dette ville jeg gjøre for å kunne lage en ord-sky basert på tekstfilen. Her er for eksempel en ord-sky over de ti siste postene på bloggen min:
Det kan se ut som om jeg er litt selvopptatt :)
Her er en beskrivelse av scriptet:
Resultatfilen kan jeg så bruke som innput til Wordle og få generert en ord-sky. Ganske enkelt egentlig, og jeg laget raskt et script for dette i Ruby. Er du interessert finner du scriptet her.
Som jeg sa innledningsvis ønsket jeg bedre ytelse enn hva Ruby kunne gi meg. Filen jeg trengte å analysere var på over 50 MB og bestod av 500.000 linjer. Den inneholdt ca 518.000 unike ord, og over 6 millioner ord totalt. Jeg jobber jo med SMS, og dette var faktisk en halv million SMS-meldinger som skulle analyseres.
På min superduper-spekkede laptop brukte Ruby-scriptet mitt 88 sekunder på denne filen, og konsumerte 185 MB minne. Dette var med Ruby versjon 1.9.3. Til sammenligning bruker F#-programmet jeg nå skal lage under 16 sekunder på den samme filen (82% reduksjon i kjøretid), og trenger ikke mer enn 50 MB RAM (73% reduksjon).
88 sekunder er en evighet, mens jeg har tolmodighet nok til å vente i 16.
BONUSOPPGAVE TIL LESEREN: Klarer du å skrelle mer tid av algoritmen – enten i Ruby eller F#?
I F# må du definere en funksjon før du kan bruke den, så det er naturlig både å kode og å presentere koden bottom up.
open System
open System.Collections.Generic
let blacklist = [""; "på"; "og"; "er"; "om"; "fra"; "med"; "i"; "to";
"det"; "å"; "ditt"; "til"; "ved"; "fra"; "for"; "av";
"en"; "din"; "du"; "at"; "vi"; "har"; "vil"; "nå";
"det"; "som"; "dere"; "kan"; "vår"; "så"]
Først importerer jeg et par navnerom (samme som using i C#), og så lager jeg en liste med de ordene jeg ikke ønsker å inkludere i analysen.
Jeg trenger også en liten funksjon for å sjekke om et ord er svartelistet:
let blacklisted (word : string) =
List.exists ((=) (word.ToLower())) blacklist
Her bruker jeg exists-funksjonen i modulen List. Den tar to argumenter: En funksjon som returnerer true hvis elementet er funnet, og listen man skal lete i. Men funksjonsargumentet her er litt spesielt. Hva betyr ((=) (word.ToLower()))?
Dette er en såkalt partial application, som jeg har snakket om mange ganger før. = er en funksjon som sjekker om to verdier er like. Den brukes normalt infix, det vil si at den plasseres mellom sine to argumenter. Men om vi plasserer den mellom to paranteser blir den omgjort til en normal prefix-funksjon.
Det neste jeg har gjort er å sende ett – og bare ett – argument til funksjonen. Dette blir da omgjort til en ny funksjon som forventer ett argument til. ((=) (word.ToLower())) er dermed en funksjon som sjekker om noe er lik lowercase-versjonen av strengen word. De fre følgende uttrykkene er helt ekvivalente, og returnerer alle true:
((=) ("Foo".ToLower())) "foo"
(fun x -> ((=) ("Foo".ToLower())) x) "foo"
(fun x -> x = "Foo".ToLower()) "foo"
Vi går videre. Nå vil jeg lage en funksjon som stripper bort siste tegn fra en streng, men bare hvis det siste tegnet er en av et bestemt sett med tegn. I Ruby var dette gjort på én linje med gsub og et regulært uttrykk, men i F# benytter jeg anledningen til å eksperimentere litt.
(* Removes c from s if c is the last char *)
let (?<<) (s:string) (c:char) =
let lastIndex = s.Length - 1
if lastIndex >= 0 && s.LastIndexOf c = lastIndex
then s.Substring (0, lastIndex)
else s
Her har jeg laget en funksjon med det litt merkelige navnet ?<<. I tillegg har jeg lagt paranteser rundt, og slik blir det en operator på lik linje med pluss, minus, gange og deling.
Det ser rart ut, men den er elegant i bruk:
let stripPunctuation (word : string) =
word ?<< '.'
?<< ','
?<< '!'
?<< ':'
La oss si at word inneholder strengern "foo!". Funksjonen ?<< kalles da først med argumentene "foo!" og '.', og resultatet er "foo!" (ingen endring altså). Dette resultatet blir nå første argument til den neste ?<<-funksjonen, som har ',' som andre argument. Og slik fortsetter det. Den tredje ?<< kalles med "foo!" og '!', og returnerer da bare "foo".
Denne teknikken kalles gjerne pipelining.
I dette programmet vil jeg bruke en generisk Dictionary<Key, Value>, slik som mange av oss er vandt til fra C#. Koden som følger er ikke spesielt funksjonell, fordi jeg baserer meg på å "mutere" (dvs. endre) dataene i dictionarien direkte. Jeg har likevel valgt å gjøre det fordi jeg jo "oversatte" et Ruby-script som gjorde det på denne måten, og fordi det vil være minst like raskt som en mere funksjonell løsning som ikke muterer data.
Først definerer jeg en ny type. Dette gjør jeg egentlig kun for å være litt eksplisit i koden, og slippe å måtte skrive Dictionary<string, int> fullt ut diverse steder.
type WordMap = Dictionary<string, int>
Jeg lager så en hjelpefunksjon som inkrementerer telleren for et bestemt ord, eller setter verdien 1 om ordet ikke finnes i dictionarien m fra før:
let increment (m : WordMap) word =
if m.ContainsKey word
then m.[word] <- m.[word] + 1
else m.[word] <- 1
Når man muterer en variabel i F# bruker man ikke = slik man gjør i typiske imperative språk. I stedet bruker man <-.
let countWord acc word =
if not (blacklisted word)
then increment acc word
countWord er en funksjon som teller et ord fra filen jeg analyserer, men kun hvis ordet ikke er svartelistet. acc er en WordMap, men jeg behøver ikke fortelle F# det (det kan jo ikke være noe annet).
Nå har vi kommet til selve funksjonen som parser en fil og teller opp ordene i den – og her bruker vi alt vi har laget sålangt. Dette er den delen av programmet som konsumerer så og si all kjøretiden.
let parseWords fileName =
let accumulator = new WordMap()
let counter = countWord accumulator
use file = IO.File.OpenText fileName
while not file.EndOfStream do
let words = file.ReadLine().Split [|' '|]
|> Array.map stripPunctuation
Array.iter counter words
accumulator
Når jeg oppretter variabelen counter så bruker jeg partial application igjen – du husker kanskje at countWord er en funksjon som tar to argumenter, men her gir jeg bare ett.
Legg også merke til nøkkelordet use som jeg bruker når jeg åpner filen. Dette er det sammen som using i C#, og file vil bli lukket/disposed før variabelen går ut av scope.
Jeg ønsker også å fjerne ord som ikke gjentas mer enn X ganger i input-filen. Jeg har eksperimentert litt, og funnet at X = 1000 fungerer bra for de filene jeg jobber med, så jeg hardkoder likegreit denne verdien.
let trimRareWords pairsWithIntValue =
Seq.filter (fun (KeyValue(_, count)) -> count > 1000)
pairsWithIntValue
Argumentet til trimRareWords kommer til å være en WordMap, altså en Dictionary<string, int>. Og det kan man også se på som en sekvens med KeyValue<string, int>. Derfor kan jeg bruke Seq.filter til å luke bort ord. I den anonyme funksjonen jeg sender til filter bruker jeg pattern matching til å plukke ut antallet forekomster for et ord.
For å produsere filen på det formatet jeg ønsker trenger jeg to funksjoner til. Den første tar et ord med tilhørende antall og lager en tekststreng som Wordle vil forstå:
let wordleLine (KeyValue(word, count)) =
sprintf "%s:%i" word count
Så trenger jeg også en funksjon som kan ta en sekvens av slike strenger og skrive dem til en fil:
let linesToFile fileName ls =
IO.File.WriteAllLines(fileName, seq ls)
Da gjenstår det bare å sy det hele sammen. Jeg må ta imot input-filnavnet (argument til programmet) og sette opp en sekvens med funksjoner som kan ta imot dette og produsere Wordle-filen.
For å måle og rapportere hvor lang tid dette tar har jeg brukt en funksjon jeg har kalt benchmark. Denne vil jeg presentere i en blogpost senere, men den tar i alle fall to argumenter: En streng som vil bli brukt som en label ved rapportering, og en parameterløs funksjon (også kalt en thunk). Den vil eksekvere thunken, måle og printe ut hvor lang tid den tok, og returnere resultatet av thunken – som i dette tilfellet er unit (altså ingen verdens ting).
[<EntryPoint>]
let main argv =
benchmark "Elapsed"
(fun () -> Seq.head argv
|> parseWords
|> trimRareWords
|> Seq.sortBy (fun (KeyValue(_, v)) -> v)
|> Seq.map wordleLine
|> linesToFile "out2.txt")
0 // return an integer exit code
Og da var vi ferdige! Jeg håper du lærte noe. Og hvis du tror du kan lære meg noe, så vil jeg gjerne høre det – forslag til strukturelle forbedringer, eller ting som vil redusere kjøretiden mottas med takk!