On Fri, Jan 29, 2010 at 12:48 AM, Terry Reedy wrote:
> On 1/28/2010 6:30 PM, Josiah Carlson wrote:
>
>> I would also point out that the way these things are typically done is
>> that programmers/engineers have use-cases that are not satisfied by
>> existing structures, they explain the issues they
--- On Fri, 1/29/10, Stephen J. Turnbull wrote:
>
> > Lisp lists are really stacks
>
> No, they're really (ie, concretely) singly-linked
> lists.
>
> Now, stacks are an abstract data type, and singly-linked
> lists provide
> an efficient implementation of stacks. But that's not
> what link
Minor erratum:
Stephen J. Turnbull writes:
> Emacs hasn't made that choice, XEmacs did. I believe Emacs is still
> "restricted" to 128MB, or maybe 256MB, buffers. They recently had an
> opportunity to increase integer size, and thus maximum buffer size,
> but refused it. It's not a no-brai
Josiah Carlson writes:
> On Fri, Jan 29, 2010 at 11:31 PM, Stephen J. Turnbull
> wrote:
> > Some people complained, but we considered this well worthwhile (moving
> > one "type bit" from the car to the header allowed Lisp integers to
> > cover the range -1G to +1G, and there are a surprising
On Fri, Jan 29, 2010 at 11:31 PM, Stephen J. Turnbull
wrote:
> Josiah Carlson writes:
> > On Thu, Jan 28, 2010 at 8:57 PM, Steve Howell wrote:
>
> > > What do you think of LISP, and "car" in particular (apart from
> > > the stupidly cryptic name)?
>
> > Apples and oranges.
>
> True, but speak
On Fri, Jan 29, 2010 at 11:25 PM, Stephen J. Turnbull
wrote:
> Josiah Carlson writes:
>
> > Lisp lists are really stacks
>
> No, they're really (ie, concretely) singly-linked lists.
>
> Now, stacks are an abstract data type, and singly-linked lists provide
> an efficient implementation of stacks.
Josiah Carlson writes:
> On Thu, Jan 28, 2010 at 8:57 PM, Steve Howell wrote:
> > What do you think of LISP, and "car" in particular (apart from
> > the stupidly cryptic name)?
> Apples and oranges.
True, but speaking of Lisp lists, here's some possibly relevant
experience. About 10 years
Josiah Carlson writes:
> Lisp lists are really stacks
No, they're really (ie, concretely) singly-linked lists.
Now, stacks are an abstract data type, and singly-linked lists provide
an efficient implementation of stacks. But that's not what linked
lists "really are". For example, singly-lin
On Thu, Jan 28, 2010 at 9:48 PM, Terry Reedy wrote:
> On 1/28/2010 6:30 PM, Josiah Carlson wrote:
>
>> I would also point out that the way these things are typically done is
>> that programmers/engineers have use-cases that are not satisfied by
>> existing structures, they explain the issues they
On Thu, Jan 28, 2010 at 8:57 PM, Steve Howell wrote:
> --- On Thu, 1/28/10, Josiah Carlson wrote:
>> [...] in the decade+ that I've been using
>> Python and
>> needed an ordered sequence; lists were the right solution
>> 99% of the
>> time [...]
>
> What do you think of LISP, and "car" in particu
Am 28.01.2010 05:30, schrieb Steve Howell:
> If you want tools that are easy to use correctly, make them bug-free and
> document their behavior. If you want tools that are easy to use well, then
> make them perform better. I am not sure how my patch contradicts either of
> these goals.
>
> You
On 1/28/2010 11:57 PM, Steve Howell wrote:
> --- On Thu, 1/28/10, Josiah Carlson wrote:
>> [...] in the decade+ that I've been using
>> Python and
>> needed an ordered sequence; lists were the right solution
>> 99% of the
>> time [...]
>
> What do you think of LISP, and "car" in particular (apart
On 1/28/2010 6:30 PM, Josiah Carlson wrote:
I would also point out that the way these things are typically done is
that programmers/engineers have use-cases that are not satisfied by
existing structures, they explain the issues they have with existing
structures, and they propose modifications.
--- On Thu, 1/28/10, Josiah Carlson wrote:
> [...] in the decade+ that I've been using
> Python and
> needed an ordered sequence; lists were the right solution
> 99% of the
> time [...]
What do you think of LISP, and "car" in particular (apart from the stupidly
cryptic name)?
___
Having read the entirety of the thread (which is a rare case these
days, I need more spare time), and being that I'm feeling particularly
snarky today, I'm going to agree 100% with everything that Raymond has
said in this message and his few subsequent messages. Snarky comments
to follow.
I would
-BEGIN PGP SIGNED MESSAGE-
Hash: SHA1
Steve Howell wrote:
> --- On Wed, 1/27/10, Alex Gaynor wrote:
>
>> "Python lists implement a pretty useless data structure"
>>
>> It's very difficult for ideas to gain traction when they
>> contain such
>> useless, and obviously wrong, rhetoric. The
On Tuesday 26 January 2010, Steve Howell wrote:
> Here are the benefits of an O(1) implementation.
[...]
> Did I leave anything out?
Good summary, Steve, thanks!
Anyway, you left two out:
* Inserting at the front gets the same complexity as inserting at the back.
* Inserting and erasing anywh
On 27Jan2010 23:08, Nick Coghlan wrote:
| Cameron Simpson wrote:
| > 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 efficie
On Wed, Jan 27, 2010 at 8:46 PM, Steve Howell wrote:
> The statement was meant 99% tongue in cheek. Like probably 99.99% of Python
> programmers, I use lists all the time; that's why I want them to be more
> versatile.
>
> There's also a 1% element of truth to the statement. To the extent that
--- On Wed, 1/27/10, Alex Gaynor wrote:
>
> "Python lists implement a pretty useless data structure"
>
> It's very difficult for ideas to gain traction when they
> contain such
> useless, and obviously wrong, rhetoric. There's an
> enormous body of
> code out there that begs to disagree with
On Wed, Jan 27, 2010 at 8:30 PM, Steve Howell wrote:
> I am not sure why Python lists get all the syntax sugar and promotion over
>deque, when in reality, Python lists implement a pretty useless data
>structure. Python lists are a glorification of a C array built on top of a
>memory-upward-bia
On Wed, Jan 27, 2010 at 11:30 PM, Steve Howell wrote:
>
>
> --- On Wed, 1/27/10, Raymond Hettinger wrote:
>
>> From: Raymond Hettinger
>
>> * the current design encourages people to use
>> the right data structure for a given need. the
>> proposed change makes the trades-off murky and
>> implem
--- On Wed, 1/27/10, Raymond Hettinger wrote:
> From: Raymond Hettinger
> * the current design encourages people to use
> the right data structure for a given need. the
> proposed change makes the trades-off murky and
> implementation dependent.
Are you saying that the current slowness of
On Jan 27, 2010, at 2:56 PM, Steve Howell wrote:
>
> --- On Wed, 1/27/10, Raymond Hettinger wrote:
>
>> From: Raymond Hettinger
>> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
>> To: "Martin v. Löwis"
>> Cc: "Steve Ho
> From: Antoine Pitrou
> gmail.com> writes:
> >
> > AFAICT, the performance of the proposal:
> >
> > * increases space requirements by a small fixed
> amount
>
> Well, given my proposal (assuming it turns out ok) it
> doesn't.
>
> > * s.append() performance slightly degraded.
>
> Why?
>
A
On Wed, Jan 27, 2010 at 2:14 PM, Daniel Stutzbach
wrote:
> On Wed, Jan 27, 2010 at 3:49 PM, Raymond Hettinger
> wrote:
>>
>> Also, am not sure if this affects psyco or the other
>> implementations such as Jython which may implement
>> lists in terms of existing Java containers.
>
> Or Unladen Swa
Raymond Hettinger gmail.com> writes:
>
> AFAICT, the performance of the proposal:
>
> * increases space requirements by a small fixed amount
Well, given my proposal (assuming it turns out ok) it doesn't.
> * s.append() performance slightly degraded.
Why?
> * the resize performance doesn't wo
--- On Wed, 1/27/10, Raymond Hettinger wrote:
> From: Raymond Hettinger
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Martin v. Löwis"
> Cc: "Steve Howell" , python-dev@python.org
> Date: Wednesday, January 27, 2010, 1:49 P
On Wed, Jan 27, 2010 at 3:49 PM, Raymond Hettinger <
raymond.hettin...@gmail.com> wrote:
> Also, am not sure if this affects psyco or the other
> implementations such as Jython which may implement
> lists in terms of existing Java containers.
>
Or Unladen Swallow. I'm -1 on mucking with any of t
On Jan 27, 2010, at 11:38 AM, Martin v. Löwis wrote:
>> Lists are indeed used *everywhere* and *vast* quantities, which is
>> why optimizations on list operations are worthwhile to pursue.
>
> Unfortunately, the proposed change is a pessimisation, not an
> optimisation. We probably shouldn't dis
--- On Wed, 1/27/10, Antoine Pitrou wrote:
> From: Antoine Pitrou
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: python-dev@python.org
> Date: Wednesday, January 27, 2010, 12:41 PM
> Le mercredi 27 janvier 2010 à 11:49
> -0800, Steve Howe
Le mercredi 27 janvier 2010 à 11:49 -0800, Steve Howell a écrit :
> A slightly more sane alternative would be to leave ob_size and ob_item
> alone with their current semantics, and then replace allocated with
> self->excess, where
>
> self->excess == excess_above * 256 + excess_below.
Or we cou
--- On Wed, 1/27/10, Antoine Pitrou wrote:
> From: Antoine Pitrou
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: python-dev@python.org
> Date: Wednesday, January 27, 2010, 6:15 AM
> Nick Coghlan
> gmail.com> writes:
> >
> > The
> In my mind Python's lists should have the same performance
> characteristics as the paper list (or better).
I think you'll have to adjust your mind then. People have
proposed various data structures that *do* work efficiently as
paper lists. So if you want a paper list, use one of them, rather
t
> Lists are indeed used *everywhere* and *vast* quantities, which is
> why optimizations on list operations are worthwhile to pursue.
Unfortunately, the proposed change is a pessimisation, not an
optimisation. We probably shouldn't discuss it further, at least not
until a PEP gets written by its p
--- On Wed, 1/27/10, Virgil Dupras wrote:
>
> Why is this thread still going? It seems to me that the
> case for this
> change is very weak. Lists, like dicts and tuples, are
> used
> *everywhere* and in *vast* quantities. Making them grow by
> 4 or 8
> bytes each for such a corner case can't be
--- On Wed, 1/27/10, Daniel Stutzbach wrote:
> From: Daniel Stutzbach
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Steve Howell"
> Cc: "John Arbash Meinel" , python-dev@python.org
> Date: Wednesday, January 27, 2010, 8:20 AM
On Wed, Jan 27, 2010 at 4:55 PM, Steve Howell wrote:
> --- On Wed, 1/27/10, John Arbash Meinel wrote:
>
>> From: John Arbash Meinel
>> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
>> To: "Steve Howell"
>> Cc: "Guido
On Wed, Jan 27, 2010 at 9:55 AM, Steve Howell wrote:
> Fair enough, but that's still wasteful of memory, keeping around a bunch of
> None elements because you can't inexpensively delete them.
>
Even if there are many references to it, there is only one None element.
--
Daniel Stutzbach, Ph.D.
P
--- On Wed, 1/27/10, John Arbash Meinel wrote:
> From: John Arbash Meinel
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Steve Howell"
> Cc: "Guido van Rossum" , "Nick Coghlan"
> , python-dev@python.org
> Date: W
> Right now the Python programmer looking to aggressively delete elements from
> the top of a list has to consider the tradeoff that the operation takes O(N)
> time and would possibly churn his memory caches with the O(N) memmove
> operation. In some cases, the Python programmer would only hav
--- On Tue, 1/26/10, Guido van Rossum wrote:
> From: Guido van Rossum
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Steve Howell"
> Cc: "Nick Coghlan" , python-dev@python.org
> Date: Tuesday, January 26, 2010, 12:57 PM
Daniel Stutzbach stutzbachenterprises.com> writes:
>
>
> I don't think your analogy works, unless you recopy your to-do lists whenever
> you complete a task in the middle of the list.
I think his analogy suggests that his to-do list is a doubly-linked list ;)
Or perhaps an array with lazy dele
Nick Coghlan gmail.com> writes:
>
> The big practical concern is actually the memory cost of adding yet
> another pointer (potentially 8 bytes of data) to every list object, even
> empty ones.
It needn't be, actually. Why?
You only need to store this other pointer when you have an orphaned area
Glenn Linderman, 27.01.2010 10:13:
> As a newcomer to python, I must say that I wouldn't expect a list to be
> like an array. I'd expect it more to be like a list... many
> implementations of lists (linked lists, in particular) make it O(1) to
> add to the front or back. An array can be used to r
--- On Wed, 1/27/10, Daniel Stutzbach wrote:
> From: Daniel Stutzbach
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Steve Howell"
> Cc: python-dev@python.org
> Date: Wednesday, January 27, 2010, 5:32 AM
> On Wed, Jan 27,
> 2010 at
On Wed, Jan 27, 2010 at 7:13 AM, Steve Howell wrote:
> My concept of Python lists is that they should have at least the same
> performance characteristics as an ordinary to-do list that you make with
> pencil, paper, and an eraser.
>
> When you complete the first task on your to-do list, you can
--- On Tue, 1/26/10, Cameron Simpson wrote:
> From: Cameron Simpson
> | 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 l
--- On Wed, 1/27/10, Glenn Linderman wrote:
> As a newcomer to python, I must say that I wouldn't expect
> a list to be like an array. I'd expect it more to be
> like a list... many implementations of lists (linked lists,
> in particular) make it O(1) to add to the front or
> back. An array can
Cameron Simpson wrote:
> 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
On approximately 1/26/2010 7:50 PM, came the following characters from
the keyboard of Cameron Simpson:
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 on
On 26Jan2010 01:57, Terry Reedy 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
Benjamin Peterson wrote:
> 2010/1/25 Steve Howell :
>> I am interested in creating a patch to make deleting elements from the front
>> of Python list work in O(1) time by advancing the ob_item pointer.
>
> How about just using a deque?
... or a stack:
http://www.egenix.com/products/pytho
>>
>> Ah, but that applies for *large* lists. Adding 8 bytes to
>> each list
>> object applies to *all* lists. I betcha that many programs
>> use many
>> tiny lists.
>>
>
> Even most tiny-ish lists are wasting memory, though, according to this
> sequence:
>
> 4, 8, 16, 25, ...
>
That is onl
On Tue, Jan 26, 2010 at 3:32 PM, Steve Howell wrote:
> Even most tiny-ish lists are wasting memory, though, according to this
> sequence:
>
> 4, 8, 16, 25, ...
>
Several operations will allocate a list of exactly the right size, wasting
no memory. In particular, a fixed-size list will always be
> From: Guido van Rossum
> Steve Howell
> wrote:
> > It seems to me that the goal of keeping lists
> > super-compact from a memory standpoint is contradicted by
> > the code in list_resize that optimistically preallocates
> > extra memory on appends.
>
> Ah, but that applies for *large* lists. A
On 1/26/2010 7:51 AM, Steve Howell wrote:
From: Nick Coghlan
Steve, I suggest creating a new issue at bugs.python.org to
track your
proposal rather than sending diffs to the list.
I was about to suggest the same thing.
Even if your final patch is not currently accepted, it will remain on
the
Adam Olsen wrote:
> This is a much better optimization than the string appending
> optimization, as it is both portable and robust.
>
> I find it shocking to change a semantic I've come to see as a core
> part of the language, but I can't come up with a rational reason to
> oppose it. The approac
On Tue, Jan 26, 2010 at 12:46 PM, Steve Howell wrote:
> It seems to me that the goal of keeping lists super-compact from a memory
> standpoint is contradicted by the code in list_resize that optimistically
> preallocates extra memory on appends.
Ah, but that applies for *large* lists. Adding 8
From: Guido van Rossum
>
> So here's how you can fix it: go to "Edit Issue" and change
> the
> "Base:" field to the following:
>
> http://svn.python.org/view/*checkout*/python/trunk/
>
I just deleted the issue altogether for now, since the preferred approach is to
use a pointer, and that's gon
On Tue, Jan 26, 2010 at 11:36 AM, Steve Howell wrote:
> --- On Tue, 1/26/10, Guido van Rossum wrote:
>
>> From: Guido van Rossum
>> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
>> To: "Steve Howell"
>> Cc: "Nick Cogh
--- On Tue, 1/26/10, Guido van Rossum wrote:
> From: Guido van Rossum
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Steve Howell"
> Cc: "Nick Coghlan" , python-dev@python.org
> Date: Tuesday, January 26, 2010, 11:17 AM
On Tue, Jan 26, 2010 at 10:01 AM, Steve Howell wrote:
> The patch is now on Rietveld.
>
> http://codereview.appspot.com/194083/show
>
> I wsa getting HTTP errors for certain operations, like trying to publish
> comments, but I am able to see the patch there.
Hey Steve,
You seem to be using Riet
On Mon, Jan 25, 2010 at 23:57, Terry Reedy 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
The patch is now on Rietveld.
http://codereview.appspot.com/194083/show
I wsa getting HTTP errors for certain operations, like trying to publish
comments, but I am able to see the patch there.
Here is the issue tracker link:
http://bugs.python.org/issue7784
Here is a rough draft of a proposal
On approximately 1/26/2010 1:27 AM, came the following characters from
the keyboard of Stefan Behnel:
Michael Foord, 26.01.2010 01:14:
How great is the complication? Making list.pop(0) efficient sounds like
a worthy goal, particularly given that the reason you don't use it is
because you *kn
--- On Tue, 1/26/10, Antoine Pitrou wrote:
> From: Antoine Pitrou
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: python-dev@python.org
> Date: Tuesday, January 26, 2010, 12:50 AM
> Terry Reedy
> udel.edu> writes:
> >
> > Th
--- On Tue, 1/26/10, Daniel Stutzbach wrote:
> Just to be clear, when you say "all tests" do you
> mean "all of the list tests" or "the full
> Python test suite"?
>
The full suite, minus some tests that skipped on my platform. The last patch I
posted was broken on test_sys.py, but I have si
On Tue, Jan 26, 2010 at 1:17 AM, Steve Howell wrote:
> Ok, I fixed the obvious segfaults, and I am now able to pass all the tests
> on my debug build. A new diff is attached.
>
Just to be clear, when you say "all tests" do you mean "all of the list
tests" or "the full Python test suite"?
--
Da
> From: Nick Coghlan
>
> Steve, I suggest creating a new issue at bugs.python.org to
> track your
> proposal rather than sending diffs to the list.
Agreed. After sending out the second, still slightly broken diff, I realized
that I probably needed to read up on the process. You can find the
Steve Howell wrote:
> Ok, I fixed the obvious segfaults, and I am now able to pass all the
> tests on my debug build. A new diff is attached.
Steve, I suggest creating a new issue at bugs.python.org to track your
proposal rather than sending diffs to the list. Putting the patch code
up on Rietvel
--- On Tue, 1/26/10, Stefan Behnel wrote:
> From: Stefan Behnel
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: python-dev@python.org
> Date: Tuesday, January 26, 2010, 1:27 AM
> Michael Foord, 26.01.2010 01:14:
> > How great is the complicati
Michael Foord, 26.01.2010 01:14:
> How great is the complication? Making list.pop(0) efficient sounds like
> a worthy goal, particularly given that the reason you don't use it is
> because you *know* it is inefficient
I agree. Given a programmer the insight that lists are implemented as
arrays in
Terry Reedy udel.edu> writes:
>
> The idea that CPython should not be improved because it would spoil
> programmers strikes me as a thin, even desparate objection. One could
> say that same thing about the recent optimization of string += string so
> that repeated concats are O(n) instead of O
--- On Mon, 1/25/10, Steve Howell wrote:
> From: Steve Howell
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Michael Foord" , "Nick Coghlan"
>
> Cc: "Christian Heimes" , python-dev@python.org
> Date: Monday, Janu
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 fo
I made enough of a patch to at least get a preliminary benchmark.
The program toward the bottom of this email runs over 100 times faster with my
patch. The patch still has a ways to go--I use a very primitive scheme to
reclaim orphan pointers (1000 at a time) and I am still segfaulting when
re
--- On Mon, 1/25/10, Nick Coghlan wrote:
> From: Nick Coghlan
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Michael Foord"
> Cc: "Christian Heimes" , python-dev@python.org
> Date: Monday, January 25, 2010, 6:32 PM
> Michae
Michael Foord wrote:
> On 26/01/2010 00:28, Christian Heimes wrote:
>> I favor this approach over an integer offset because doesn't change the
>> semantic of ob_item.
>>
> Well, on the face of it this doesn't sound like a huge increase in
> complexity. Not that I'm qualified to judge.
Christia
On 25Jan2010 12:34, Steve Howell wrote:
| From: Raymond Hettinger
| > 1) To many things in the Python world rely on
| > the current implementation of lists. It's not
| > worth breaking third-party extensions, tools like psyco,
| > work on unladen swallow, and other implementations of Python
| >
--- On Mon, 1/25/10, Christian Heimes wrote:
> From: Christian Heimes
> Michael Foord wrote:
> > How great is the complication? Making list.pop(0)
> efficient sounds like
> > a worthy goal, particularly given that the reason you
> don't use it is
> > because you *know* it is inefficient (so the
On Mon, Jan 25, 2010 at 7:32 PM, Michael Foord
wrote:
> On 26/01/2010 00:28, Christian Heimes wrote:
>>
>> Michael Foord wrote:
>>
>>>
>>> How great is the complication? Making list.pop(0) efficient sounds like
>>> a worthy goal, particularly given that the reason you don't use it is
>>> because y
On 26/01/2010 00:28, Christian Heimes wrote:
Michael Foord wrote:
How great is the complication? Making list.pop(0) efficient sounds like
a worthy goal, particularly given that the reason you don't use it is
because you *know* it is inefficient (so the fact that you don't use it
isn't eviden
Michael Foord wrote:
> How great is the complication? Making list.pop(0) efficient sounds like
> a worthy goal, particularly given that the reason you don't use it is
> because you *know* it is inefficient (so the fact that you don't use it
> isn't evidence that it isn't wanted - merely evidence
--- On Mon, 1/25/10, Benjamin Peterson wrote:
> From: Benjamin Peterson
> Subject: Re: [Python-Dev] patch to make list.pop(0) work in O(1) time
> To: "Steve Howell"
> Cc: python-dev@python.org
> Date: Monday, January 25, 2010, 3:15 PM
> 2010/1/25 Steve Howell :
On 26/01/2010 00:12, Christian Heimes wrote:
Benjamin Peterson wrote:
Yes, but in either of these cases is there an excellent performance
improvement to be gained and is it worth the complexity of your
optimization? I think not.
Me, too.
I already tried to explain Steve that I have us
Benjamin Peterson wrote:
> Yes, but in either of these cases is there an excellent performance
> improvement to be gained and is it worth the complexity of your
> optimization? I think not.
Me, too.
I already tried to explain Steve that I have used list.pop(0) in very
few cases during my seven yea
--- On Mon, 1/25/10, Mike Klaas wrote:
> From: Mike Klaas
> > On Mon, Jan 25, 2010 at 1:22 PM, Steve Howell
> wrote:
> >>
> >> I haven't completely worked out the best strategy
> to eventually release
> >> the memory taken up by the pointers of the
> unreleased elements, but the
> >> worst case
On Mon, Jan 25, 2010 at 11:32 AM, Daniel Stutzbach
wrote:
> On Mon, Jan 25, 2010 at 1:22 PM, Steve Howell wrote:
>>
>> I haven't completely worked out the best strategy to eventually release
>> the memory taken up by the pointers of the unreleased elements, but the
>> worst case scenario is that
2010/1/25 Steve Howell :
>> From: Raymond Hettinger
>>
>> On Jan 25, 2010, at 12:36 PM, Steve Howell wrote:
>>
>> >
>> > Deque does not support all the operations that list
>> does. It is also roughly twice as slow for accessing
>> elements (I've measured it).
>>
>>
>> ISTM that apps that want to
> From: Raymond Hettinger
>
> On Jan 25, 2010, at 12:36 PM, Steve Howell wrote:
>
> >
> > Deque does not support all the operations that list
> does. It is also roughly twice as slow for accessing
> elements (I've measured it).
>
>
> ISTM that apps that want to insert or pop from the front of
> l
On Jan 25, 2010, at 12:36 PM, Steve Howell wrote:
>
> Deque does not support all the operations that list does. It is also roughly
> twice as slow for accessing elements (I've measured it).
ISTM that apps that want to insert or pop from the front of list are also apps
that don't care about
--- On Mon, 1/25/10, Benjamin Peterson wrote:
> 2010/1/25 Steve Howell :
> > I am interested in creating a patch to make deleting
> elements from the front
> > of Python list work in O(1) time by advancing the
> ob_item pointer.
>
> How about just using a deque?
Deque does not support all the op
From: Raymond Hettinger
> On Jan 25, 2010, at 11:22 AM, Steve Howell
> wrote:
> I
> am interested in creating a patch to make deleting elements
> from the front of Python list work in O(1) time by advancing
> the ob_item pointer.
>
> +1 on doing whatever experiments you feel like
> doing-1 on putt
--- On Mon, 1/25/10, Daniel Stutzbach wrote:
> FWIW, for a long-running FIFO queue, it's critical to
> release some of the memory along the way, otherwise the
> amount of wasted memory is unbounded.
>
Somebody implementing a long-running FIFO queue should actually be using deque
instead of lis
2010/1/25 Steve Howell :
> I am interested in creating a patch to make deleting elements from the front
> of Python list work in O(1) time by advancing the ob_item pointer.
How about just using a deque?
--
Regards,
Benjamin
___
Python-Dev mailing lis
On Jan 25, 2010, at 11:22 AM, Steve Howell wrote:
> I am interested in creating a patch to make deleting elements from the front
> of Python list work in O(1) time by advancing the ob_item pointer.
+1 on doing whatever experiments you feel like doing
-1 on putting something like this in the cor
On Mon, Jan 25, 2010 at 1:22 PM, Steve Howell wrote:
> I haven't completely worked out the best strategy to eventually release the
> memory taken up by the pointers of the unreleased elements, but the worst
> case scenario is that the unused memory only gets wasted until the time that
> the list
98 matches
Mail list logo
