Re: ANNOUNCE: python-apt

[Antti-Juhani Kaijanaho <gaia@iki.fi>]

On Mon, Feb 21, 2000 at 08:39:44AM -0500, Daniel Burrows wrote:
>   Well, you rarely want to access an arbitrary member in C++.  But the thing
> that concerned me was that the Python interface *appears* to be O(1) even though
> it's actually O(n).

You can make this amortized O(1) (no, I'm not going to analyze it, this
is a gut feeling) by doing some dynamic programming, assuming that one
usually makes at least one pass over the whole sequence (in any order).

Have an auxiliary table holding the C++ iterators.  Initialize the array
to hold empty values (say, end() iterators) in its buckets.

Handle the index zero case as a special case.  When a user asks for the
i'th element in the sequence, check the aux table.  If the i'th entry is
nonempty, use that iterator.  Otherwise retrieve the (i-1)'th iterator
using this algorithm recursively, apply ++ to it and save the result in
the i'th bucket in the aux table, and use that iterator.

The recursion in that algorithm should be easy to convert into iteration,
if necessary.

We assume that the iterators are not invalidated by this algorithm or
by the user between invocations of this algorithm.  (If an operation
invalidates iterators, it must flush the aux table.)

-- 
%%% Antti-Juhani Kaijanaho % gaia@iki.fi % http://www.iki.fi/gaia/ %%%

                                  ""
                             (John Cage)