Advertisement Jump to content
Sign in to follow this  
Prune

Histogram: logarithmic binning in O(1)?

This topic is 1877 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I need a histogram with a logarithmic X axis; that is, the bin size is logarithmic (say with ranges 0.1-1, 1-10, 10-100, etc.). I'm storing the histogram as a plain 1D array.

Given a value, to find the corresponding bin, code I've found online loops over the bins, calculating bin width and checking if x falls in it, else continuing. That's O(num_bins), which is awful. How do I calculate the bin/array index in O(1) as is done in the linear case? Surely there's a closed-form analytic formula.

Edited by Prune

Share this post


Link to post
Share on other sites
Advertisement

\[\text{bin}(x) = \left \lfloor \log_{10}\left ({\frac{x}{x_\text{min}}} \right ) \right \rfloor \]

 

In your case, \( x_\text{min} = 0.1 \) and the bin numbering starts at zero. You can derive this by starting the histogram at the 1..10 bin and accounting for the smaller bins afterwards.

Share this post


Link to post
Share on other sites

Actually, not quite there. When I said "say with ranges 0.1-1, 1-10, 10-100, etc." that was just an example. The formula above works when num_bins = log10(max_range). But I want num_bins to be a parameter that can be set independently of max_range.

Share this post


Link to post
Share on other sites

The general formula is:

bin = floor(N * (log(x) - log(min)) / (log(max) - log(min)))

The value of bin is the bin index such that there are N bins logaritmically spaced between min (inclusive) and max (exclusive).

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!