A Linear-Time probabilistic counting algorithm, or Linear Counting algorithm, was proposed by Kyu-Young Whang at al. in 1990.
It’s a hash-based probabilistic algorithm for counting the number of distinct values in the presence of duplicates.
The algorithm has O(N) time complexity, where N is the total number of elements, including duplicates.
This implementation uses bitvector to store the counter’s array.
from pdsa.cardinality.linear_counter import LinearCounter lc = LinearCounter(1000000) lc.add("hello") print(lc.count())
Build a counter¶
To build a counter, specify its length.
from pdsa.cardinality.linear_counter import LinearCounter lc = LinearCounter(100000)
Memory for the counter is assigned by chunks, therefore the length of the counter can be rounded up to use it in full.
This implementation uses MurmurHash3 family of hash functions which yields a 32-bit hash value that implies the maximal length of the counter.
Index element into the counter¶
It is possible to index into the counter any elements (internally it uses repr() of the python object to calculate hash values for elements that are not integers, strings or bytes.
Size of the counter in bytes¶
Length of the counter¶
Count of unique elements in the counter¶
It is only an approximation, that is quite good for not huge cardinalities.