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
