On 26Jan2010 01:57, Terry Reedy <tjre...@udel.edu> wrote: | On 1/25/2010 9:32 PM, Nick Coghlan wrote: | >However, as Cameron pointed out, the O() value for an operation is an | >important characteristic of containers, and having people get used to an | >O(1) list.pop(0) in CPython could create problems not only for other | >current Python implementations but also for future versions of CPython | >itself. | | The idea that CPython should not be improved because it would spoil | programmers strikes me as a thin, even desparate objection.
Hey, I even used the word "thin" to describe my concern! My point was that I look on python builtins like list and dict as highly optimised, highly efficient facilities. That means that I expect a "list" to be very very much like a linear array as one would find in C-like languages, with realloc() managment behind the scenes to handle the resizing requirements on append/extend. It also means that the O() cost of operations should be pretty obvious. pop(0) "obviously" involves shuffling everything down one slot. This means that the python programmer should expect that the common "array" type operations such as __getitem__ should be as blazingly fast as possible, and to expect that barring unusual programmer requirements, if I'm thinking about "arrays" I should almost always reach for a python list. The proposed change to make pop(0) O(1) involves adding a base offset to the internal list implementation. Doesn't that incur a (small) overhead to _every_ list operation? Doesn't that weaken "list" as the "as efficient as possible" implementation of choice for "array"-like things? | One | could say that same thing about the recent optimization of string += | string so that repeated concats are O(n) instead of O(n*n). What a | trap if people move code to other implementations (or older Python) | without that new feature. | | Of course, the whole purpose of adding a jit to CPython would be to | spoil us. | | It is a fact already that optimizing CPython code is specific to a | particular interpreter, system, and workload. Yes, optimisation is nice. Higher seed is nice. But there are optimisations that simple fix inefficiencies or provide a special case for a common operation, and there are those with side effects elsewhere in the implementation (i.e. the base offset this pop(0) opt would incur, which adds a (small) cost to everything). The other aspect, mentioned elsewhere in this thread, is that programmers should know the O() cost of these operations. Cheers, -- Cameron Simpson <c...@zip.com.au> DoD#743 http://www.cskk.ezoshosting.com/cs/ I am a kind of burr; I shall stick. - William Shakespeare, _Measure for Measure_ _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
