[Date Prev][Date Next] [Thread Prev][Thread Next] [Date Index] [Thread Index]

Re: ANNOUNCE: python-apt

On Sun, Feb 20, 2000 at 05:13:34PM -0500, Fabien Ninoles was heard to say:
> On Mon, Feb 14, 2000 at 10:01:45AM -0500, Daniel Burrows wrote:
> > On Mon, Feb 14, 2000 at 08:39:43AM -0500, Daniel Burrows was heard to say:
> > >   Another thing I'm wondering about is the iterators -- right now I've wrapped
> > > them pretty straightforwardly, substituting a 'next' member for the increment
> > > operation.  I could make them into sequences (as you suggested with the
> > > version list), but this has the drawback that accessing an arbitrary member
> > > in Python would be O(n) and iterating over the list in a 'for' loop would
> > > be O(n^2) (normal Python sequences are just arrays, so it's expected that
> > > those operations will be O(1) and O(n))  OTOH, "for i in package.versions" is
> > > a pretty nice way to do things.
> The drawback is inherent to the libapt library, IMHO (don't you have the same
> for accessing an arbitrary member with the C++ implementation?). However, with

  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).

> sequencing in Python, you can assume that the list will be access through an
> iteration like manner. So, I suggest you to cache both the index and the next
> object last access. In most case (at least in case where performance are important),
> your will only have to return the next.next pointer:

  Hmmm.  I thought about doing this, but I don't like it -- it feels like a
hack.  What I've currently actually done is to make pkg.versions return a tuple
of the available versions of the package; this is fine for iteration, although
arbitrary accesses are still O(n)..but it would be trivial to cache the
tuple inside the Python package object if I need to (I think that, as Jason
observed, that might be going a little overboard though :) )

> Hope this help.

   Thanks for the suggestion,

"(You see, the best way to solve a problem is to rigorously define it in terms
 of other people's problems and then run away quickly.)"
  -- Roland McGrath <frob@debian.org>

Reply to: