If one doesn't care about slicing, the obvious implementation using a
dictionary and two counters works great for a deque with random
indexing. Well... except for the doubling in memory usage.
- Josiah
On Wed, Jan 27, 2010 at 4:15 PM, Raymond Hettinger
raymond.hettin...@gmail.com wrote:
On
Steve Howell wrote:
There is also the possibility that my initial patch can be refined by
somebody smarter than myself to eliminate the particular tradeoff.
In fact, Antoine Pitrou already suggested an approach, although I
agree that it kind of pushes the boundary of sanity. :)
I'm actually
On Wed, Jan 27, 2010 at 4:50 PM, Nick Coghlan ncogh...@gmail.com wrote:
Steve Howell wrote:
There is also the possibility that my initial patch can be refined by
somebody smarter than myself to eliminate the particular tradeoff.
In fact, Antoine Pitrou already suggested an approach, although I
On Wed, Jan 27, 2010 at 3:50 PM, Nick Coghlan ncogh...@gmail.com wrote:
I'm actually wondering if you could apply some of the implementation
strategies discussed here to grant O(1) random access to arbitrary
elements of a deque.
I haven't looked at the deque code in a long time, but I
Are you free to chat about this in IRC?
I completely unconvinced that there are use cases for
wanting face random access to the i-th element of a large deque
that is changing sizes on each end. The meaning of the
20th index changes as the data moves. It becomes pointless
to store indices to
Alex Gaynor wrote:
I don't see how that's possible. The linked list is a pretty well
known data structure and arbitrary lookups are O(n) in it. Using the
unrolled-linked-list data structure python uses you can make it faster
by a constant factor, but not O(1). There are other structures
On Wed, Jan 27, 2010 at 5:06 PM, Daniel Stutzbach
dan...@stutzbachenterprises.com wrote:
On Wed, Jan 27, 2010 at 3:50 PM, Nick Coghlan ncogh...@gmail.com wrote:
I'm actually wondering if you could apply some of the implementation
strategies discussed here to grant O(1) random access to
FWIW, deque indexing for small deques is already O(1)
and somewhat fast. You only get O(n) degradation
(with a small contant factor) on large deques.
Hi.
For small dequeues (smaller than a constant), you have to have O(1)
operations, by definition :-)
Cheers,
fijal
On Jan 27, 2010, at 3:55 PM, Maciej Fijalkowski wrote:
FWIW, deque indexing for small deques is already O(1)
and somewhat fast. You only get O(n) degradation
(with a small contant factor) on large deques.
Hi.
For small dequeues (smaller than a constant), you have to have O(1)
