Robert Bradshaw wrote: > 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 ? >> I think it's mainly that "the average Python programmer" tends to use random indexing a lot more than remove(), and so list is optimized for that common use pattern. Those who actually think about algorithms, complexity etc. can be assumed to be able to switch another better suited type if needed.
(Also, everything else being equal, a dynamic array uses 1/2 the memory as there's no need for pointers between elements). Dag Sverre --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
