[Inada Naoki <songofaca...@gmail.com>] > 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.
Which is a good point. I added a lot more, though, because Wes didn't even mention queues in his question: [Wes Turner <wes.tur...@gmail.com>] >>>> How slow and space-inefficient would it be to just implement the set >>>> methods >>>> on top of dict? I can't guess what he was _really_ asking about, so now he's got lots of answers ;-) > 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. To flesh this out, the FIFO queue entries are all together in a contiguous vector, with no "holes" in the middle. Pushing a new item appends "to the right" (higher index in the vector), while popping an item leaves "a hole" at the left. But there are no holes "in the middle" in this case. So the first real entry is at a higher index with every pop, but iteration starts at index 0 every time. The more pops there are, the more holes iteration has to skip over, one at a time, to find the first real entry remaining. Until pushing a new item would fall off the right end of the vector. Then the table is rebuilt from scratch, moving all the real entries to form a contiguous block starting at index 0 again. >> 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), Yes. > 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). For the specific case of FIFO queues, sure. In general, though, "O(1) period". is more desirable than "amortized O(1)". This is especially true when sets get very large. > Current dict is not optimized for queue usage. Nor should it be:-) That's what collections.deque is for, pushes and pops, at both ends, always time O(1) period. No holes, no internal rearrangements, and O(1) "wasted" space. _______________________________________________ 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/5VDU52JX2GFM6546W6FCFKXIODDAQKP4/ Code of Conduct: http://python.org/psf/codeofconduct/
