Hi,
Your code is faster because it short-cuts sooner when you know the
result of an operation. Because of your condition,
{ [ 2dup = ] [ 3drop 1array ] }
your code can jump to the conclusion that { 1 2 3 } 3 among is { { 1 2
3 } }, whereas Eric's word must compute the combinations of { 2 3 }
and prefix each of those with 1. But to do that it must compute the
combinations of { 3 } and prefix those with 2, etc. You could add such
a condition to Eric's word and you should see a speed improvement.
Another possibility to give speed is to use a memoization:
: prefix-each [ prefix ] curry map ;
MEMO: (combos) ( m n -- seqs )
! m options, choose n things
{
{ [ dup 0 = ] [ 2drop { { } } ] }
{ [ over empty? ] [ 2drop { } ] }
{ [ t ]
[ [ [ [ 1- ] bi@ (combos) ] [ drop 1- ] 2bi prefix-each ]
[ [ 1- ] dip (combos) ] 2bi append ] }
} cond ;
: combos ( seq n -- seqs )
over length swap (combos)
swap [ [ nth ] curry map ] curry map ;
This is basically Eric's solution, but we do all the computations with
the generic sequence { 0 1 2 ... n-1 }, which Factor sees as the
number n. Since all computations are done on these generic sequences
we can memoize, then map over the generic results to put the correct
sequence items in.
On a first run:
[ 20 20 <array> 20 [ combos ] with each ] time
=> 6764 ms run / 4834 ms GC time
But memoizing kicks in on the second run:
[ 20 20 <array> 20 [ combos ] with each ] time
=> 2381 ms run / 1200 ms GC time
For comparison, here are the times for the other solutions on my
machine:
[ 20 20 <array> 20 [ among ] with each ] time
=> 10416 ms run / 7555 ms GC time
[ 20 20 <array> 20 [ combinations ] with each ] time
=> 24471 ms run / 14297 ms GC time
Cheers,
Justin
-------------------------------------------------------------------------
This SF.net email is sponsored by the 2008 JavaOne(SM) Conference
Don't miss this year's exciting event. There's still time to save $100.
Use priority code J8TL2D2.
http://ad.doubleclick.net/clk;198757673;13503038;p?http://java.sun.com/javaone
_______________________________________________
Factor-talk mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/factor-talk
