Thank you for the invitation and orientation.
—
Sent from Mailbox for iPhone
On Tue, Apr 2, 2013 at 8:41 AM, John Benediktsson <mrj...@gmail.com>
wrote:
> 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(R) 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://altfarm.mediaplex.com/ad/ck/12124-176961-30367-2
_______________________________________________
Factor-talk mailing list
Factor-talk@lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/factor-talk
