Code covered by the BSD License  

Highlights from
find_idx

Be the first to rate this file! 18 Downloads (last 30 days) File Size: 4.25 KB File ID: #23049

find_idx

by

 

20 Feb 2009 (Updated )

Fractional binning

| Watch this File

File Information
Description

idx=find_idx(xi, xgrid)

This function not only bin similarly to HISTC, but also returns the fractional position of data points within the binning interval.

It is equivalent to
interp1(xgrid,(1:length(xgrid)), xi)
but with the speed improvement up to 5 times.

Algorithm: dichotomy, complexity of m.log(n), where m isnumber of data points (xi) and n is number of bins (xgrid).

Few obvious examples of applications:
 - binning step for more sophisticated interpolation schemes such as multi-dimensional spline or linear tensorial interpolations.
- Generate discrete random sequences with given probability distribution.

MATLAB release MATLAB 7.7 (R2008b)
Other requirements mex compilation correctly setup
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (2)
24 Feb 2009 Bruno Luong

Hi John,

Thanks for your comment. Fair enough. histc is fater than interp1. I also discovered this fact recently (after I developed this code and benchmark various methods in fact), and this is something I did not expected.

22 Feb 2009 John D'Errico

This would be useful to anyone implementing an interpolant in one dimension, or for those writing an interpolation in higher dimensions on a regular lattice. For example, a tensor product interpolant would benefit from this code as the first step, as would some other methods.

I won't offer a rating since I cannot test this without a c-compiler, and without the presence of the compiled version, it just calls interp1 as the engine. It looks well done to me from a quick read through of the code though. I won't make any claim about the c code, since I have no skills in that respect.

I'm not sure about the speed claim though, since if the author has based the claim of speed to a comparison to interp1, I can achieve a 55% reduction in time over interp1 just by a simple call to histc.

xgrid = (0:.1:10);
xi = rand(1,10000)*10;

tic,dx=diff(xgrid);[junk,B]=histc(xi,xgrid);B=B+(xi-xgrid(B))./dx(B);toc
Elapsed time is 0.010040 seconds.

tic,B = interp1(xgrid,(1:length(xgrid)), xi);toc
Elapsed time is 0.022428 seconds.

Both code fragments generate the same outputs, yet the histc one is considerably faster, and written in basic matlab. Any comparison of time should use this as the reference, not interp1.

Updates
20 Feb 2009

Correct tags

Contact us