On Jan 23, 7:54 am, Steven D'Aprano <st...@remove-this- cybersource.com.au> wrote: > On Sat, 23 Jan 2010 09:57:04 -0500, Roy Smith wrote: > > In article <hje979$kc...@news.eternal-september.org>, > > "Alf P. Steinbach" <al...@start.no> wrote: > > >> But it would IMHO have been better if it wasn't called "list", which > >> brings in the wrong associations for someone used to other languages. > > > +1. > > > When I first started using Python (back in the 1.4 days), I assumed a > > list was a singly-linked list. > > Why would you do that? I can think of at least eight different > implementations of the abstract list data structure: > > constant-size array > variable-size array > variable-size array with amortised O(1) appends > singly-linked list > singly-linked list with CDR coding > doubly-linked list > skip list > indexable skip list > > One can reasonably disregard constant-sized arrays as a possibility, > given that Python lists aren't fixed size (pity the poor Pascal and > Fortran coders who are stuck with static arrays!), but the rest are all > reasonable possibilities. Why assume one specific implementation in the > absence of documentation promising certain performance characteristics? > > > Oddly enough, I was going to write in the above paragraph, "like a C++ > > STL list", until I happened to glance at the STL docs and refreshed my > > memory that an STL list is doubly-linked. Which just goes to show that > > making assumptions based on names is a bad idea. > > Exactly :) > > > So, we're right back to my statement earlier in this thread that the > > docs are deficient in that they describe behavior with no hint about > > cost. Given that, it should be no surprise that users make incorrect > > assumptions about cost. > > There are quite a few problems with having the documentation specify cost: > > (1) Who is going to do it? Any volunteers? > > (2) Big-oh notation can be misleading, especially for naive users, or > those whose intuition for what's fast has been shaped by other languages. > Big-oh doesn't tell you whether something is fast or slow, only how it > scales -- and sometimes not even then. > > (3) Having documented a particular performance, that discourages > implementation changes. Any would-be patch or new implementation not only > has to consider that the functional behaviour doesn't change, but that > the performance doesn't either. > > In practice the Python developers are unlikely to make an implementation > change which leads to radically worse performance, particularly for > critical types like list and dict. But in other cases, they might choose > to change big-oh behaviour, and not wish to be tied down by documentation > of the cost of operations. > > (4) How much detail is necessary? What about degenerate cases? E.g. dict > lookup in CPython is typically O(1) amortised, but if all the keys hash > to the same value, it falls to O(N). > > (5) Should the language guarantee such degenerate behaviour? Who decides > which costs are guaranteed and which are not? > > (6) Such performance guarantees should be implementation specific, not > language specific. CPython is only one implementation of the language out > of many. >
Bringing this thread full circle, does it make sense to strike this passage from the tutorial?: ''' It is also possible to use a list as a queue, where the first element added is the first element retrieved (“first-in, first-out”); however, lists are not efficient for this purpose. While appends and pops from the end of list are fast, doing inserts or pops from the beginning of a list is slow (because all of the other elements have to be shifted by one). ''' I think points #3 and #6 possibly apply. Regarding points #2 and #4, the tutorial is at least not overly technical or specific; it just explains the requirement to shift other elements one by one in simple layman's terms. -- http://mail.python.org/mailman/listinfo/python-list
