Hjelp til løsing av algoritmeoppgaver.

[torbjørn marø]

En rekursiv beskrivelse av algoritmen blir ganske enkel (selv om den ikke gir den mest effektive implementasjonen):

For morroskyld (det er søndag) har jeg implementert tre varianter av algoritmen din i Clojure. Den første er så og si den samme som du hadde:

(defn sums [n]
 (if (<= n 4)
   (list n)
   (cons 3 (sums (- n 3)))))

 

Men i Clojure vil jeg få problemer med stacken på denne, fordi den ikke bruker halerekursjon. sums2 bruker derfor dette, og har derfor en overload som tar en accumulator-parameter. Jeg har også endret fra å bruke liste til å bruke vector (mere ideomatisk Clojure):

(defn sums2 
 ([n] (sums2 n []))
 ([n acc] 
   (if (<= n 4)
     (conj acc n)
     (recur (- n 3) (conj acc 3)))))

 

I sums3 har jeg flyttet overloaden inn i funksjonen (letfn er det samme som labels i Lisp mener jeg) - det er egentlig mere passende. Det er også mere optimalt skal det vise seg...

(defn sums3 [n]
 (letfn [(sums-internal [n acc]
            (if (<= n 4)
              (conj acc n)
              (recur (- n 3)
                     (conj acc 3))))]
    (sums-internal n [])))

 

Jeg tester funksjonene med et stort tall - men ikke så stort at det får den første til å "flyte over":

 

(time (sums 10000))
(time (sums2 10000))
(time (sums3 10000))

 

Og får da:

 

"Elapsed time: 3.038205 msecs"
"Elapsed time: 2.972946 msecs"
"Elapsed time: 1.4016 msecs"

Endret 23. oktober 2011 av torbjørn marø

[torbjørn marø]

Og så kom jeg på at jeg burde teste din implementasjon, bare med vector i stedet for liste, og da ble jeg overrasket!

 

(defn sums4 [n]
 (if (<= n 4)
   [n]
   (conj (sums (- n 3)) 3)))


(time (sums 5000))
(time (sums2 5000))
(time (sums3 5000))
(time (sums4 5000))

"Elapsed time: 2.008361 msecs"
"Elapsed time: 1.926604 msecs"
"Elapsed time: 0.853499 msecs"
"Elapsed time: 0.417951 msecs"

 

Halerekursjonen er altså betraktelig treigere enn din løsning om jeg bruker vector. Overrasket!

Endret 23. oktober 2011 av torbjørn marø

[asicman]

Lurer på om det virkelig finnes noen som synes Haskell er enklere å forstå enn Lisp?! Skjønner ikke at det er mulig..

 

Personlig foretrekker jeg Lisp. Men jeg har sett mange som bare klager på parenteser dersom man nevner Lisp. Tror jeg har postet denne tidligere, men...

 

[asicman]

Halerekursjonen er altså betraktelig treigere enn din løsning om jeg bruker vector. Overrasket!

 

Hmm det var rart. Kanskje det har noe med constraints pga. JVM? Er vektorer mer effektiv enn cons celler?

 

Må ta en test i SBCL.

 

Ellers har Common Lisp flet som er meget lik labels (bare scope av den lokale funksjonen som er forskjellig).

[asicman]

Endringer av elementer i array i Common Lisp er stort set gjort via side effekter. Så det å jeg har laget et par hjelpefunksjoner for å returnere vector etter at man has pushet på et element:

 

(declaim (optimize (speed 3) (safety 0) (debug 0)))

(defun sums (n)
 (if (<= n 4) (list n)
     (cons 3 (sums (- n 3)))))

(defun sums-t (n)
 (labels ((tail-sums (n acc)
            (if (<= n 4) (cons n acc)
                (tail-sums (- n 3) (cons 3 acc)))))
   (tail-sums n nil)))


