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

Reply via email to