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
