Daniel Fleischman added the comment:
Hey Raymond,
> "Changing the dict implementation to a linked list would make your case
perform better but would make most users worse off."
Is there any standard benchmark? I would like to implement my idea, as I
think that it is very unlike
Daniel Fleischman added the comment:
Thank you for your reply. I didn't know that this was the expected behavior
(found it at https://wiki.python.org/moin/TimeComplexity):
"For these operations, the worst case n is the maximum size the container ever
achieved, rather than just the cu
Daniel Fleischman added the comment:
Thank you again, Dennis.
I would disagree with your conclusion for mainly 3 reasons:
1. The linked list proposal would increase the memory usage by 2 Py_ssize_t per
entry, plus another 2 for the whole dictionary. I don't think this is an
overwhelming
Daniel Fleischman added the comment:
I think the idea of augmenting the struts to maintain a linked list of elements
together with periodically shrinking on removal would solve both time and space
issues, right?
Space will be always linear, and operations would still be constant amortized
Daniel Fleischman added the comment:
Please find attached a more complete example of the issue I am reporting.
tl;dr: I can make `sum(d.values())` run in O(maximum_size_in_d's_history)
instead of O(len(d)), even when len(d) == 1.
The linked list approach would work in terms of making
Daniel Fleischman added the comment:
Thank you for your message!
I'm not particularly looking for an implementation, I was just surprised by
this behavior.
It can get even worse. Consider this example:
```
d = large_dict()
# remove all but one element of d, runs in quadratic time
Daniel Fleischman added the comment:
The linked list solution is not as easy to implement as I expected, because of
insertions. :(
--
___
Python tracker
<https://bugs.python.org/issue44
New submission from Daniel Fleischman :
The following code takes quadratic time on the size of the dictionary passed,
regardless of the dictionary (explanation below):
```
def slow_dictionary(d):
while len(d) > 0:
# Remove first element
key = next(iter(d))
de
