fast 1d histogramming algorithms based on binary search. (faster than histcounts)
78 descargas
Actualizado 2 dic 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:

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.

Citar como

Bryce Henson (2024). fast_search_histogram (, GitHub. Recuperado .

Compatibilidad con la versión de MATLAB
Se creó con R2019a
Compatible con cualquier versión
Compatibilidad con las plataformas
Windows macOS Linux
Más información sobre Data Distribution Plots en Help Center y MATLAB Answers.

Community Treasure Hunt

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

Start Hunting!

No se pueden descargar versiones que utilicen la rama predeterminada de GitHub

Versión Publicado Notas de la versión

Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.
Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.