bwoodsend/hirola

NumPy vectorized hash table for fast set and dict operations.

hirola's Issues

Performance

• Hirola version: 0.2.1
• Python version: 3.9.6
• Operating System: Linux 5.13.12-arch1-1

Description

Hi,

this library looks really cool and to be a perfect fit for my purposes, I wonder why it didn't have any stars so far.

I was hoping to use it as a more lightweight replacement for pandas.Categorical, however I noticed that it is seems to be comparably slow for some reason. I was wondering whether some of the strategies employed in pandas could be adapted to speed up this library as well?

What I Did

Performance comparison between pandas.Categorical(...).codes and hirola.HashTable.get:

from timeit import timeit
import hirola
import numpy as np
import pandas as pd
import string


def generate_strings(count, min_len, max_len):
    words = np.random.choice(
        list(string.ascii_letters),
        (count, max_len)
    ).view((str, max_len)).reshape(-1)
    lengths = np.random.choice(np.arange(min_len, max_len + 1), count)
    return np.array([
        word[:length]
        for word, length in zip(words, lengths)
    ])


# Generate some strings to chose from
all_strings = generate_strings(1000, 5, 15)
known = np.random.choice(all_strings, 500, replace=False)
sought = np.random.choice(all_strings, 500, replace=False)
sought = np.random.choice(sought, 10000)

tab = hirola.HashTable(len(known), known.dtype)
tab.add(known)

print("hirola", timeit(lambda: tab.get(sought), number=100))
print("pandas", timeit(
    lambda: pd.Categorical(sought, categories=known).codes,
    number=100,
))

# Check that both methods actually yield the same results:
np.testing.assert_equal(
    tab.get(sought),
    pd.Categorical(sought, categories=known).codes)

Output:

hirola 2.799455799000498
pandas 0.12548323099872505

I didn't investigate the reason (vectorization, hash/search algorithm/...?)