fast_search_histogr​am

fast 1d histogramming algorithms based on binary search. (faster than histcounts)

This project demonstrates superior speed to Matlab's inbuilt histcounts function and provides an adaptive function (hist_adaptive_method) that automatically picks the fastest method.

The brute force approach to histogramming is to compare each bin to each data value (or *count*) and gives a complexity **O(n·m)** where *n* is the number of data values and *m* is the number of bins. This can be improved by two algorithms.

1. **Bin Search, O(n·log(m))**: For each count do a binary search for the histogram bin that it should go into and then increment that bin. Because the bins are already ordered then there is no sorting needed. Best when m>>n (sparse histogramming).
to use:
bin_counts=hist_bin_search(data,edges)

2. **Count Search, O(m·log(n))**: For each bin edge do a binary search to find the nearest data index. Use the difference in this data index between bins to give the number of counts. Must have ordered data for the search to work, sorting first would cost **O(n·log(n))** and would make this method slower unless repeated histogramming was needed. Best when n>>m (dense histogramming) which is the more common use case. (this is the method shown in the logo)
to use:
bin_counts=hist_count_search(data,edges) (WARNING SORTED DATA REQUIRED)

I observe empirically (see /figs/scaling_comparison.png & hist_scaling_test) that there is a fairly complex dependence of which algorithm is best on the value of n and m. I have implemented a function that does a good job of picking the fastest method.