[prev in list] [next in list] [prev in thread] [next in thread] 

List:       python-dev
Subject:    Re: [Python-Dev] O(1) random access to deque? (Re: patch to make
From:       Josiah Carlson <josiah.carlson () gmail ! com>
Date:       2010-01-28 23:39:37
Message-ID: e6511dbf1001281539h3aaccf6ud7a504f68e0664af () mail ! gmail ! com
[Download RAW message or body]

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.hettinger@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/python-dev%40progressive-comp.com

[prev in list] [next in list] [prev in thread] [next in thread]