Hello, I'm an old lisp-list user and python is my first use of dynamic array-list.
Complexity for lisp-list is constant and fast o(1) when we add a new element at the head of the list. (cons e L) in Lisp or e::L in caml. Complexity is also o(1) when we take the end of the list, or read the first term. (cdr L) and (car L) in Lisp, or hd L and tl L in caml. In theses cases the list L remains the same. Can I see in python that L[-1], L.push() and L.pop() are always fast in constant time ? The only difference is about the global change of L in sage and python. Python lists have also constant time for reading an element L[k] and get the length L.len. For lisp-list theses two times are not constant and may be long for long lists. And the python code must either never use the previous value of L, or copy the list, but it may be long... And it must be always exclude to change the list L in a loop over L. Do you know standard algorithms which are better with python and impossible with lists ? or better in lisp and slower with python ? Francois > As you say, the iterator goes by index. This isn't really "solvable" the > way you seem to expect because of how lists fundamentally work. Workarounds: > > a) for x in L[:]: ... # makes a copy > b) remove from the end of the list... > > If your list is big: Note that removing from the middle of a list is > going to be expensive since the remainder of the list is copied for each > iteration. You should consider alternative ways of expressing your > algorithm (or, if you have to do this, look around for a linked list > implementation for Python). > > Removing from the end is cheap, so is removing from either end using > collections.deque. > > --~--~---------~--~----~------------~-------~--~----~ To post to this group, send email to sage-support@googlegroups.com To unsubscribe from this group, send email to sage-support-unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/sage-support URL: http://www.sagemath.org -~----------~----~----~----~------~----~------~--~---
