Efficient Histogram Algorithm?

*To*: mathgroup at smc.vnet.net*Subject*: [mg113026] Efficient Histogram Algorithm?*From*: Julian Francis <julian.w.francis at gmail.com>*Date*: Mon, 11 Oct 2010 05:17:56 -0400 (EDT)

Dear all, Does anyone know of a way to implement a fast histogram algorithm in Mathematica? My first attempt (In44) was based around a table and using the count function. A bit of thought indicates that this might not be very efficient as it would seem to involve examining the list 255 times, when only once is necessary. The second attempt involved using the built in library function BinCounts, but surprisingly this was only about twice as fast as my initial naive version, which makes me wonder if it is as efficient as it could be. I can assume for my purposes that the list will always have integer values between 0 and 255, and that there are 256 bins. I wasn't able to think of a way to implement the histogram function in a functional programming style that was also efficient, although it is fairly easy to write in an imperative language. This may reflect the vast majority of my programming experience has been in imperative languages. I am using an old version of Mathematica (v4.1) (but on a modern PC); but if anyone has dramatically different times for the BinCounts function, then maybe it is time for me to upgrade. My motivation is a pattern recognition algorithm I am implementing, but it requires a large number of histograms to be created, hence the running time of an individual histogram is actually quite important. Thanks for any help, Julian. In[44]:= jhistogram[list_] := Table[Count[list, n], {n, 0, 255}] In[51]:= \!\(Timing[\(randomList = Table[Random[Integer, 255], {10\^6}];\)]\) Out[51]= {1.373 Second, Null} In[54]:= Timing[hist = jhistogram[randomList];] Out[54]= {2.34 Second, Null} In[56]:= << Statistics` In[57]:= Timing[hist = BinCounts[randomList, {0, 255}];] Out[57]= {0.936 Second, Null}