Ordered Sets

Raymond Hettinger python at rcn.com
Fri Mar 20 18:08:48 CET 2009


[Aahz]
> The doubly-linked list part is what's sick and perverted.

The doubly-linked list part is what gives it big-oh running
times the same as regular sets.  If the underlying sequence
is stored as a list, then deletion goes from O(1) to O(n).
If the insertion times are recorded in a dictionary, then
the insertion order has to be sorted prior to iteration
which makes iteration go from O(n) to O(n log n).


Raymond






More information about the Python-list mailing list