Ideally it could be both elegant and fast.
Part of the reason the make version is faster is likely due to the use of
an accumulator that avoids creation of intermediate arrays (e.g., "map
concat" creates a first array ("map") then creates a second array to hold
all the values when flattening the first array ("concat").
I think trying the simplest construct that solves the problem is a good
first approach (thus the "cartesian-product cartesian-product"), but if you
want more speed, you could create an accumulator and do it all in one loop:
: 2cartesian-map ( ... seq1 seq2 seq3 quot: ( ... elt1 elt2 elt3 -- ...
newelt ) -- ... newseq )
V{ } clone [
[ push ] curry compose [
[ with with each ] 2curry with each
] 3curry each
] keep ; inline
: 2cartesian-product ( ... seq1 seq2 seq3 -- ... newseq )
[ { } 3sequence ] 2cartesian-map ;
This is much faster on a simple benchmark:
! your version
Running time: 2.062021414 seconds
! this new version
Running time: 1.218346195 seconds
It could even be faster if you preallocate the vector knowing that the
output will be "len(seq1) * len(seq2) * len(seq3)" in size. Also, as an
API, you might consider returning an array, which is particularly nice if
the vector size is preallocated because "{ } like" is a fast operation in
that case (no resizing of the underlying array necessary).
If you'd like to make contributions, we'd welcome them. Generally we are
flexible about putting things in $factor/extra/, it should have some tests,
but we are flexible on style and performance. It's a nice way to
experiment with new ideas or iterate on solutions before we add them to the
more "standard library" in basis/ or core/.
Best,
John.
On Mon, Apr 1, 2013 at 1:43 PM, Loryn Jenkins <lor...@gmail.com> wrote:
> And by "why is the ugly code faster", what I mean to ask is: If the code
> were submitted for inclusion into the Factor libraries:
> A. Would the elegant code by chosen over the ugly code, regardless of
> performance?
> B. Would the evaluator want to optimise the elegant code before approving
> it?
>
> What's the culture of elegance vs performance? (Saith I: Given that I
> notice both the extreme level of abstraction and elegance of the existing
> code base! :-) )
>
> Loryn Jenkins
>
>
> On Tue, Apr 2, 2013 at 7:33 AM, Loryn Jenkins <lor...@gmail.com> wrote:
>
>> Hmm, thanks. I must've been tired!
>>
>> Firstly, John: How did you perceive such an elegant solution? Is this
>> simply "experience", or were you looking at the problem in a certain light?
>>
>> Secondly, why is it the drop-dead ugly version outperforms the elegant
>> version by so much (~ 2.7 times).
>>
>> Relative timings:
>> gc [ 100,000 [ { 1 2 3 4 5 6 7 8 9 10 } dup dup 2cartesian-product drop
>> ] times ] time
>> -->32.070791587
>>
>> gc [ 100,000 [ { 1 2 3 4 5 6 7 8 9 10 } dup dup 2-cartesian-product drop
>> ] times ] time
>> --> 11.547108682
>>
>> : 2cartesian-product ( seq1 seq2 seq3 -- newseq )
>> cartesian-product cartesian-product concat
>> [ first2 swap '[ _ prefix ] map ] map concat ;
>>
>> : 2-cartesian-product ( seq1 seq2 seq3 -- newseq )
>> cartesian-product cartesian-product concat
>> [ [ first2 first2 [ >vector ] bi@ [ over ] dip swap prefix [ swap
>> prefix ] dip swap , , ] each
>> ] V{ } make ;
>>
>> Loryn Jenkins
>>
>>
>> On Tue, Apr 2, 2013 at 1:27 AM, John Benediktsson <mrj...@gmail.com>wrote:
>>
>>> Just call "concat" again;
>>>
>>> : 2cartesian-product ( seq1 seq2 seq3 -- newseq )
>>> cartesian-product cartesian-product concat
>>> [ first2 swap '[ _ prefix ] map ] map concat ;
>>>
>>>
>>> IN: scratchpad { 1 2 } { 3 4 } { 5 6 } 2cartesian-product .
>>> {
>>> { 1 3 5 }
>>> { 1 3 6 }
>>> { 1 4 5 }
>>> { 1 4 6 }
>>> { 2 3 5 }
>>> { 2 3 6 }
>>> { 2 4 5 }
>>> { 2 4 6 }
>>> }
>>>
>>>
>>>
>>>
>>>
>>> On Mon, Apr 1, 2013 at 7:25 AM, Loryn Jenkins <lor...@gmail.com> wrote:
>>>
>>>> Thank you!
>>>>
>>>> That's certainly cleaner.
>>>>
>>>> Just needed to flatten the output. I think I've seen a single word
>>>> that'll do that for me, but I can't remember what it is just now. unzip and
>>>> union will have to do for this morning.
>>>>
>>>> Thanks for your help both, Rupert and John.
>>>>
>>>> USING: USING: kernel sequences vectors assocs sets
>>>>
>>>> : 2cartesian-product ( seq1 seq2 seq3 -- newseq )
>>>> cartesian-product cartesian-product concat
>>>> [ first2 swap '[ _ prefix ] map ] map unzip union ;
>>>>
>>>>
>>>> Good night!
>>>>
>>>>
>>>> On Tue, Apr 2, 2013 at 1:07 AM, John Benediktsson <mrj...@gmail.com>wrote:
>>>>
>>>>> Or, alternatively doing the concat first:
>>>>>
>>>>> : 2cartesian-product ( seq1 seq2 seq3 -- newseq )
>>>>> cartesian-product cartesian-product concat
>>>>> [ first2 swap '[ _ prefix ] map ] map ;
>>>>>
>>>>>
>>>>>
>>>>> On Mon, Apr 1, 2013 at 7:06 AM, John Benediktsson <mrj...@gmail.com>wrote:
>>>>>
>>>>>> Instead of using make, you can do this which looks cleaner:
>>>>>>
>>>>>> : 2cartesian-product ( seq1 seq2 seq3 -- newseq )
>>>>>> cartesian-product cartesian-product [
>>>>>> [ first2 swap '[ _ prefix ] map ] map
>>>>>> ] map concat ;
>>>>>>
>>>>>>
>>>>>>
>>>>>> On Mon, Apr 1, 2013 at 6:59 AM, Loryn Jenkins <lor...@gmail.com>wrote:
>>>>>>
>>>>>>> Thanks, Rupert.
>>>>>>>
>>>>>>> I followed your suggestion, and managed to get it working. :-)
>>>>>>>
>>>>>>> USING: kernel sequences vectors make
>>>>>>>
>>>>>>> : 2-cartesian-product ( seq1 seq2 seq3 -- newseq )
>>>>>>> cartesian-product cartesian-product concat
>>>>>>> [ [ first2 first2 [ >vector ] bi@ [ over ] dip swap prefix [
>>>>>>> swap prefix ] dip swap , , ] each
>>>>>>> ] V{ } make ;
>>>>>>>
>>>>>>> Loryn Jenkins
>>>>>>>
>>>>>>>
>>>>>>> On Mon, Apr 1, 2013 at 11:17 PM, Rupert Swarbrick <
>>>>>>> rswarbr...@gmail.com> wrote:
>>>>>>>
>>>>>>>> Loryn Jenkins <lor...@gmail.com> writes:
>>>>>>>> > Hi
>>>>>>>> >
>>>>>>>> > I'm attempting to adapt the code for cartesian-product into
>>>>>>>> > 2cartesian-product, in order to produce the cartesian product of 3
>>>>>>>> > sequences.
>>>>>>>>
>>>>>>>> I'm afraid I haven't got time to properly look at your code, but
>>>>>>>> don't
>>>>>>>> forget that the cartesian product is associative. That is:
>>>>>>>>
>>>>>>>> (A × B) × C = A × (B × C)
>>>>>>>>
>>>>>>>> and either of these two makes sense for the cartesian product of
>>>>>>>> three
>>>>>>>> sets. In your case, this means that
>>>>>>>>
>>>>>>>> { 1 2 } { 3 4 } { 5 6 } cartesian-product cartesian-product
>>>>>>>>
>>>>>>>> will almost do what you want (it's the right hand side of the
>>>>>>>> equation
>>>>>>>> above). But the nesting won't be quite right, since you'll have
>>>>>>>> elements
>>>>>>>> that look like { 1 { 3 5 } }, so you can fix that with something
>>>>>>>> like
>>>>>>>>
>>>>>>>> [ first2 first2 ] map
>>>>>>>>
>>>>>>>> I think (untested).
>>>>>>>>
>>>>>>>> Rupert
>>>>>>>>
>>>>>>>>
>>>>>>>> ------------------------------------------------------------------------------
>>>>>>>> Own the Future-Intel® Level Up Game Demo Contest 2013
>>>>>>>> Rise to greatness in Intel's independent game demo contest.
>>>>>>>> Compete for recognition, cash, and the chance to get your game
>>>>>>>> on Steam. $5K grand prize plus 10 genre and skill prizes.
>>>>>>>> Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
>>>>>>>> _______________________________________________
>>>>>>>> Factor-talk mailing list
>>>>>>>> Factor-talk@lists.sourceforge.net
>>>>>>>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>>>>>>>
>>>>>>>>
>>>>>>>
>>>>>>>
>>>>>>> ------------------------------------------------------------------------------
>>>>>>> Own the Future-Intel® Level Up Game Demo Contest 2013
>>>>>>> Rise to greatness in Intel's independent game demo contest.
>>>>>>> Compete for recognition, cash, and the chance to get your game
>>>>>>> on Steam. $5K grand prize plus 10 genre and skill prizes.
>>>>>>> Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
>>>>>>> _______________________________________________
>>>>>>> Factor-talk mailing list
>>>>>>> Factor-talk@lists.sourceforge.net
>>>>>>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>>>>>>
>>>>>>>
>>>>>>
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------------
>>>>> Own the Future-Intel® Level Up Game Demo Contest 2013
>>>>> Rise to greatness in Intel's independent game demo contest.
>>>>> Compete for recognition, cash, and the chance to get your game
>>>>> on Steam. $5K grand prize plus 10 genre and skill prizes.
>>>>> Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
>>>>> _______________________________________________
>>>>> Factor-talk mailing list
>>>>> Factor-talk@lists.sourceforge.net
>>>>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>>>>
>>>>>
>>>>
>>>>
>>>> ------------------------------------------------------------------------------
>>>> Own the Future-Intel® Level Up Game Demo Contest 2013
>>>> Rise to greatness in Intel's independent game demo contest.
>>>> Compete for recognition, cash, and the chance to get your game
>>>> on Steam. $5K grand prize plus 10 genre and skill prizes.
>>>> Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
>>>> _______________________________________________
>>>> Factor-talk mailing list
>>>> Factor-talk@lists.sourceforge.net
>>>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>>>
>>>>
>>>
>>>
>>> ------------------------------------------------------------------------------
>>> Own the Future-Intel® Level Up Game Demo Contest 2013
>>> Rise to greatness in Intel's independent game demo contest.
>>> Compete for recognition, cash, and the chance to get your game
>>> on Steam. $5K grand prize plus 10 genre and skill prizes.
>>> Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
>>> _______________________________________________
>>> Factor-talk mailing list
>>> Factor-talk@lists.sourceforge.net
>>> https://lists.sourceforge.net/lists/listinfo/factor-talk
>>>
>>>
>>
>
>
> ------------------------------------------------------------------------------
> Own the Future-Intel® Level Up Game Demo Contest 2013
> Rise to greatness in Intel's independent game demo contest.
> Compete for recognition, cash, and the chance to get your game
> on Steam. $5K grand prize plus 10 genre and skill prizes.
> Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
> _______________________________________________
> Factor-talk mailing list
> Factor-talk@lists.sourceforge.net
> https://lists.sourceforge.net/lists/listinfo/factor-talk
>
>
------------------------------------------------------------------------------
Own the Future-Intel® Level Up Game Demo Contest 2013
Rise to greatness in Intel's independent game demo contest.
Compete for recognition, cash, and the chance to get your game
on Steam. $5K grand prize plus 10 genre and skill prizes.
Submit your demo by 6/6/13. http://p.sf.net/sfu/intel_levelupd2d
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
