Author inada.naoki
Recipients arigo, aronacher, eric.snow, inada.naoki, rhettinger, serhiy.storchaka
Date 2017-09-11.01:05:02
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1505091903.28.0.805560210915.issue31265@psf.upfronthosting.co.za>
In-reply-to
Content
>  I'm unclear about whether you understand and acknowledge why the doubly-linked list was chosen and what kind of workloads it supports (we didn't choose it because it was either convenient or fun, we chose it because it was an algorithmically correct way of supporting arbitrary deletion, move-to-front, move-to-back, pop-first, and pop-last operations all of which have legitimate use cases).

Arbitrary deletion: New and current implementation has same complexity, because current implementation relying on dict deletion.  Only difference is current implementation need to remove item from link list, not only dict.

move-to-front, move-to-back: Current implementation is worst case O(1) and new implementation is amortized O(1), like insertion.

pop-first, pop-last: Current implementation is worst case O(1).  New implementation is typical case (when dict is dense) O(1).  When mixed with arbitrary deletion operation (dict is sparse), it's become amortized O(1).
History
Date User Action Args
2017-09-11 01:05:03inada.naokisetrecipients: + inada.naoki, arigo, rhettinger, aronacher, eric.snow, serhiy.storchaka
2017-09-11 01:05:03inada.naokisetmessageid: <1505091903.28.0.805560210915.issue31265@psf.upfronthosting.co.za>
2017-09-11 01:05:03inada.naokilinkissue31265 messages
2017-09-11 01:05:02inada.naokicreate