(defun make-vector ()
 (make-array '(1000) :adjustable t :fill-pointer 0))

(defun vector-push-return (item vec)
 (vector-push-extend item vec)
 vec)

(defun sums-t-vec (n)
 (labels ((tail-sums-vec (n vec)
            (if (<= n 4) (vector-push-return n vec)
                (tail-sums-vec (- n 3) (vector-push-return 3 vec)))))
   (tail-sums-vec n (make-vector))))

Hvis jeg kjører benchmark så blir tiden stort sett 0 (siden jeg ikke har msec slik som deg), men jeg har antall cycles, selv om jeg ikke er helt sikker på hvordan SBCL beregner dette. Men relativ forskjell kan gi noen indikasjoner. Det ser ut som om det går litt tid til å allokere output (repl/SLIME) så jeg summerer alle tallene for at tiden utskriften tar ikke skal forstyrre resultatet og ikke fylle skjermen hele tiden.

 

CL-USER>  (time (loop for e in (sums 10000) sum e))
Evaluation took:
 0.000 seconds of real time
 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
 100.00% CPU
 226,220 processor cycles
 65,536 bytes consed

10000
CL-USER>  (time (loop for e in (sums-t 10000) sum e))
Evaluation took:
 0.000 seconds of real time
 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
 100.00% CPU
 128,703 processor cycles
 32,768 bytes consed

10000
CL-USER> (time (loop for e across (sums-t-vec 10000) sum e))
Evaluation took:
 0.000 seconds of real time
 0.000000 seconds of total run time (0.000000 user, 0.000000 system)
 100.00% CPU
 638,288 processor cycles
 34,400 bytes consed

10000

Så i SBCL så tar vector versjonen mye lenger tid. Men det er mulig at vector push ikke er så optimalt som bare å lage en lenket liste a av cons cell'er.

[torbjørn marø]

Halerekursjonen er altså betraktelig treigere enn din løsning om jeg bruker vector. Overrasket!

 

Hmm det var rart. Kanskje det har noe med constraints pga. JVM? Er vektorer mer effektiv enn cons celler?

Ja.., jeg kan ikke huske om jeg har sett det beskrevet svart på hvitt noe sted, men det ante meg at Clojure var raskere på vector enn lister. Det er ideomatisk Clojure å bruke vector på data fremfor lister - selv om sekvens-abstraksjonen ligger over og gjør at de stort sett kan behandles likt.

 

Men man bør huske på hva de er optimalisert for. Lister er generelt raske på operasjoner i front, mens vector er rask i enden for å si det sånn. Men i dette tilfellet skulle vel ikke det ha noe å si.

[torbjørn marø]

Lurer på om det virkelig finnes noen som synes Haskell er enklere å forstå enn Lisp?! Skjønner ikke at det er mulig..

Personlig foretrekker jeg Lisp. Men jeg har sett mange som bare klager på parenteser dersom man nevner Lisp.

Jada, de fleste henger seg opp i parantesene, men trodde ikke den typen utviklere syntes Haskell var noe lettere. Personlig føler jeg Haskell-kode er som Lisp hvor man har fjernet parantesene, og da blir det i alle fall vanskelig

[GeirGrusom]

Lurer på om det virkelig finnes noen som synes Haskell er enklere å forstå enn Lisp?! Skjønner ikke at det er mulig..

Personlig foretrekker jeg Lisp. Men jeg har sett mange som bare klager på parenteser dersom man nevner Lisp.

Jada, de fleste henger seg opp i parantesene, men trodde ikke den typen utviklere syntes Haskell var noe lettere. Personlig føler jeg Haskell-kode er som Lisp hvor man har fjernet parantesene, og da blir det i alle fall vanskelig

Jeg må si jeg foretrekker Haskell. Selv synes jeg parantesene gjør slik at en blir "tvunget" til å lese igjennom mye mer kode enn det som ofte er nødvendig. Det er sikkert en vanesak, men først og fremst liker jeg at det benyttes operator presedens fremfor at en bare tygger ut selve uttrykkstreet. Det tar mye kortere tid å lese matematiske uttrykk siden jeg har benyttet hele skolegangen min til å lese uttrykk på den måten.

[torbjørn marø]

Selv synes jeg parantesene gjør slik at en blir "tvunget" til å lese igjennom mye mer kode enn det som ofte er nødvendig. Det er sikkert en vanesak, men først og fremst liker jeg at det benyttes operator presedens fremfor at en bare tygger ut selve uttrykkstreet. Det tar mye kortere tid å lese matematiske uttrykk siden jeg har benyttet hele skolegangen min til å lese uttrykk på den måten.

Jeg kjøper den. Selv om jeg har opparbeidet meg endel Lisp-erfaring nå synes jeg fortsatt ofte det er vanskelig å lese koden. Selv kode jeg syntes var enkel å grei å skrive for en måned siden kan bli litt kryptisk når jeg leser den nå. Sånn er det jo ofte i alle språk, men man kan finne på så mye rart i Lisp

 

Men kraften/fleksibiliteten Lisp-syntaksen gir deg må ikke undervurderes.

Endret 24. oktober 2011 av torbjørn marø

[GeirGrusom]

Men kraften/fleksibiliteten Lisp-syntaksen gir deg må ikke undervurderes.

Kan ikke benektes.

[snippsat]

Ser ikke ut som noen har nevnt navnet på algoritmen Partition(integer partition)

Også en del bøker om temaet Generating Partitions

Skulle ikke forundere meg om at Donald Knuth har skrevet noe smart om dette i bind 3(som jeg ikke har lest)

Har sett på en del løsninger da i python,men har ikke fått tid til og studere dette så nøye at jeg poster noe kode.

Endret 25. oktober 2011 av SNIPPSAT

[asicman]

Ser ikke ut som noen har nevnt navnet på algoritmen Partition(integer partition)

 

Det er ikke denne algoritmen som heter partitions. Paritions er å dele opp tall i summer av andre tall. Algoritmen går ut på å finne en partisjon slik at produktet av alle tallene i partisjonen er høyest.

 

Dersom man ikke begrenser seg til heltall ser dette ut til å bli e, f.eks. e^(2001/e). At det blir 3 og noen ganger 2,2 har nok med at snittet blir mest likt e uten at jeg har sett noe bevis på det.

 

Skulle ikke forundere meg om at Donald Knuth har skrevet noe smart om dette i bind 3(som jeg ikke har lest)

Har sett på en del løsninger da i python,men har ikke fått tid til og studere dette så nøye at jeg poster noe kode.

 

Du mener nok bind 4. Bind 3 er om sortering og søk. Jeg har heller ikke lest bind 4. Har bare 1-3.

 

Artig hvis du poster Python kode med løsninger.

[asicman]

Jeg må si jeg foretrekker Haskell. Selv synes jeg parantesene gjør slik at en blir "tvunget" til å lese igjennom mye mer kode enn det som ofte er nødvendig.

 

Det er ikke alltid man slipper parenteser i Haskell. Enkelte ganger kan det være litt irriterende. I Python osv. kan man skrive

 

>>> 2 * 3
6
>>> 2 * -3
-6

 

I Haskell:

 

Prelude> 2 * 3
6
Prelude> 2 * -3

<interactive>:1:0:
   Precedence parsing error
       cannot mix `*' [infixl 7] and prefix `-' [infixl 6] in the same infix expression
Prelude> 2 * (-3)
-6

 

I Lisp skriver man:

 

CL-USER> (* 3 -1/3)
-1

 

 

Lisp har jo nesten ingen syntax, det er bare (funksjon args...). Men funksjonene kan hete +,-, osv. Enkelte utrykk (eller retter sagt funksjonskall) kan bli enkere i prefix notasjon

 

CL-USER> (+ 1 2 3 4 5 6 7 8 9 10)
55
CL-USER> (< 1 2 3 4 5 6 7 8 9 10)
T

 

If er ikke syntax, men en funksjon som sjekker om det første argumentet er forskjellig fra nil og returnerer det andre eller tredje argumentet. Man kan da skrive ting som

 

CL-USER> (+ 3 4 (if (oddp (random 10)) 993 -7))
0
CL-USER> (+ 3 4 (if (oddp (random 10)) 993 -7))
1000

 

Det som også er elegant er at det ikke er forskjell på kode og data, noe som er veldig nyttig når man begynner å skrive macro'er. Det er da man ser lyset