search

DanielStutzbach / blist

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

O(log n) add and remove for sorted* #31

Open matteodellamico opened 13 years ago

matteodellamico commented 13 years ago

A C implementation of sorted* could give O(log n) add and remove methods. It remains to be seen if that would really boost performance, as the number of comparisons is already O(log n) and the tree can't be that tall anyway -- max height is now 16 in the C source.

grantjenks commented 9 years ago

@matteodellamico Have you tried the pure-Python SortedContainers module? For sorted* add and remove it's much faster than blist.