sorting+lambdas in Cython

[David Joyner]

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.)

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. 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.

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

Any ideas?

- David Joyner

[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

[David Joyner]

Okay, thanks. This helped narrow down the problem.

I had a cdef command which I omitted from the email,
for simplicity (I assumed it could not have been the problem,
but it was):


def my_sort2():
cdef list L
L = [2,1,3,0]
L.sort(cmp=my_order, key=None, reverse=False)
#L.sort()
return L


This will not compile:

sage: attach "/home/wdj/sagefiles/codes/sort_test.spyx"
Compiling /home/wdj/sagefiles/codes/sort_test.spyx...
Error compiling cython file:
Error converting /home/wdj/sagefiles/codes/sort_test.spyx to C:


Error converting Pyrex file to C:
------------------------------------------------------------
...
return x-y

def my_sort2():
cdef list L
L = [2,1,3,0]
L.sort(cmp=my_order, key=None, reverse=False)
^
------------------------------------------------------------

/home/wdj/.sage/temp/hera/342/spyx/_home_wdj_sagefiles_codes_sort_test_spyx/_home_wdj_sagefiles_codes_sort_test_spyx_0.pyx:19:5:
Cannot convert 'int (object) except -1' to Python object


sage:

Does this make sense?

[Robert Bradshaw]

On Dec 13, 2008, at 11:21 AM, David Joyner wrote:

>>>
>>> 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).
>
>
> Okay, thanks. This helped narrow down the problem.
>
> I had a cdef command which I omitted from the email,
> for simplicity (I assumed it could not have been the problem,
> but it was):
>
>
> def my_sort2():
> cdef list L
> L = [2,1,3,0]
> L.sort(cmp=my_order, key=None, reverse=False)
> #L.sort()
> return L
>
>
> This will not compile:

[...]

OK, that was a bug (when it's declared as a list), and was fixed this
morning when you pointed it out.

http://trac.cython.org/cython_trac/ticket/161

- Robert