Steven D'Aprano wrote:
On Fri, 20 Mar 2009 11:50:28 -0700, Scott David Daniels wrote:
Raymond Hettinger wrote:
[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).
The double-linked list part could be done with weakrefs and perhaps Aahz
would relax a bit.
I'm not sure whether Aahz's description is meant to be taken seriously,
or if there is a smiley hidden in his post. After all, doubly-linked
lists are a standard building block in data structure design.
But assuming it is meant as a serious criticism, I'm not sure that I like
the idea of using weakrefs. I think it is a feature, not a bug, that
sets, lists and dicts keep a reference to the items in them. I think it
would be bizarre if putting an item into an OrderSet meant that you
needed to put it somewhere else as well to prevent it being garbage
collected.
Or have I misunderstood the consequences of using weakrefs?
I think the idea was 2 weakrefs and 1 normal ref instead of 3 normal refs.
--
http://mail.python.org/mailman/listinfo/python-list
