Performance

[coldfix]

Performance

[bwoodsend]

I somehow thought I had to pass the desired number of elements and hirola would then choose a good hash table length for me. I don't know where I got that idea.

For the record, I've just pushed 41e0ba3 to master which adds a warning if you let your table get too full so the next person to make that mistake should find out otherwise pretty quickly.

[coldfix]

Part of the performance difference can be mitigated by not redoing the lookups in the case where we have many repeated values:

def hiro2(sought):
    unique, indices = np.unique(sought, return_inverse=True)
    return tab.get(unique)[indices]

print("hiro2", timeit(lambda: hiro2(sought), number=100))

Output:

hiro2 0.2717397840006015

Still a bit slower than pandas, but already much better in this situation.

[bwoodsend]

Thanks for the interest and benchmark code. I hadn't heard of pandas.Categorical().

The solution to why hirola is performing slower is actually very simple although the explanation is less so. If I change:

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

from your code to:

tab = hirola.HashTable(len(known) * 1.5, known.dtype)

then then my benchmark values go from:

hirola 5.591865312977461
pandas 0.24903952999738976

to:

hirola 0.11547893600072712
pandas 0.2469974830164574

The problem is that you're letting the table get full. You have 500 unique but a table size of 500. Once a hash table gets more than around ²⁄₃ full the algorithm very quickly loses efficiciency, devolving towards plain brute force searching. I guess I need to put these last sentences somewhere more prominent.

And if you don't mind eating extra memory, you can keep adding extra space. With that 1.5 multiplier set to 2 I get 0.08231 and with it set to 3 I get 0.06492.

[coldfix]

Oh, many thanks, that makes sense. I somehow thought I had to pass the desired number of elements and hirola would then choose a good hash table length for me. I don't know where I got that idea.

[coldfix]

Awesome!