Re from jt & Eric Gouriou: Quick permutations

To: info-dylan@ai.mit.edu
Subject: Re from jt & Eric Gouriou: Quick permutations
From: dauclair@hotmail.com
Date: Mon, 22 Jan 2001 10:15:02 -0500 (EST)
Organization: Deja.com
References: <94ac3d$6j9$1@nnrp1.deja.com>
Xref: traf.lcs.mit.edu comp.lang.dylan:13013

I got emails from jt and Eric Gouriou giving a couple of suggestions:

jt wrote:

>I briefly looked at your post this weekend (gave me a break from from
>javascript) and it seems to me that the overall running time was
>dominated by memory allocation. I couldn't see anything inherently
>inefficient about the algorithm.

and recommended speeding up the algorithm (as is) by:

>Other than that you might manually unroll the final calls to permute
>one or two vectors [snip 'if(size(seq) = 1) list(seq) end;' etc]

which sped the resulting executable a bit.

I was afraid that the consing would be the cause of the slowness
(actually, I feared that the recursion coupled with the consing was the
problem).  Eric sent me three libraries that did combinations.  His
libraries precomputed the size of the result sequence and filled it
using Pascal's Triangle.

I'll try a two-phase approach using Eric's solution and jt's profiling:
first I'll see if a pre-allocated sequence (of size n!) solves (the
majority of) the time problem, then I'll try computing the permutations
using Pascal's Triangle.

Thanks for the help,
Sincerely,
Doug Auclair, not knowing anything about using Pascal's Triangle, but on
a programming quest to learn

Sent via Deja.com
http://www.deja.com/

References:

Quick permutations

From: dauclair@hotmail.com