4 ms·
Problem with bisect is that bisect.insort() insertion is O(n), whereas C++ set.insert() is O(log n).
by vikinghckr 7y ago
Problem with bisect is that bisect.insort() insertion is O(n), whereas C++ set.insert() is O(log n).
- stfwn 7y agoIt 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.org/message/3XA5XVGOPQNOVP6PRODTARAFPFXWG3PX/ https://mail.python.org/archives/list/python-ideas@python.or...
- carapace 7y agoI 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.py https://github.com/calroc/xerblin/blob/master/xerblin/btree....
- carapace 7y agoWith 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 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 https://en.wikipedia.org/wiki/Binary_search_algorithm edit: Unless you mean moving the data?