search

DanielStutzbach / blist

A list-like type with better asymptotic performance and similar performance on small lists
Other
313 stars 35 forks source link

Changing an existing key in a sorteddict #13

Closed mikegraham closed 14 years ago

mikegraham commented 14 years ago

sorteddict.__setitem__ works by

self._sortedkeys.add(key)
self._map[key] = value

Where _sortedkeys is a sortedset and _map is a dict. In the case where key is already in the sorteddict and you are merely changing its value, an operation that could be performed in constant time takes O(log n) time. Code like

if key in self._map:
    self._sortedkeys.add(key)
self._map[key] = value

should improve the asymptotic performance in this case.

DanielStutzbach commented 14 years ago

Good find. Committed as 5c5bfeb8e6c84986e170a90086f57aaee65e93e8

Thanks! (sorry for the duplicate replies; meant to the issue to begin with)