[Steve Howell] > Why wouldn't you get a competent C programmer simply make > list_ass_slice smart enough to make list.pop(0) O(1)?
When this suggestion was discussed on python-dev years ago, it was rejected. One reason is that it was somewhat common for C code to access the list data structure directly (bypassing API accessor functions). Changing the list to have a starting offset would break existing C extensions. Another reason is that Guido is non-tolerant of space or time trade-offs for lists and tuples because they pervade the language and are heavily used internally. Any additional space or time requirement however small would impact the language performance as a whole. FWIW, that is also the reason that lists are not weak-referenceable (it would cost one extra pointer field per instance and that wasn't deemed to be worth it). > The brilliant computer scientist, Christian Heimes, provides the > answers, and I am paraphrasing here, of course: IMHO, Christian IS a brilliant computer scientist, so I'll ignore the rude intention and take the sentence literally. > 1) You can save 64 bits for every list by not storing an extra > pointer! > 2) You can simplify the CPython implementation! > 3) You can avoid the oh-so-expensive check "if ilow == 1" for all > operations that don't need this optimization! > > Sounds like two micro-optimizations to me (and a copout to boot). Micro or not, these reasons were part of Guido's rationale. Tim Peters and I also participated in the conversation and did not disagree. So, collections.deque() was born and the problem stopped being an issue. Also, Daniel Stuzbach has published a blist implementation that offers high performance insertions and deletions and fast handling of sparse lists. Raymond -- http://mail.python.org/mailman/listinfo/python-list
