[Terry Reedy]
> On enhancing list object: queue vs. deque.
>
> My general impression is that queues, while less common than stacks,
> are used enough in enough different algorithms that adding one
> implementation field to list headers so that pop(0) is an O(1)
> pointer move might be an overall win for Python. The current O(n)
> move everything every time behavior is certainly a nuisance when
> queues are needed.
See the other msgs in this thread today -- I'm not convinced that queue-like
behavior can be supported that efficiently.
> Deques, on the other hand, seem to be more a theoretical construct.
> Algorithm books include them for completeness in describing possible
> list disciplines, but generally ignore them thereafter. I am hard
> put to remember an algorithm that actually needs them. They are
> certainly much rarer than queues. So I do not think trying to make
> prepends O(1) should be considered further.
I expect that if queue-like behavior *can* be supported efficiently using an
always-contiguous vector, efficient dequeue-like behavior will fall out for
free.
> My possibly naive thought is that before reallocating, look at the
> ratio of left free to total.
I don't know what that means (neither the "left free" part nor what exactly
"total" is counting). The devil is in the details here.
> If memmove would result in as much, or perhaps nearly as much,
> over-allocation as realloc,
memmove() leaves the total number of unused slots unchanged. realloc can do
that too, or increase it by any amount, or decrease it by any amount. I
just don't know what you're trying to say ... explain how it works, step by
step, in the
q = [incoming() for i in range(1000)]
while True:
q.append(incoming())
consume(q.pop(0))
example.
> then just do that. Certainly if the ratio is small (like say .1),
> don't bother with memmove. The exact cutoff is a tuning matter.
>
> Separate issue: for best performance, one would like to be able trade
> space for time and preallocate a large enough block so that most
> append faults result in a memmove back to the left. Does the current
> builtin shrinkage discipline would allow this. Or does "q=[0]*1000;
> q[:]=[]" shrink the space for q back to nearly nothing?
Python *offers* to give 992 slots back; whether the platform realloc()
accepts the offer is up to it. In the "details are everything" department,
Python *also* creates a temp vector of length 1000, and copies all of q[:]
into it before it deletes any of q: emptying a list is a linear-time
operation, not constant-time. That's because it's not safe to decref
anything in a list while tearing it down (e.g., the list may be visible to a
__del__ method, which must not be allowed to see NULL pointers, or reclaimed
objects, in the list).
> (One might also want to do same for stack. And yes, I remember:
> 'user tuning' is a 'bad idea'. But....)
RetroSearch is an open source project built by @garambo | Open a GitHub Issue
Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo
HTML:
3.2
| Encoding:
UTF-8
| Version:
0.7.4