Hello,
I have optimized the expansion of the macro whichever. In the current implementation, it generates n random values, creates O(n) functions and calls one of them. Using a sort of "inline" binary search, I was able to create an expansion which makes one call to RANDOM, O(log n) tests, and also does not create any extra function.
A test with my implementation:
cl-user> (macroexpand-1 '(whichever (list 1) (list 2) (list 3) (list 4) (list 5) (list 6) (list 7))) (let ((#:random-number854 (random 7))) (if (< #:random-number854 3) (if (< #:random-number854 1) (list 1) (if (< #:random-number854 2) (list 2) (list 3))) (if (< #:random-number854 5) (if (< #:random-number854 4) (list 4) (list 5)) (if (< #:random-number854 6) (list 6) (list 7))))) t
Regards, Gustavo Henrique Milaré.
Gustavo gugamilare@gmail.com writes:
Hello,I have optimized the expansion of the macro whichever.
Is there anything obviously wrong with my simpler implementation? http://article.gmane.org/gmane.lisp.alexandria.devel/213
Cheers,
Luis Oliveira luismbo@gmail.com writes:
Gustavo gugamilare@gmail.com writes:
Hello,I have optimized the expansion of the macro whichever.
Is there anything obviously wrong with my simpler implementation? http://article.gmane.org/gmane.lisp.alexandria.devel/213
This is roughly
(case (random n) (0 ...) ...)
Which has a decision as O(n) as SBCL and related compilers are too stupid to implement case efficiently as an indexed jump. It could easily be O(1). It would be on AllegroCL I believe.
The patch by Gustavo is O(log(n)), which is, given the current state of SBCL, much better. But it would require a very clever compiler to figure out how to transform it into an O(1) jump.
Note that the ncase trick where you jump into an array of lambdas would be an exceedingly bad idea in general, before anybody proposes it, as the case bodies could use local variables, so promoting a non-consing algorithm to a consing one.
Why didn't the original whichever just use case?
On 3 March 2010 16:27, Gustavo gugamilare@gmail.com wrote:
Thanks for the patch! Committed (in the Git repo.)
Cheers,
-- Nikodemus
alexandria-devel@common-lisp.net