If one doesn't care about slicing, the obvious implementation using a dictionary and two counters works great for a deque with random indexing. Well... except for the doubling in memory usage.
- Josiah On Wed, Jan 27, 2010 at 4:15 PM, Raymond Hettinger <raymond.hettin...@gmail.com> wrote: > > On Jan 27, 2010, at 3:55 PM, Maciej Fijalkowski wrote: > > 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. > > > Hi. > > For small dequeues (smaller than a constant), you have to have O(1) > operations, by definition :-) > > > LOL, of course that's true. > What I meant though is that for deques that fit in a single block, the > lookup is direct (no searching). > For multi-block deques, the code traverses links (one link for every 62 > elements). > So the indexing time would be i//62 + 1. However , if i is more than > half-way through the deque, the search starts from the other end. So the > indexing time is: min(i, len(d)-i)//2 + 1. > It's still O(n) for large deques, but the constant factor isn't large and it > is fast for small deques, and always O(1) for accesses near either end (i.e. > d[0] and d[-1] are direct lookups with no searching) -- those cases are > typical. > What use case requires a large deque, growing on end, shrinking on the > other, and needs O(1) random access to elements in the middle? Stored > indicies lose their meaning whenever the deque mutates. > > Raymond > _______________________________________________ > 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/josiah.carlson%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