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
