On Sat, Dec 21, 2019 at 3:17 AM Tim Peters <[email protected]> wrote:
>
> [Wes Turner <[email protected]>]
> >> How slow and space-inefficient would it be to just implement the set
> >> methods
> >> on top of dict?
>
> [Inada Naoki <[email protected]>]
> > 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.
I read this thread, and I understand all of them.
I just meant the performance of the next(iter(D)) is the most critical part
when you implement orderdset on top of the current dict and use it as a queue.
This code should be O(N), but it's O(N^2) if q is implemented on top
of the dict.
while q:
item = q.popleft()
Sorry for the confusion.
>
> 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.
It is a bit misleading. If "the cardinality of the set" means len(S),
set requires the rebuild in low frequency if the its items are random.
Anyway, it is a smaller problem than next(iter(D)) because of the
amortized cost is O(1).
Current dict is not optimized for queue usage.
Regards,
--
Inada Naoki <[email protected]>
_______________________________________________
Python-Dev mailing list -- [email protected]
To unsubscribe send an email to [email protected]
https://mail.python.org/mailman3/lists/python-dev.python.org/
Message archived at
https://mail.python.org/archives/list/[email protected]/message/DFJQOW225OSRPFDHBJ3UBYRRMZ52AXDH/
Code of Conduct: http://python.org/psf/codeofconduct/
