--- 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
--- 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)?
___
--- 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, 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
> 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, 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, 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
--- 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 big practical concern is actually t
--- 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, 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
--- 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
--- 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 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
> 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.
>
>
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, 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
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 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:
> >
> > The idea that CPython should not be impro
--- 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
> 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
--- 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 complication? Making list.pop(0)
>
--- 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
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
> Michael Foord wrote:
> > On 26/01/2010 00:28,
--- 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, 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 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 o
> 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
--- 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?
Deq
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 yo
--- 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
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.
The patch will probably be rejected, but I would like to try it anyway as an
exercise in digging into the CPython source, and working through the proces
34 matches
Mail list logo
