[alexandria-devel] Optimization for whichever
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, -- Luís Oliveira http://student.dei.uc.pt/~lmoliv/
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
participants (4)
-
Gustavo -
John Fremlin -
Luis Oliveira -
Nikodemus Siivola