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}