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/archive%40mail-archive.com
