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

Re: ANNOUNCE: python-apt



Another of your great projects Dan. Congrats!

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
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:

__getitem__(self,index):
	if index < self.lastindex:
		self.cachenext = self.next # first one
		self.lastindex = 0
	res = self.cachenext
	for i in range(index-self.lastindex):
		res = res.next
	self.lastindex = index
	self.cachenext = res
	return res

for sure this depends on the fact that the cache doesn't change much, but I think
is it the case ;)

> > 
> >   Maybe I should provide that interface and put a warning on it that it's not
> > efficient for long lists, so (eg) iterating over the entire package cache like
> > that is a bad idea..
> 
>   Ok, I think I worked out how to do this.  A fairly standard idiom in Python
> is that dictionary-like objects provide a 'keys' method which lists all the
> keys of the object, and a 'values' method which lists the values.  I'll provide
> these for the package class, where the 'keys' are the package names and the
> 'values' are the package iterators.  Other iterator lists can probably be
> exposed as sequences; version lists (for example) are short enough that the
> efficiency hit won't matter.  (..what about the reverse depends list for
> libc6?)  In all cases, I think I'll keep the 'next' member around for people who
> want to use it.
> 
>   Daniel

Hope this help.

> 
> -- 
> Exhilaration is that feeling you get just after a great idea hits you,
> and just before you realize what is wrong with it.
> 

-- 
------------------------------------------------------------------------
Fabien Ninoles        Chevalier servant de la Dame Catherine des Rosiers
aka Corbeau aka le Veneur Gris               Debian GNU/Linux maintainer
E-mail:                                                    fab@tzone.org
WebPage:                                    http://www.tzone.org/~fabien
RSA PGP KEY [E3723845]: 1C C1 4F A6 EE E5 4D 99  4F 80 2D 2D 1F 85 C1 70
------------------------------------------------------------------------


Reply to: