Lekte meg litt i Clojure i kveld med oppgave 2 fra posten som startet denne tråden:
...her er det du som skal tenke på et tall, og programmet skal gjette. Du gir tilbakemelding til programmet om det skal gjette høyere eller lavere. Her vil jeg også ha med at den teller antall forsøk, så da er det om å gjøre å finne ut hvordan du kan få den til å gjette tallet på færrest mulig forsøk.
Jeg lagde en ren funksjonell løsning:
Kode
(defn solve
"Side-effect free function to find a number in a range.
oracle is a function that will validate a guess (if it's
correct, too high, or too low. Yields the number of
guesses it had to make."
[from to oracle]
(letfn [(guess-between [low high]
(quot (+ low high) 2))]
(loop [attempts 1
low (dec from)
high (inc to)]
(let [guess (guess-between low high)]
(condp = (oracle guess)
:too-low (recur (inc attempts) guess high)
:too-high (recur (inc attempts) low guess)
:correct attempts)))))
For å bruke denne funksjonen manuelt i konsollet laget jeg en funksjon for å spørre brukeren om et tall var riktig gjettet, og en funksjon for å starte "spillet":
Kode
(defn manually-verify-answer [guess]
(print "Is it" guess
"(y:yes / l:too low / h:too high? ")
(flush)
(condp = (read)
'y :correct
'l :too-low
'h :too-high
(do
(println "Please reply with one of the letters"
"y, l, or h.")
(recur guess))))
Kode
(defn run-manually []
(println "Think of a number from 0 to 100.")
(println "I solved it with"
(solve 0 100 manually-verify-answer)
"guesses!"))
Jeg var deretter interessert i å finne ut hvor god løsningen var til å gjette. Jeg lagde en funksjon som opprettet automatiske verifiserings-funksjoner:
Kode
(defn make-oracle
"Yields an oracle function for any correct answer."
[correct-number]
(fn [guess]
(cond
(< guess correct-number) :too-low
(> guess correct-number) :too-high
(= guess correct-number) :correct)))
Så trengte jeg en liten average-funksjon:
Kode
(defn average [seq]
(/ (apply + seq)
(count seq)))
Og så til slutt en funksjon for å kjøre løsningen på en gitt range:
Kode
(defn run-complete [from to]
(println "Running solver for all numbers between"
from "and" to)
(->>
(range from (inc to))
(map #(solve from to (make-oracle %)))
average
float
(println "Average guesses to solve:")))
Fra 0 til 100 bruker funksjonen i snitt 5,8 forsøk.
Fra 0 til 1000 bruker funksjonen i snitt 8,988 forsøk.
Fra 0 til 10000 bruker funksjonen i snitt 12,36 forsøk.
Fra 0 til 100000 bruker funksjonen i snitt 15,7 forsøk.
Osv., osv. ...
Å finne snittet for en range fra 0 til én million tar på min maskin ca 1438 millisekunder med denne koden. Fra 0 til 10 mill tar det ca 17 sekunder.
DET SOM VAR LITT OVERRASKENDE kom resultatet jeg fikk da jeg forsøkte å parallellisere testen. Jeg har 8 kjerner på laptopen, og endret den siste funksjoner over fra å bruke
map til å bruke
pmap. Alle CPU'ene ble nå involvert i å teste de ulike tallene, men det ser ut til at koordineringen mellom trådene har et ganske stort overhead, for nå tok rangen fra 0 til 10 millioner hele 24 sekunder.
Er det noen som kan forklare hvorfor på en overbevisende måte? Burde det gå raskere om jeg manuelt delte opp rangen i 8, og kjørte 8 ulike tråder, for så til slutt å folde sammen resultatet?