Re^2: Perl hit counter for multiple ranges, optimization or options in other languages?

~~If you use a slightly different data structure, you could even use a modified binary search to find the proper bucket, resulting in log2(N) comparisons instead of N/2 comparisons (on average).~~

Update: Ignore this - Laurent_R's solution assumes an already sorted data set and just steps through it. $coffee++.

--MidLifeXis

Comment on Re^2: Perl hit counter for multiple ranges, optimization or options in other languages? Download Code

Replies are listed 'Best First'.
Re^3: Perl hit counter for multiple ranges, optimization or options in other languages? by Laurent_R (Canon) on Aug 08, 2013 at 14:44 UTC
The algorithm I suggested is actually reading in parallel the data and the bin ranges. Therefore, it does just 1 comparison per line of data (plus one additional comparison each time the program crosses a bin range). The complexity is O(N). It will be very difficult to do anything better for N data records (at least if the data is sorted, which was my starting hypothesis; even if the data needs to be sorted, it is still likely to be the fastest solution if a good N Log N sorting program is used).	[reply]
Re^4: Perl hit counter for multiple ranges, optimization or options in other languages? by MidLifeXis (Monsignor) on Aug 08, 2013 at 14:48 UTC
Quite right. Coffee deficiency. --MidLifeXis	[reply]