Using Python's Bisect Module
johnlekberg.com
Using Python's Bisect Module
1–10 of 14 posts
Re: Using Python's Bisect Module
#2The entire bisect module, consisting of 4 public functions, is literally only 32 lines of code.
Re: Using Python's Bisect Module
#3The entire bisect module, consisting of 4 public functions, is literally only 32 lines of code.
Re: Using Python's Bisect Module
#4The entire bisect module, consisting of 4 public functions, is literally only 32 lines of code.
Hate to be pedantic, as it is a thing of beauty, but most of it is replaced by a C implementation instead.
Re: Using Python's Bisect Module
#5The entire bisect module, consisting of 4 public functions, is literally only 32 lines of code.
https://github.com/python/cpython/blob/master/Lib/bisect.py
Interesting to see the module defines a pure Python implementation first, then tries to import a fast C implementation. If the C version is present, it replaces the Python version.
Bisect is a very old module, certainly present in Python 1.5.2 from 1999 that I started with. I expect the C implementations got added a year or two later.
Re: Using Python's Bisect Module
#6Earlier quoted context omitted.
https://github.com/python/cpython/blob/master/Lib/bisect.py
Interesting to see the module defines a pure Python implementation first, then tries to import a fast C implementation. If the C version is present, it replaces the Python version. Bisect is a very old module, certainly present in Python 1.5.2 from 1999 that I started with. I expect the C implementations got added a year or two later.
> Interesting to see the module defines a pure Python implementation first, then tries to import a fast C implementation.
Peak Python
Re: Using Python's Bisect Module
#7Bisect is nice, but it's not the fastest option.
If binning data, discretize it and then use a dict lookup - `grades_to_letters[grade//10]`, for example.
For insort, and indeed anything with sorted collections, just use the http://www.grantjenks.com/docs/sortedcontainers/ module. Inserting an element is worst-case sublinear time, and also faster than C-extensions. It's one of the very few data-structure libraries I use regularly.
Re: Using Python's Bisect Module
#8Is O(n + log n) really a thing or should he just write O(n)?
Re: Using Python's Bisect Module
#9Is O(n + log n) really a thing or should he just write O(n)?
Short answer is no because we’re talking about asymptotic behavior and n dominates log n.
Long answer is yes because O notation is commonly written this way to be more illustrative of what’s happening in an algorithm and that were smushing to algorithms together.
If you can be more precise then feel free to write it down. For example O notation hides a constant factor but if you happen to actually know it exactly you might see O(7n) in the wild.
Re: Using Python's Bisect Module
#10Earlier quoted context omitted.
https://github.com/python/cpython/blob/master/Lib/bisect.py
Interesting to see the module defines a pure Python implementation first, then tries to import a fast C implementation. If the C version is present, it replaces the Python version. Bisect is a very old module, certainly present in Python 1.5.2 from 1999 that I started with. I expect the C implementations got added a year or two later.
Yes, but now I want to know:
1. Is there a C version? I don't see it in the same directory.
2. If there is a C version, does anyone who submits a PR (like the one in 2019 adding 'key'[0]) have to submit a C version along with it?