On Oct 27, 2009, at 3:15 AM, Francois Maltey wrote: > 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 ?
If you really want to see, you could look at the source or benchmark it. > 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 ? Nothing's impossible, but binary searches are much faster with dynamic array lists. > or better in lisp and slower with python ? Pathfinding algorithms could benefit by storing partial paths as linked lists (though of course the linked lists structure is easy to write in Python too). - Robert > 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 -~----------~----~----~----~------~----~------~--~---
