39 lines
1.2 KiB
Plaintext
39 lines
1.2 KiB
Plaintext
From: moshez at math.huji.ac.il (Moshe Zadka)
|
|
Date: Mon, 26 Apr 1999 01:17:48 +0300
|
|
Subject: Time complexity of dictionary insertions
|
|
In-Reply-To: <000901be8e11$b4842560$f09e2299@tim>
|
|
References: <glmpv4vnhh6.fsf@caffeine.mitre.org> <000901be8e11$b4842560$f09e2299@tim>
|
|
Message-ID: <Pine.SUN.3.95-heb-2.07.990426011503.1244D-100000@sunset.ma.huji.ac.il>
|
|
X-UID: 64
|
|
|
|
On Sat, 24 Apr 1999, Tim Peters wrote:
|
|
|
|
> [someone asks about the time complexity of Python dict insertions]
|
|
>
|
|
> [Tim replies]
|
|
> > 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).
|
|
|
|
<snipped discussion whether Amortized Constant Time is a C++/STL/CS
|
|
concept>
|
|
|
|
> This one-ups-man-ship would be a lot cuter if Python's dict insertion were
|
|
> in fact amortized constant time <0.9 wink>. It's not, and the answer I gave
|
|
> doesn't imply that it is. Insertion in STL hashed associative containers
|
|
> isn't ACT either.
|
|
|
|
This is interesting. What is the WCS behaviour of Python dicts?
|
|
|
|
but-it-doesn't-really-matter-'cause-it-takes-finite-time-anyway-ly y'rs,
|
|
Z.
|
|
|
|
--
|
|
Moshe Zadka <mzadka at geocities.com>.
|
|
QOTD: What fun to me! I'm not signing permanent.
|
|
|
|
|
|
|
|
|
|
|