gmane.comp.lang.factor.general

What is a good definition ?

Hi,

I needed to get the list of all combinaisons of n elements chosen in  
a sequence.

Quite simple in fact but disturbing for a beginner.

First problem, how to know if there is already a word doing this in  
factor?
RTFM =>  I read "Sequence operations" several times.
Documentation is very nice and interesting to read but it's sometime  
difficult for me to find a word doing what I want.
(Or there are too many words doing quite the same, I don't know)
Nevertheless reading definitions often give new ideas  on how to  
solve problems.

Second problem, maybe the needed word is undocumented somewhere in  
the extra directory.
In that case it's maybe simpler to rewrite than to try to find it.

With doc freshly reminded I wrote without too many difficulties the  
next two definitions  (lean back and think)

: columnize ( seq -- seq )
     [ 1array ] map
; inline

: among ( seq n -- seq )
     2dup swap length
     {

(Continue reading)

headers

Eric Mertens | 24 Apr 00:25

Re: What is a good definition ?

On Wed, Apr 23, 2008 at 2:17 PM, Jean-François Bigot
<jeff.bigot@...> wrote:
> Hi,
>
>  I needed to get the list of all combinaisons of n elements chosen in
>  a sequence.

Does this do what you needed?

: combos ( seq -- seqs )
    dup empty? [ drop { { } } ]
    [
        unclip
        [ combos dup ]
        [ [ prefix ] curry map append ] bi*
    ] if ;

( scratchpad ) { 1 2 3 } combos .
{ { } { 3 } { 2 } { 2 3 } { 1 } { 1 3 } { 1 2 } { 1 2 3 } }

--

-- 
Eric Mertens

-------------------------------------------------------------------------
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

headers

Jean-François Bigot | 25 Apr 23:15

Re: What is a good definition ?

Hi,

Eric nicely gave me his solution :

DEFER: combinations

: (combinations) [ 1 tail ] dip combinations ;

: prefix-each [ prefix ] curry map ;

: combinations ( seq n -- seqs )

  {

  { [ dup 0 = ] [ 2drop { { } } ] }

  { [ over empty? ] [ 2drop { } ] }

  { [ t ] [

  [ [ 1- (combinations) ] [ drop first ] 2bi prefix-each ]

  [ (combinations) ] 2bi append

  ] }

  } cond ;

It looks nice :

- only three conditions,

- very few shuffle words

- a good name

- prefix-each makes sens

OK lets try

[ 20 20 <array> 20 [ among ] with each ] time

=> "end > sequence" error

I missed something (Eric didn't !)

I add a condition to my def that becomes

: columnize ( seq -- seq )

[ 1array ] map

; inline

: among ( seq n -- seqs )

2dup swap length

{

{ [ over 1 = ] [ 3drop columnize ] }

{ [ over 0 = ] [ 2drop 2drop { } ] }

{ [ 2dup < ] [ 2drop [ 1 cut ] dip

[ 1- among [ append ] with map ]

[ among append ] 2bi

] }

{ [ 2dup = ] [ 3drop 1array ] }

{ [ 2dup > ] [ 2drop 2drop { } ] }

} cond

;

so again

[ 20 20 <array> 20 [ among ] with each ] time

=> 8953 ms run / 4142 ms GC time

and after

[ 20 20 <array> 20 [ combinations ] with each ] time

=> 20500 ms run / 6359 ms GC time

I tried several times to be sure !

for "10 10 <array> 10" results are equals to 16 ms but for "large number" Eric's nice word is twice slower than mine.

WHY ?

Are there rules to optimise a word ?

On what point must we focus to build efficient code ?

-------------------------------------------------------------------------
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
Factor-talk@...
https://lists.sourceforge.net/lists/listinfo/factor-talk

headers

Justin DeVries | 26 Apr 00:45

Re: What is a good definition ?

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 <at> (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
Factor-talk@...
https://lists.sourceforge.net/lists/listinfo/factor-talk