Sent from my iPhone
> To post to this group, send email to sage-s...@googlegroups.com
> To unsubscribe from this group, send email to sage-support...@googlegroups.com
> For more options, visit this group at http://groups.google.com/group/sage-support
> URL: http://www.sagemath.org
I have no idea why L.pop(0) is not optimized, but L.pop(<int>0) is
(and the latter should be very fast). Clearly a bug in Cython, but
user the latter.
> After all, "collections" is Python, not Cython.
> Nevertheless, I'd still appreciate to learn a Cython replacement for
> pop(0) that is fast on long lists as well.
There isn't one as pop(0) on a list requires re-copying the entire
contents of the list. You could use numpy arrays, where slices such as
L[1:] are views. A cython-implemented linked list may perform well
here as well.
> I found this:
> but Sturla Molden's trick didn't work for me: Cython complained about
> an incomplete type.
> Best regards,
Very interesting--looks like the crossover point is around 200
elements. Looks like Python's native pop uses memmove rather than
doing a loop shift the array which could account for the difference.
> Since L.pop() (popping the last item) is so much faster than L.pop(0),
> I could perhaps just revert my lists.
Inserting into the 0th element will have the same issues as popping it.
>> > Nevertheless, I'd still appreciate to learn a Cython replacement for
>> > pop(0) that is fast on long lists as well.
>> There isn't one as pop(0) on a list requires re-copying the entire
>> contents of the list.
> Really? I'm surprised that an in-place change requires copying.
It's an array, not a linked list. The k-th item of a list occupies a
fixed location in memory relative to the head of the object, so
removing an item requires shifting everything. (Not the data, just the
>> You could use numpy arrays, where slices such as
>> L[1:] are views. A cython-implemented linked list may perform well
>> here as well.
> I've never used numpy before, but I'll give it a try.
> 625 loops, best of 3: 1.07 µs per loop
As numpy slices are views, they are a bit more expensive but require
O(1) time, whereas slicing a list is O(n) time.
sage: from numpy import array
sage: for k in [2..5]:
... L = range(10^k)
... N = array(L)
625 loops, best of 3: 656 ns per loop
625 loops, best of 3: 576 ns per loop
625 loops, best of 3: 3.42 µs per loop
625 loops, best of 3: 627 ns per loop
625 loops, best of 3: 45.5 µs per loop
625 loops, best of 3: 578 ns per loop
625 loops, best of 3: 959 µs per loop
625 loops, best of 3: 630 ns per loop
Looks like your arrays are pretty small though.
> Will the picture be different when cimporting numpy.ndarray in Cython?
Likely not. The primary benefits (100x or more speedups) are when
indexing and using native C types. Why not write your own simple
cdef class Queue:
cdef list elements
cdef int start
cdef int end
cdef int capacity
def __init__(self, initial_capacity=5):
self.elements = [None] * initial_capacity
self.start = 0
self.end = 0
self.capacity = initial_capacity
cpdef push(self, o):
self.elements[self.end] = o
self.end = (self.end + 1) % self.capacity
if self.end == self.start:
self.elements = self.elements[self.start:] +
self.elements[:self.end] + [None] * self.capacity
self.start = 0
self.end = self.capacity
self.capacity *= 2
if self.start == self.end:
raise ValueError, "Empty queue"
self.elements[self.start] = None
self.start = (self.start + 1) % self.capacity
def f(Queue q):
return q.pop(), q
q = Queue()
for k in range(1000):
625 loops, best of 3: 147 ns per loop
Ah, in that case it would make total sense. Your example feels a lot
like the category pushout stuff :).
>> It's an array, not a linked list. The k-th item of a list occupies a
>> fixed location in memory relative to the head of the object, so
>> removing an item requires shifting everything...
> ... except when removing the last item (which explains why L.pop() is
> fast), OR THE FIRST. Because, when removing the first item, you don't
> need to shift the other items towards the head, because you could more
> easily move the head towards the other items.
That depends on how easily you can shift the head; it's an
implementation detail in Python (and most other languages that I'm
aware of) that you can't. Of course C lets you do this, but that's
because it doesn't really have arrays, just pointers (and you still
usually have to keep the "original" head around to free it). Of course
being able to shift the head as well as the tail is what I
>> Likely not. The primary benefits (100x or more speedups) are when
>> indexing and using native C types. Why not write your own simple
> Would be worth a try. Thank you for the code!
> Best regards,