Vfrdtyky

I got a List of integers and I want to count the number of times each integer appears in the list.

For example: [0,5,0,1,3,3,1,1,1] gives (0 -> 2), (1 -> 4), (3 -> 2), (5 -> 1). I only need the count, not the value (the goal is to have an histogram of the counts).

A common approach would be to group by value then count the cardinality of each set. In SQL: SELECT count(*) FROM myTable GROUPBY theColumnContainingIntegers.

Is there a faster way to do this? A heuristic or a probabilistic approach is fine since I am computing a large data set and sacrifying precision for speed is fine.

Something similar to HyperLogLog algorithm (used to count the number of distinct elements in a data set) would be great, but I did not find anything like this...

Let's take your set containing 9 elements [0,5,0,1,3,3,1,1,1] and make it big but with same frequencies of elements:

> bigarray = [0,5,0,1,3,3,1,1,1] * 200

 => [0, 5, 0, 1, 3, 3, 1, 1, 1, 0, 5, 0, 1, 3, 3, 1, ...

Now bigarray size is 1800 so let's try to work with it.

Take a sample of 180 elements (random 180 elements from this set)

Now compute occurence for this random subset

{5=>19, 3=>45, 1=>76, 0=>40}

Normalized:

{5=>1.0, 3=>2.3684210526315788, 1=>4.0, 0=>2.1052631578947367}

Of course for different random subset results will be different:

{5=>21, 3=>38, 1=>86, 0=>35}

Normalized

{5=>1.0, 3=>1.8095238095238095, 1=>4.095238095238095, 0=>1.6666666666666667}

Of course there are some errors there - this is inevitable and you will need to state what will be acceptable error

Now make same test for bigarray (size 1000) with 50% of 0's and 50% of 1's

 > bigarray = [0,1] * 500

 => [0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0,  ...

With sample of 100 elements:

{0=>50, 1=>50}

Normalized

{0=>1.0, 1=>1.0}

Second sample:

{0=>49, 1=>51}

Normalized

{0=>1.0, 1=>1.0408163265306123}

It seems that we can easily reduce our subset and here Sampling comes.

Especially Reservoir Sampling - this may be very useful if in your case data is populated 'live' or set is too large to process all values at once.

edit

Concerning comment:
Of course if you have large set and some element appears there very rare then you may have lost it and occurence will equal 0.

Then you may use kind of smoothing function (check additive smoothing). Just assume that each possible element 1 more time than it really appeared.

For example let's say we have set:

1000 elements 1

100 elements 2

10 elements 3

1 elements 4

Let's say our subset contains {1=>100,2=>10,3=>1, 4=>0}

Smoothing param = 0.05 so we add 0.05 to each occurence

{1=>100.05,2=>10.05,3=>1.05, 4=>0.05}

Of course this is assuming that you know what values are even possible to be present in the set.