Speeding up HeavyHitters add function

[argenisleon]

Hi,

Thanks for the amazing library.

I am trying to speed up the add function in Heavy Hitter class.
First I am trying to speed up the hash calculation using the hash_pandas_object from the pandas' library which seems to be faster than the pyprobable implementation.

Creating 100_000 items

import pandas as pd
from pandas.util import hash_pandas_object
df = pd.DataFrame({"A":["hash this"]*100_000})

Using pandas

%%time
hash_pandas_object(df, index=False).values

Wall time: 8.96 ms
array([12356425079718161818, 12356425079718161818, 12356425079718161818,
       ..., 12356425079718161818, 12356425079718161818,
       12356425079718161818], dtype=uint64)

Vs

Using pyprobables

%%time
from probables.hashes import default_fnv_1a
for _ in df.A.values:
    default_fnv_1a("1dhusadhf")

Wall time: 449 ms

In the add function in the line
https://github.com/barrust/pyprobables/blob/master/probables/countminsketch/countminsketch.py#L274
the hashed value returns multiple values in a list. But I am not sure why, any help?

[barrust]

I am glad that you have found this package helpful. The default fnv-1a hash can be slow due to it being a pure python implementation. There are several things that one can do to speed it up such as using a hashing function implemented in C. For example, you can see the documentation that shows how to easily setup a custom hashing strategy or by utilizing custom hashing functions.

If you do not want to build your own system, there are additional functions that can be used, default_md5 and default_sha256, which are both implemented in C and would be faster than the default fnv-1a code. If you want to use something else, there are decorators that can be used to help ensure that you get the correct number of hash results. They are documented on read-the-docs

As for why the code uses a list of hash results is due to how Count-min Sketches work (which the Heavy Hitter is built upon). It uses a set of hash values (of the same input) to generate a fingerprint of the locations within a width*depth table. Specifically, it needs depth number of hashes per input to generate the required fingerprint. For a more in-depth understanding of how Count-min Sketches work, you can look at Wikipedia Count-min Sketch. There are other good resources, but I do not have them quickly available.

I hope this is informative and helpful!