[Zope-dev] Is object lookup in a container O(log n)?

[Kevin Dangoor]

----- Original Message -----
From: "Jim Fulton" <jim@digicool.com>
To: "Kevin Dangoor" <kid@kendermedia.com>
Cc: <zope-dev@zope.org>
Sent: Tuesday, February 08, 2000 9:53 AM
Subject: Re: [Zope-dev] Is object lookup in a container O(log n)?


> Folders use Python dictionaries, which use hashing.  This is
> much faster than O(log n), if the container is already
> loaded in memory.  One problem with using Python dictionaries
> is that for *really* big (hundreds of thousands of objects)
> containers, you have to have have alot of information in memory
> and reloading the container into memory if O(n).

Ahh. I hadn't realized that Python dictionaries use hashing. That makes
sense for most applications.

I assume an ObjectManager ZClass will be the same, performance-wise, as a
Folder. Do you have any idea where the threshold is as far as the hash table
is concerned? For my own application, I'd be looking at 1000-2000 objects
right now. For others (since this is code I'm thinking of releasing), they
could be looking at much more.

I can consider doing something like breaking off the first two characters of
the identifiers and creating containers with those characters as an id and
splitting the objects up in those folders.

> We plan, in the future, to provide folder-like objects
> suited to very large collections. These will be based on
> BTrees and will be O(log n) for lookup.  Catalog uses BTrees
> and is O(log n) for searches.

Sounds good...

Kevin