list.pop(0) vs. collections.dequeue
in [Python]
|
From: Steve Howell on 25 Jan 2010 18:40 --- On Mon, 1/25/10, Chris Colbert <sccolbert(a)gmail.com> wrote: > > looking at that code, i think you could solve > your whole problem with a single called to reversed() (which > is NOT the same as list.reverse()) > I do not think that's actually true. It does no good to pop elements off a copy of the list if there is still code that refers to the original list. So I think you really do want list.reverse(). The problem with reversing the lists is that it gets sliced and diced and passed around to other methods, one of which, html_block_tag, recursively calls back to the main method. So you could say that everybody just has to work with a reversed list, but in my mind, that would be just backward and overly complicated. I am not completely ruling out the approach, though. The idea of modelling the program essentially as a stack has some validity, and it probably would run faster. https://bitbucket.org/showell/shpaml_website/src/tip/shpaml.py
From: geremy condra on 25 Jan 2010 18:45 On Sat, Jan 23, 2010 at 4:38 AM, Alf P. Steinbach <alfps(a)start.no> wrote: <snip> > Hm, it would be nice if the Python docs offered complexity (time) > guarantees in general... > > Cheers, > > - Alf This would be a very welcome improvement IMHO- especially in collections. Geremy Condra
From: Ethan Furman on 25 Jan 2010 19:25 Steve Howell wrote: >> On Sat, 23 Jan 2010 09:57:04 -0500, Roy Smith wrote: >>> 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. No hint? Looking at the below snippet of docs -- "not efficient" and "slow" sound like pretty good hints to me. > 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. > I think the paragraph is fine. Instead of waiting for the (hundreds of?) posts wondering why making a FIFO queue from a list is so slow, and what's wrong with Python, etc, etc, it points out up front that yes you can, and here's why you don't want to. This does not strike me as too much knowledge. ~Ethan~
From: Alf P. Steinbach on 25 Jan 2010 20:13 * Ethan Furman: > Steve Howell wrote: >>> On Sat, 23 Jan 2010 09:57:04 -0500, Roy Smith wrote: >>>> 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. > > No hint? Looking at the below snippet of docs -- "not efficient" and > "slow" sound like pretty good hints to me. > >> 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. >> > > I think the paragraph is fine. Instead of waiting for the (hundreds > of?) posts wondering why making a FIFO queue from a list is so slow, and > what's wrong with Python, etc, etc, it points out up front that yes you > can, and here's why you don't want to. This does not strike me as too > much knowledge. Is the tutorial regarded as part of the language specification? I understand that the standard library docs are part (e.g. 'object' is only described there), and that at least some PEPs are. Cheers, - Alf
From: Jerry Hill on 25 Jan 2010 20:58
On Sat, Jan 23, 2010 at 4:38 AM, Alf P. Steinbach <alfps(a)start.no> wrote: > Hm, it would be nice if > the Python docs offered complexity (time) guarantees in general... Last time it came up, I don't think there was any core developer interest in putting complexity guarantees in the Python Language Reference. Some folks did document the behavior of most of the common CPython containers though: http://wiki.python.org/moin/TimeComplexity -- Jerry |