Re: Grace and Maps (was Re: Development process in the Ada community)

[David Bolen <db3l@fitlinxx.com>]

Stephen Leake <stephen.a.leake.1@gsfc.nasa.gov> writes:

> But if I just declare a map in Python, there's no way it's guaranteed
> to be best case. So I think you are saying "yes, they live with the
> O(n) worst case, and hope for the O(1) best case, and take whatever
> they actually get".

Yes.  But it's also that a good deal of implementation effort has gone
into making the odds of the O(1) case much better than that of the
O(n) case.

> Hmm. Maybe there is a way to tell Python what the hash table size
> should be, and what hash function to use? Then I can get O(1). I
> confess to never having used either a Perl or Python map.

Python automatically maintains (grows) the hash table so that it is no
more than 2/3 full.  It is limited to a 32-bit key, and is
open-addressed, not chained.  Any "hashable" object in Python may be
used as a dictionary key - objects may implement their own hashing
function if they prefer.  The default hashing function for user
created objects is to hash to the object's location in memory.  The
built-in types tend to have type-specific tuned hashing functions.
The source indicates the algorithm was originally based on Algorithm D
from Knuth Vol. 3, Sec. 6.4.

> Well, the question is, is a "typical" map in Perl or Python "close to"
> O(n), or "close to" O(1)? Anybody have any data?

In Python it's expected to be average O(1), and only extremely rarely
O(n) (e.g., if everything hashes to the same value).  But formally the
operations are still O(n) - a lot of tuning over the course of
Python's evolution just makes the typical case much closer to best
than worst.  In particular, Python's hash table does not depend on the
randomness of the hashing function, and in fact works very well for
very regular (even monotonically increasing) hash functions.

There are some newsgroup posts over the years (look for stuff by Tim
Peters in particular), but I don't know of a formal algorithm analysis
online anywhere.  The dictionary object source itself has quite a bit
of information:

   http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/python/python/dist/src/Objects/dictobject.c?rev=HEAD

(Hoping this isn't too off-topic for an Ada group)

--
-- David
-- 
/-----------------------------------------------------------------------\
 \               David Bolen            \   E-mail: db3l@fitlinxx.com  /
  |             FitLinxx, Inc.            \  Phone: (203) 708-5192    |
 /  860 Canal Street, Stamford, CT  06902   \  Fax: (203) 316-5150     \
\-----------------------------------------------------------------------/