[Tutor] Counting # of dictionary keys

[Bob Gailer]

--=======3B0B1409=======
Content-Type: text/plain; x-avg-checked=avg-ok-7FF3611; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 8bit

At 08:54 AM 4/16/2003 -0500, Dana Larose wrote:
> >>> len(your_dict)
>What is the complexity of this operation?  Does it run in time O(1) or
>O(n)?

This question is best answered by someone who knows the innards of the 
interpreter. I ran a test, created a dict d with almost 10,000,000 entries. 
Took several minutes. Began to exceed RAM. len(d) took no observable time. 
So I guess O(1) is the answer.

>If it doesn't, is there a O(1) method for determining the number of 
>key/value pairs in a dictionary?

You could extend dict by creating a class with dict as the superclass, and 
provide your own __len__ method to return a count. You'd also need 
__setitem__ and __delitem__ methods in which you'd inc/dec/rement a class 
property counter.

Bob Gailer
bgailer@alum.rpi.edu
303 442 2625

--=======3B0B1409=======
Content-Type: text/plain; charset=us-ascii; x-avg=cert; x-avg-checked=avg-ok-7FF3611
Content-Disposition: inline


---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.467 / Virus Database: 266 - Release Date: 4/1/2003

--=======3B0B1409=======--