undefined | Better HN

0 pointsvikinghckr6y ago0 comments

Problem with bisect is that bisect.insort() insertion is O(n), whereas C++ set.insert() is O(log n).

0 comments

3 comments · 2 top-level

stfwn6y ago· 1 in thread

It is somewhat strange that Python does not have a binary tree in the standard library. I also couldn't find any discussion on the topic either. It might be a nice contribution.

Edit: it was coined a few times on the python-ideas mailing list but it seems it just died a silent death there. https://mail.python.org/archives/list/python-ideas@python.or...

carapace6y ago

I suspect it's because you rarely need them in Python because the existing built-ins (list, tuple, dict, set) usually work well enough for a given job, or you're already using e.g. Pandas or something.

FWIW: https://github.com/calroc/xerblin/blob/master/xerblin/btree....

carapace6y ago

With respect, I think you're worng about that.

> The module [bisect] ... uses a basic bisection algorithm to do its work.

~ https://docs.python.org/3.0/library/bisect.html

> Binary search runs in logarithmic time in the worst case, making O(log n) comparisons...

~ https://en.wikipedia.org/wiki/Binary_search_algorithm

edit: Unless you mean moving the data?

j / k navigate · click thread line to collapse