[Pyrex] Question, plus suggestions for improvement?

[Bill Mill]

On 8/1/06, Josiah Carlson <jcarlson at uci.edu> wrote:
>
> "Bill Mill" <bill.mill at gmail.com> wrote:
> >
> > > If you need to perform many accesses, it's better to convert it to a
> > > standard C array of integers/floats, allocated with malloc() (and freed with
> > > free()). You can index it with any "cdef int" variable, and this will
> > > provide C-like performance. This is especially useful if the same data is
> > > used many times (eg: convert the data to C array in the constructor, and
> > > then use it in all the methods).
> >
> > While very interesting, I won't copy the thread between you and
> > Josiah. Instead, I'll give you both some more requirements.
> >
> > Since the size of the input list is limited severely by practical
> > concerns (it has factorial(len(input_list)) permutations), my problem
> > is largely one of many array accesses.
> >
> > Would it be better to convert the list into a C array? How should I do
> > so? I assume I'll need to convert it back to a python array when I'm
> > done - is that going to kill any performance gains I may see inside
> > the main loop? (Well, if you answer the second question, I'll just
> > experiment and answer the third for you.)
>
> See my most recent post, which includes an optimized version which does
> not require converting the input in any way.  It copies the input, and
> initializes an array of ints.  From then on, it permutes this list of
> ints (which is fast), and just before returning, copies the original
> input to the copy initially made (thus creating a permutation), and
> returns.  It should be about as fast as you could get this particular
> algorithm in Pyrex.
>
>  - Josiah
>

I think your post hit while I was writing mine. Thanks very much for
all that effort.

I have to report, unfortunately, that my working version of your code,
which I dubbed PermuteJ, ends up being a bit slower than Permute2. My
guess is that the cost of transferring the C array to the Python one
for every iteration outweighs the benefit of the quicker C accesses,
but I have not really tested that assertion.

(I posted my modified version of your code at
http://www.bigbold.com/snippets/posts/show/2353 ).

Thanks
Bill Mill
bill.mill at gmail.com