I have updated the sample source from the book (http://tinyurl.com/clojure-samples ) to the new laziness. Along the way, I replaced the lazy-cons based implementation of the fibonacci numbers with this:
(defn fibo ([] (concat [0 1] (fibo 0 1))) ([a b] (let [n (+ a b)] (lazy-seq (cons n (fibo b n))))))
Is there a better/more idiomatic approach, without resorting to code in clojure-contrib? Test your code against the following expression to flush out stack and heap overflows.
(rem (nth (fibo) 1000000) 1000) -> 875
Also, the current 'fibs' implementation in clojure.contrib.seq fails the test above, because it holds the entire sequence as it goes. We should replace it with whatever the community comes up with on this thread.
> I have updated the sample source from the book (http://tinyurl.com/clojure-samples > ) to the new laziness. Along the way, I replaced the lazy-cons based
> implementation of the fibonacci numbers with this:
> (defn fibo
> ([]
> (concat [0 1] (fibo 0 1)))
> ([a b]
> (let [n (+ a b)]
> (lazy-seq
> (cons n (fibo b n))))))
> Is there a better/more idiomatic approach, without resorting to code
> in clojure-contrib? Test your code against the following expression to
> flush out stack and heap overflows.
> (rem (nth (fibo) 1000000) 1000)
> -> 875
> Also, the current 'fibs' implementation in clojure.contrib.seq fails
> the test above, because it holds the entire sequence as it goes. We
> should replace it with whatever the community comes up with on this
> thread.
On Feb 23, 2009, at 11:43 AM, Stuart Halloway wrote:
> Also, the current 'fibs' implementation in clojure.contrib.seq fails > the test above, because it holds the entire sequence as it goes. We > should replace it with whatever the community comes up with on this > thread.
The fibs implementation in clojure.contrib.lazy-seqs is not a function that returns fib(n) given n. Instead, it is an infinite sequence of all the fibonacci numbers. It holds onto its head because it's intended to. It's surely not the right way to deal with fibonacci numbers in every context, but I don't think it needs replacing because it requires a large java heap to pass this test:
As the sequence is very cheap to calculate it is difficult to see the
benefit of keeping it in memory under any circumstances. I would
replace the one in contrib with Christophe's short, easy to understand
implementation. Caching values isn't getting you anywhere; just
wasting resources.
Chris
On Feb 23, 12:51 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> On Feb 23, 2009, at 11:43 AM, Stuart Halloway wrote:
> > Also, the current 'fibs' implementation in clojure.contrib.seq fails
> > the test above, because it holds the entire sequence as it goes. We
> > should replace it with whatever the community comes up with on this
> > thread.
> The fibs implementation in clojure.contrib.lazy-seqs is not a function
> that returns fib(n) given n. Instead, it is an infinite sequence of
> all the fibonacci numbers. It holds onto its head because it's
> intended to. It's surely not the right way to deal with fibonacci
> numbers in every context, but I don't think it needs replacing because
> it requires a large java heap to pass this test:
> Using a good old sequence of vectors:
> (defn fibo []
> (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
> Christophe
> Stuart Halloway a écrit :
>> I have updated the sample source from the book (http://tinyurl.com/clojure-samples >> ) to the new laziness. Along the way, I replaced the lazy-cons based
>> implementation of the fibonacci numbers with this:
>> (defn fibo
>> ([]
>> (concat [0 1] (fibo 0 1)))
>> ([a b]
>> (let [n (+ a b)]
>> (lazy-seq
>> (cons n (fibo b n))))))
>> Is there a better/more idiomatic approach, without resorting to code
>> in clojure-contrib? Test your code against the following expression
>> to
>> flush out stack and heap overflows.
>> (rem (nth (fibo) 1000000) 1000)
>> -> 875
>> Also, the current 'fibs' implementation in clojure.contrib.seq fails
>> the test above, because it holds the entire sequence as it goes. We
>> should replace it with whatever the community comes up with on this
>> thread.
On Feb 23, 2:51 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> The fibs implementation in clojure.contrib.lazy-seqs is not a function
> that returns fib(n) given n.
> I think defining a fib(n) function somewhere in contrib or core that
> operates as efficiently as we can manage would be a good idea.
There was a thread on comp.lang.lisp a while ago where a number of
people went back and forth trying to come up withe the fastest fib(n)
algorithm (again, *not* returning a sequence, but just the nth fib
given n). Here is the winner of that informal competition translated
to clojure:
(defn fib
([n]
(fib n 1))
([n b]
(if (zero? b) ;calculate lucas numbers
(cond
(zero? n) 2
(= n 1) 1
:otherwise
(if (even? n)
(let [ k (/ n 2)
l (fib k 0)]
(+ (* l l) (if (even? k) -2 2)))
(let [ k (- n 1)
l (fib k 0)
f (fib k 1)]
(/ (+ (* 5 f) l) 2))))
(cond ;calculate fibonacci numbers
(zero? n) 0
(= n 1) 1
:otherwise
(if (even? n)
(let [ k (/ n 2)
l (fib k 0)
f (fib k 1)]
(* f l))
(let [ k (- n 1)
l (fib k 0)
f (fib k 1)]
(/ (+ f l) 2)))))))
takes over 85 seconds, or more than 40 times as long as the lucas
number based algorithm at top to compute the one millionth fibonacci
number. The simple loop version:
(defn fib-naive2 [n]
(loop [a 0 b 1 counter 0]
(if (= counter n) a
(recur b (+ a b) (inc counter)))))
fares exactly the same as one might expect.
for comparison, here are some timings under different lisps on the
same machine. All timings are after several runs to warm up caches
and, in the case of clojure, hotspot optimizations.
Time to calculate the one millionth fibonacci number using the lucas
number based algorithm at top:
as you can see, clojure is competitive with other lisps/schemes,
faster than some, slower than others. this is really just a benchmark
of the bignum package used by the lisp implementation. I think ecl
uses GMP which is quite fast.
btw, I tried adding type annotations to the clojure version but it
didn't seem to make much difference.
> On Feb 23, 2:51 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> > The fibs implementation in clojure.contrib.lazy-seqs is not a function
> > that returns fib(n) given n.
> > I think defining a fib(n) function somewhere in contrib or core that
> > operates as efficiently as we can manage would be a good idea.
> There was a thread on comp.lang.lisp a while ago where a number of
> people went back and forth trying to come up withe the fastest fib(n)
> algorithm (again, *not* returning a sequence, but just the nth fib
> given n). Here is the winner of that informal competition translated
> to clojure:
> (defn fib
> ([n]
> (fib n 1))
> ([n b]
> (if (zero? b) ;calculate lucas numbers
> (cond
> (zero? n) 2
> (= n 1) 1
> :otherwise
> (if (even? n)
> (let [ k (/ n 2)
> l (fib k 0)]
> (+ (* l l) (if (even? k) -2 2)))
> (let [ k (- n 1)
> l (fib k 0)
> f (fib k 1)]
> (/ (+ (* 5 f) l) 2))))
> (cond ;calculate fibonacci numbers
> (zero? n) 0
> (= n 1) 1
> :otherwise
> (if (even? n)
> (let [ k (/ n 2)
> l (fib k 0)
> f (fib k 1)]
> (* f l))
> (let [ k (- n 1)
> l (fib k 0)
> f (fib k 1)]
> (/ (+ f l) 2)))))))
> takes over 85 seconds, or more than 40 times as long as the lucas
> number based algorithm at top to compute the one millionth fibonacci
> number. The simple loop version:
> (defn fib-naive2 [n]
> (loop [a 0 b 1 counter 0]
> (if (= counter n) a
> (recur b (+ a b) (inc counter)))))
> fares exactly the same as one might expect.
> for comparison, here are some timings under different lisps on the
> same machine. All timings are after several runs to warm up caches
> and, in the case of clojure, hotspot optimizations.
> Time to calculate the one millionth fibonacci number using the lucas
> number based algorithm at top:
> as you can see, clojure is competitive with other lisps/schemes,
> faster than some, slower than others. this is really just a benchmark
> of the bignum package used by the lisp implementation. I think ecl
> uses GMP which is quite fast.
> btw, I tried adding type annotations to the clojure version but it
> didn't seem to make much difference.
On Feb 23, 9:31 pm, Jeffrey Straszheim <straszheimjeff...@gmail.com>
wrote:
> The speed of the JVM's big ints, and therefore Clojure's, doesn't seem to be
> competitive.
Clearly the JVM's big ints doesn't compare favorably with GMP. On the
other hand, Clojure falls near the middle of the range of the various
lisps and schemes. It's about as fast as LispWorks 32-bit for example.
> On Feb 23, 9:31 pm, Jeffrey Straszheim <straszheimjeff...@gmail.com> > wrote: >> The speed of the JVM's big ints, and therefore Clojure's, doesn't seem to be >> competitive.
> Clearly the JVM's big ints doesn't compare favorably with GMP. On the > other hand, Clojure falls near the middle of the range of the various > lisps and schemes. It's about as fast as LispWorks 32-bit for example.
Too bad GMP is LGPLv3+, while Java is GPLv2 only, so we'll not see Java using GMP in the foreseeable foture. Kaffe's JVM uses GMP, though. If Clojure runs on it, it'd be interesting to see what sort of numbers it produces.
I've not seen a decent GMP wrapper for Java -- does anyone know of any such implementation?
Hello,
What about giving back 'lazy-cons (or lcons as a shortcut), with the
optional possibility to give the cons an internal name ?
This could allow for self-recursive definition, such as this one for a
fibonacci generator function as :
I wanted to try a definition closer to the one I had in my Haskell book.
This definition needs the ability for the lazy-seq to reference itself.
For example, it can in straight clojure be written as :
But of course, the above version, while interesting, leaks memory since the
lazy seq is bound to a global var.
So I've played with clojure core to allow the creation of lazy-sequences
that can refer to themselves inside their body, and get rid of the memory
leak problem.
I've called this 'named-lazy-seq : (named-lazy-seq [a-name] ... )
And since the pattern (lazy-seq (cons ...)) may well be a common one, I've
also recreated 'lazy-cons (or lcons for brevity) that is just a macro
calling either 'lazy-seq or 'named-lazy-seq depending on its arity :
> Beautiful-thanks.
> - Afficher le texte des messages précédents -
> > Using a good old sequence of vectors:
> > (defn fibo []
> > (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))
> > Christophe
> > Stuart Halloway a écrit :
> >> I have updated the sample source from the book (
> http://tinyurl.com/clojure-samples > >> ) to the new laziness. Along the way, I replaced the lazy-cons based
> >> implementation of the fibonacci numbers with this:
> >> Is there a better/more idiomatic approach, without resorting to code
> >> in clojure-contrib? Test your code against the following expression
> >> to
> >> flush out stack and heap overflows.
> >> (rem (nth (fibo) 1000000) 1000)
> >> -> 875
> >> Also, the current 'fibs' implementation in clojure.contrib.seq fails
> >> the test above, because it holds the entire sequence as it goes. We
> >> should replace it with whatever the community comes up with on this
> >> thread.
> Hello, > What about giving back 'lazy-cons (or lcons as a shortcut), with the > optional possibility to give the cons an internal name ?
It would work and that's why Stuart said "without resorting to code in clojure-contrib": (defn fibo[] (seq-utils/rec-cat fib [0 1] (map + fib (rest fib))))
(Btw, Stuart, due to latest changes in Clojure's lazy-seq implementation, rec-seq is atom-based again.)
2009/2/24 Christophe Grand <christo...@cgrand.net>
> Laurent PETIT a écrit :
> > Hello,
> > What about giving back 'lazy-cons (or lcons as a shortcut), with the
> > optional possibility to give the cons an internal name ?
> It would work and that's why Stuart said "without resorting to code in
> clojure-contrib":
> (defn fibo[]
> (seq-utils/rec-cat fib [0 1] (map + fib (rest fib))))
Wow, I think now is time for me to also try to learn more the stuff that is
in clojure-contrib !
Anyway, it was interesting to try doing it by tweaking clojure itself :-)
Could'nt it be interesting to consider adding the possibility to make self
recursive calls inherent to lazy-seqs, as I proposed ?
It's a one line change in a clojure class, and a one line change in lazy-seq
also.
And I don't think it would have performance impacts for people not willing
to use that.
> 2009/2/24 Christophe Grand <christo...@cgrand.net > <mailto:christo...@cgrand.net>>
> Laurent PETIT a écrit : > > Hello, > > What about giving back 'lazy-cons (or lcons as a shortcut), with the > > optional possibility to give the cons an internal name ? > It would work and that's why Stuart said "without resorting to code in > clojure-contrib": > (defn fibo[] > (seq-utils/rec-cat fib [0 1] (map + fib (rest fib))))
> Wow, I think now is time for me to also try to learn more the stuff > that is in clojure-contrib !
> Anyway, it was interesting to try doing it by tweaking clojure itself :-)
Prior to r1300 it was even easier: no change to Clojure was required.
> Could'nt it be interesting to consider adding the possibility to make > self recursive calls inherent to lazy-seqs, as I proposed ?
While having played a lot with rec-cons, rec-cat and rec-seq — which can prove useful in simplifying some code —, I'm still ambivalent about the general case of recursive data structures in functional programming that's why I'm not lobbying for their inclusion in core.
> On Feb 23, 2:51 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> > The fibs implementation in clojure.contrib.lazy-seqs is not a function
> > that returns fib(n) given n.
> > I think defining a fib(n) function somewhere in contrib or core that
> > operates as efficiently as we can manage would be a good idea.
> There was a thread on comp.lang.lisp a while ago where a number of
> people went back and forth trying to come up withe the fastest fib(n)
> algorithm (again, *not* returning a sequence, but just the nth fib
> given n). Here is the winner of that informal competition translated
> to clojure:
> (defn fib
> ([n]
> (fib n 1))
> ([n b]
> (if (zero? b) ;calculate lucas numbers
> (cond
> (zero? n) 2
> (= n 1) 1
> :otherwise
> (if (even? n)
> (let [ k (/ n 2)
> l (fib k 0)]
> (+ (* l l) (if (even? k) -2 2)))
> (let [ k (- n 1)
> l (fib k 0)
> f (fib k 1)]
> (/ (+ (* 5 f) l) 2))))
> (cond ;calculate fibonacci numbers
> (zero? n) 0
> (= n 1) 1
> :otherwise
> (if (even? n)
> (let [ k (/ n 2)
> l (fib k 0)
> f (fib k 1)]
> (* f l))
> (let [ k (- n 1)
> l (fib k 0)
> f (fib k 1)]
> (/ (+ f l) 2)))))))
> takes over 85 seconds, or more than 40 times as long as the lucas
> number based algorithm at top to compute the one millionth fibonacci
> number. The simple loop version:
> (defn fib-naive2 [n]
> (loop [a 0 b 1 counter 0]
> (if (= counter n) a
> (recur b (+ a b) (inc counter)))))
> fares exactly the same as one might expect.
> for comparison, here are some timings under different lisps on the
> same machine. All timings are after several runs to warm up caches
> and, in the case of clojure, hotspot optimizations.
> Time to calculate the one millionth fibonacci number using the lucas
> number based algorithm at top:
> as you can see, clojure is competitive with other lisps/schemes,
> faster than some, slower than others. this is really just a benchmark
> of the bignum package used by the lisp implementation. I think ecl
> uses GMP which is quite fast.
> btw, I tried adding type annotations to the clojure version but it
> didn't seem to make much difference.
> On Feb 23, 2:51 pm, "Stephen C. Gilardi" <squee...@mac.com> wrote:
> > The fibs implementation in clojure.contrib.lazy-seqs is not a function
> > that returns fib(n) given n.
> > I think defining a fib(n) function somewhere in contrib or core that
> > operates as efficiently as we can manage would be a good idea.
> There was a thread on comp.lang.lisp a while ago where a number of
> people went back and forth trying to come up withe the fastest fib(n)
> algorithm (again, *not* returning a sequence, but just the nth fib
> given n). Here is the winner of that informal competition translated
> to clojure:
> (defn fib
> ([n]
> (fib n 1))
> ([n b]
> (if (zero? b) ;calculate lucas numbers
> (cond
> (zero? n) 2
> (= n 1) 1
> :otherwise
> (if (even? n)
> (let [ k (/ n 2)
> l (fib k 0)]
> (+ (* l l) (if (even? k) -2 2)))
> (let [ k (- n 1)
> l (fib k 0)
> f (fib k 1)]
> (/ (+ (* 5 f) l) 2))))
> (cond ;calculate fibonacci numbers
> (zero? n) 0
> (= n 1) 1
> :otherwise
> (if (even? n)
> (let [ k (/ n 2)
> l (fib k 0)
> f (fib k 1)]
> (* f l))
> (let [ k (- n 1)
> l (fib k 0)
> f (fib k 1)]
> (/ (+ f l) 2)))))))
> takes over 85 seconds, or more than 40 times as long as the lucas
> number based algorithm at top to compute the one millionth fibonacci
> number. The simple loop version:
> (defn fib-naive2 [n]
> (loop [a 0 b 1 counter 0]
> (if (= counter n) a
> (recur b (+ a b) (inc counter)))))
> fares exactly the same as one might expect.
> for comparison, here are some timings under different lisps on the
> same machine. All timings are after several runs to warm up caches
> and, in the case of clojure, hotspot optimizations.
> Time to calculate the one millionth fibonacci number using the lucas
> number based algorithm at top:
> as you can see, clojure is competitive with other lisps/schemes,
> faster than some, slower than others. this is really just a benchmark
> of the bignum package used by the lisp implementation. I think ecl
> uses GMP which is quite fast.
> btw, I tried adding type annotations to the clojure version but it
> didn't seem to make much difference.
On Feb 24, 1:18 pm, Luke VanderHart <luke.vanderh...@gmail.com> wrote:
> Just out of curiosity - did you by any chance "warm up" the JVM to
> make sure that the fib function was JIT'd before you did this
> benchmark?
> On Feb 23, 5:46 pm, Raffael Cavallaro <raffaelcavall...@gmail.com>
> wrote:
> > for comparison, here are some timings under different lisps on the
> > same machine. All timings are after several runs to warm up caches
> > and, in the case of clojure, hotspot optimizations.
