Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 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) operations, by definition :-) LOL, of course that's true. What I meant though is that for deques that fit in a single block, the lookup is direct (no searching). For multi-block deques, the code traverses links (one link for every 62 elements). So the indexing time would be i//62 + 1. However , if i is more than half-way through the deque, the search starts from the other end. So the indexing time is: min(i, len(d)-i)//2 + 1. It's still O(n) for large deques, but the constant factor isn't large and it is fast for small deques, and always O(1) for accesses near either end (i.e. d[0] and d[-1] are direct lookups with no searching) -- those cases are typical. What use case requires a large deque, growing on end, shrinking on the other, and needs O(1) random access to elements in the middle? Stored indicies lose their meaning whenever the deque mutates. Raymond ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/josiah.carlson%40gmail.com ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
[Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 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 believe the memory structure is already larger than that for a basic list. Reworking the way that extra space is used may be a more fruitful strategy than trying to convince anyone that it is worth changing the list implementation for this corner case. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --- ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 agree that it kind of pushes the boundary of sanity. :) 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 believe the memory structure is already larger than that for a basic list. Reworking the way that extra space is used may be a more fruitful strategy than trying to convince anyone that it is worth changing the list implementation for this corner case. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --- ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/alex.gaynor%40gmail.com 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 like skip-lists that have O(log n) arbitrary lookups though. If someone could make an O(1) linked-list I'd love to see it :) Alex -- I disapprove of what you say, but I will defend to the death your right to say it. -- Voltaire The people's good is the highest law. -- Cicero Code can always be simpler than you think, but never as simple as you want -- Me ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 believe the memory structure is already larger than that for a basic list. The memory structure is a linked list of blocks, where each block can hold several elements. As a linked list, the current structure would have O(n) random access. A few years back, I had proposed an alternative way of implementing deque, that would allow O(1) random access: http://mail.python.org/pipermail/python-dev/2007-November/075242.html It's essentially identical to Steve's proposal for list, except that I made the array circular, so element i is at position items[(start + i) % len]. That way it doesn't have to regularly allocate and deallocate memory for an approximately-fixed-length FIFO queue (which Steve's list will need to do). Raymond's objections are here: http://mail.python.org/pipermail/python-dev/2007-November/075244.html -- Daniel Stutzbach, Ph.D. President, Stutzbach Enterprises, LLC http://stutzbachenterprises.com ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 moving targets. I know on no real-world code that every uses this. 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. Is this a real need or a made-up use case by someone hell-bent on changing a core data structure? Raymond On Jan 27, 2010, at 1:50 PM, Nick Coghlan 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 agree that it kind of pushes the boundary of sanity. :) 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 believe the memory structure is already larger than that for a basic list. Reworking the way that extra space is used may be a more fruitful strategy than trying to convince anyone that it is worth changing the list implementation for this corner case. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --- ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/raymond.hettinger%40gmail.com ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 like skip-lists that have O(log n) arbitrary lookups though. If someone could make an O(1) linked-list I'd love to see it :) Yeah, you're right - I was completely misremembering how deque worked. I've come across a data structure implementation similar to the one Steve is proposing somewhere before, but deque obviously isn't it. Cheers, Nick. -- Nick Coghlan | ncogh...@gmail.com | Brisbane, Australia --- ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 arbitrary
elements of a deque.
I haven't looked at the deque code in a long time, but I believe the
memory structure is already larger than that for a basic list.
The memory structure is a linked list of blocks, where each block can hold
several elements. As a linked list, the current structure would have O(n)
random access.
A few years back, I had proposed an alternative way of implementing deque,
that would allow O(1) random access:
http://mail.python.org/pipermail/python-dev/2007-November/075242.html
It's essentially identical to Steve's proposal for list, except that I made
the array circular, so element i is at position items[(start + i) % len].
That way it doesn't have to regularly allocate and deallocate memory for an
approximately-fixed-length FIFO queue (which Steve's list will need to do).
Raymond's objections are here:
http://mail.python.org/pipermail/python-dev/2007-November/075244.html
I'm curious whether something similar could be added to python as a
separate data structure, but for use with strings (bytes in 3.x)? I
recently had to implement a circular FIFO buffer for storing
characters read from a serial line. I basically needed O(1) append,
removal from the front, and lookup/slice in the middle. For example:
x = Buffer(16)
x.write('abcde')
x[1:-1]
'bcd'
x.read(2)
'ab'
len(x)
3
x.read()
'cde'
The backing structure was array.array('B'), which worked pretty well
for my needs. It was more memory-efficient, but the problem is that
implementing all of these operations in python was a bit of a
performance hit.
You could easily adapt this to a dynamic or fixed-size array and
change the interface for working with both ends of the data. By the
way, if you keep the array size as a power of two, you can replace the
relatively expensive modulus operations with bitwise and.
- Max
___
Python-Dev mailing list
Python-Dev@python.org
http://mail.python.org/mailman/listinfo/python-dev
Unsubscribe:
http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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 ___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
Re: [Python-Dev] O(1) random access to deque? (Re: patch to make list.pop(0) work in O(1) time)
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) operations, by definition :-) LOL, of course that's true. What I meant though is that for deques that fit in a single block, the lookup is direct (no searching). For multi-block deques, the code traverses links (one link for every 62 elements). So the indexing time would be i//62 + 1. However , if i is more than half-way through the deque, the search starts from the other end. So the indexing time is: min(i, len(d)-i)//2 + 1. It's still O(n) for large deques, but the constant factor isn't large and it is fast for small deques, and always O(1) for accesses near either end (i.e. d[0] and d[-1] are direct lookups with no searching) -- those cases are typical. What use case requires a large deque, growing on end, shrinking on the other, and needs O(1) random access to elements in the middle? Stored indicies lose their meaning whenever the deque mutates. Raymond___ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com
