Re: Efficient Histogram Algorithm?

*To*: mathgroup at smc.vnet.net*Subject*: [mg113052] Re: Efficient Histogram Algorithm?*From*: "Sjoerd C. de Vries" <sjoerd.c.devries at gmail.com>*Date*: Tue, 12 Oct 2010 04:26:21 -0400 (EDT)*References*: <i8uknn$of3$1@smc.vnet.net>

My laptop is 5 years old but on V7 it takes BinCounts 0.468 s to calculate this. Cheers -- Sjoerd On Oct 11, 11:17 am, Julian Francis <julian.w.fran... at gmail.com> wrote: > 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}