55 lines
1.7 KiB
Plaintext
55 lines
1.7 KiB
Plaintext
From: tim_one at email.msn.com (tim_one at email.msn.com)
|
|
Date: Thu, 22 Apr 1999 20:19:48 GMT
|
|
Subject: Time complexity of dictionary insertions
|
|
References: <371F2125.BEC5F892@fzi.de>
|
|
Message-ID: <7fo08u$4j2$1@nnrp1.dejanews.com>
|
|
Content-Length: 1417
|
|
X-UID: 89
|
|
|
|
In article <371F2125.BEC5F892 at fzi.de>,
|
|
Oliver Ciupke <ciupke at fzi.de> wrote:
|
|
> As I understood from the Python documentation, dictionaries are
|
|
> implemented as extensible hash tables.
|
|
|
|
Yes.
|
|
|
|
> What I didn't find either in the references or in the FAQ is: what is
|
|
> the actual time complexity for an insertion into a dictionary?
|
|
|
|
Min O(1), Max O(N), Ave O(1). If the hash function is doing a terrible job
|
|
(e.g. maps every key to the same hash value), make those all O(N).
|
|
|
|
> Do the old contents (probably references)
|
|
|
|
Yes.
|
|
|
|
> have to be copied when extending (doubling?)
|
|
|
|
Approximately doubling, yes.
|
|
|
|
> the dictionary?
|
|
|
|
Right.
|
|
|
|
> I guess updates and deletions have constand complexity, right?
|
|
|
|
No; see above for insertion. Deletion is O(1) always, because Python doesn't
|
|
try to shrink the table by magic (if you stick in a million keys and then
|
|
delete them, the table will still contain a million "this entry isn't being
|
|
used" markers).
|
|
|
|
> If the complexity of insertion is something like n*log(n), does anyone
|
|
> know measurements "how linear" the real measured times are?
|
|
|
|
In practice, with a non-pathological hash function + key distribution combo,
|
|
insertion & deletion act like O(1) on average.
|
|
|
|
for-more-details-see-the-source-code<wink>ly y'rs - tim
|
|
|
|
-----------== Posted via Deja News, The Discussion Network ==----------
|
|
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
|
|
|
|
|
|
|
|
|