On Thu, Oct 20, 2011 at 4:55 AM, Simon King <[email protected]> wrote: > Hi Robert, > > On 20 Okt., 13:38, Robert Bradshaw <[email protected]> > wrote: >> > 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. > > Yes. But the point is that I am popping from (several) input lists, > while I am only appending to the list that will eventually be > returned. I can revert the input lists (profiting from fast L.pop()) > and don't need to revert the output list.
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 implemented. >> Likely not. The primary benefits (100x or more speedups) are when >> indexing and using native C types. Why not write your own simple >> queue? > > Would be worth a try. Thank you for the code! > > Best regards, > Simon > > -- > To post to this group, send email to [email protected] > To unsubscribe from this group, send email to > [email protected] > For more options, visit this group at > http://groups.google.com/group/sage-support > URL: http://www.sagemath.org > -- To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org
