[Wes Turner <wes.tur...@gmail.com>]
>> How slow and space-inefficient would it be to just implement the set methods
>> on top of dict?
[Inada Naoki <songofaca...@gmail.com>]
> Speed: Dict doesn't cache the position of the first item. Calling
> next(iter(D)) repeatedly is O(N) in worst case.
> ...
See also Raymond's (only) message in this thread. We would also lose
low-level speed optimizations specific to the current set
implementation. And we would need to define what "insertion order"
_means_ for operators (union, intersection, symmetric difference) that
build a new set out of other sets without a user-level "insert" in
sight. However that's defined, it may constrain possible
implementations in ways that are inherently slower (for example, may
require the implementation to iterate over the larger operand where
they currently iterate over the smaller).
And the current set implementation (like the older dict
implementation) never needs to "rebuild the table from scratch" unless
the cardinality of the set keeps growing. As Raymond telegraphically
hinted, the current dict implementation can, at times, in the presence
of deletions, require rebuilding the table from scratch even if the
dict's maximum size remains bounded.
That last can't be seen directly from Python code (rebuilding the
table is invisible at the Python level). Here's a short example:
d = dict.fromkeys(range(3))
while True:
del d[0]
d[0] = None
Run that with a breakpoint set on dictobject.c's `dictresize()`
function. You'll see that it rebuilds the table from scratch every
3rd time through the loop. In effect, for the purpose of deciding
whether it needs to rebuild, the current dict implementation sees no
difference between adding a new element and deleting an existing
element Deleting leaves behind "holes" that periodically have to be
squashed out of existence so that insertion order can be maintained in
a dead simple way upon future additions.
_______________________________________________
Python-Dev mailing list -- python-dev@python.org
To unsubscribe send an email to python-dev-le...@python.org
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/python-dev@python.org/message/BVCDKT5ULY324RZATMCEFGAMYOBJFHIZ/
Code of Conduct: http://python.org/psf/codeofconduct/
