Author inada.naoki
Recipients arigo, aronacher, eric.snow, inada.naoki, rhettinger, serhiy.storchaka
Date 2017-09-12.07:27:13
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <>
In-reply-to <>
> Eric Snow added the comment:
> On Sun, Sep 10, 2017 at 10:27 PM, Serhiy Storchaka
> <> wrote:
>> Note that mixed insertion and deletion is worst-case O(n) in current implementation.
> Could you elaborate?  Note that every operation of the current
> implementation matches the complexity of the Python implementation.

It means rebuilding hash table to clean up dummy entries.
So, even when dict size is not increasing, remove + insert loop has
worst case O(n), amortized O(1) complexity.
Date User Action Args
2017-09-12 07:27:13inada.naokisetrecipients: + inada.naoki, arigo, rhettinger, aronacher, eric.snow, serhiy.storchaka
2017-09-12 07:27:13inada.naokilinkissue31265 messages
2017-09-12 07:27:13inada.naokicreate