8× faster binary search: from compiled code to mechanical sympathy
How do you speed up computational Python code? A common, and useful,
starting point is:
- Pick a good algorithm.
- Use a compiled language to write a Python extension.
- Maybe add parallelism so you can use multiple CPU cores.
But what if you need more speed? Consider the following real problem,
one of the steps in scikit-learn’s gradient histogram boosting
algorithm:
- You have a large array of floating point numbers.
- You want to assign them to the integer range 0-254, spread out evenly.
scikit-learn implements this by splitting up the full range of float
values into 255 buckets, creating a sorted array of bucket boundaries,
and then using binary search to choose the appropriate bucket for each
value. The binary search is implemented in a compiled language, and it