[Cython] [sage-devel] sorting+lambdas in Cython

[Robert Bradshaw]

On Dec 13, 2008, at 8:12 AM, David Joyner wrote:

> Hi:
>
> Perhaps this should go to the Cython devel list
> but I looked at the archives and FAQ and guide on
> cython.org and did not see this issue discussed.
> (BTW, the links on http://docs.cython.org/
> under "Indices and tables" are broken, and also
> the docs page has no link back to the main cython page.)

Thanks. This is relevant here and there.

> Basic idea is that I would like to rewrite the coding theory
> modules in Cython. One of the basic tasks is to sort
> a collection of vectors by the "Hamming weight" (the number of
> non-zero positions). This is very easy to do using
> Python since you can feed sort a comparison function,
> like this:
>
> def my_sort1():
>     L = [2,1,3,0]
>     #L.sort(cmp=lambda x,y: x-y, key=None, reverse=False)
>     L.sort()
>     return L
>
> or like this:
>
> def my_order(x,y):
>     return x-y
>
> def my_sort2():
>     L = [2,1,3,0]
>     #L.sort(cmp=my_order, key=None, reverse=False)
>     L.sort()
>     return L
>
> However, I cannot figure out how to do something like this
> in Cython.

The second works just fine for me (with our without the custom cmp  
command).

> I resorted to trying to build my own sort function
> in Cython, but it turned out to be slower than simply using the
> Python sort.

Python's sort it rather good, it'd be hard to beat it generically. If  
I were trying to speed things up, I would make sure your hamming  
weight computation is extremely fast, and (safely) cached.  
Equivalently, you could sort the list [(v.hamming_weight(), v) for v  
in L] using a cmp function that only looks at the first element of  
the tuple.

If this wasn't fast enough, you could get the hamming weights as a  
list of c ints, sort that (keeping track of the permutation) and then  
return the permuted list. Sorting a list of ints can be written  
faster than Python's sort.

> Also, I'd like to know if lambdas are implemented in Cython.

No, not yet. I would love to do this, and think I know how, but don't  
know when I'll have the time.

- Robert