On Sat, Dec 21, 2019 at 3:17 AM Tim Peters <tim.peters@gmail.com> wrote:
[Wes Turner <wes.turner@gmail.com>]
How slow and space-inefficient would it be to just implement the set methods on top of dict?
[Inada Naoki <songofacandy@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.
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 <songofacandy@gmail.com>