Message 396972 - Python tracker

➜

This issue tracker has been migrated to GitHub, and is currently read-only.
For more information, see the GitHub FAQs in the Python's Developer Guide.

Author	methane
Recipients	Dennis Sweeney, danielfleischman, methane, rhettinger, serhiy.storchaka
Date	2021-07-05.08:23:54
SpamBayes Score	-1.0
Marked as misclassified	Yes
Message-id	<1625473434.72.0.678414929805.issue44555@roundup.psfhosted.org>
In-reply-to

Content
iterating whole over the dict is O(n) where n is the historical max size of the dict. On the other hand, there are no guarantee about `next(iter(d))` is O(1). The guarantee is O(n) at worst case. And your example is the worst case. So this is not a bug. As Dennis wrote, we won't add doubly linked list to the dict only for this purpose. OrderedDict is for the use case. I don't have any better idea than bpo-32623. More ideas are welcome.

iterating whole over the dict is O(n) where n is the historical max size of the dict.

On the other hand, there are no guarantee about `next(iter(d))` is O(1). The guarantee is O(n) at worst case. And your example is the worst case. So this is not a bug.

As Dennis wrote, we won't add doubly linked list to the dict only for this purpose.
OrderedDict is for the use case.

I don't have any better idea than bpo-32623. More ideas are welcome.

History
Date	User	Action	Args
2021-07-05 08:23:54	methane	set	recipients: + methane, rhettinger, serhiy.storchaka, Dennis Sweeney, danielfleischman
2021-07-05 08:23:54	methane	set	messageid: <1625473434.72.0.678414929805.issue44555@roundup.psfhosted.org>
2021-07-05 08:23:54	methane	link	issue44555 messages
2021-07-05 08:23:54	methane	create