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