fast_search_histogr​am

fast 1d histogramming algorithms based on binary search. (faster than histcounts)
83 Downloads
Aktualisiert 2. Dez 2021

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.

Zitieren als

Bryce Henson (2024). fast_search_histogram (https://github.com/brycehenson/fast_search_histogram), GitHub. Abgerufen.

Kompatibilität der MATLAB-Version
Erstellt mit R2019a
Kompatibel mit allen Versionen
Plattform-Kompatibilität
Windows macOS Linux
Kategorien
Mehr zu Data Distribution Plots finden Sie in Help Center und MATLAB Answers

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Versionen, die den GitHub-Standardzweig verwenden, können nicht heruntergeladen werden

Version Veröffentlicht Versionshinweise
1.0.0

Um Probleme in diesem GitHub Add-On anzuzeigen oder zu melden, besuchen Sie das GitHub Repository.
Um Probleme in diesem GitHub Add-On anzuzeigen oder zu melden, besuchen Sie das GitHub Repository.