Index.difference performance

[Winand]

I need to append several big Series to a big categorical Series.
Trying to update categories FAST i've found out that Index.difference uses Python's set, which is slow on creating LARGE set (i have up to 500k categories and 1.3M values).
numpy's setdiff1 is more than an order of magnitude faster (as of datetime64 Categorical):

tmp_unique = tmp.unique()
new_cats = pd.Index(pd.np.setdiff1d(tmp_unique[~pd.isnull(tmp_unique)], to.cat.categories))

Not so fast:

new_cats = pd.Index(tmp_unique[~pd.isnull(tmp_unique)]).difference(to.cat.categories)

[jreback]

can u show the creation of tmp

[jreback]

and to

[Winand]

I've tried to implement this with string data and difference performed better. But setdiff1d is much better with datetime64[ns]

import pandas as pd, time

to=pd.Series(pd.DatetimeIndex(range(1000000))).astype('category')#pd.Series(("hello%d"%i for i in range(1000000))).astype('category')
cats = to.cat.categorical._categories.values
tmp=pd.Series(pd.DatetimeIndex(range(1000000, 1200000)))#pd.Series(("bye%d"%i for i in range(200000)))

tmp_unique = tmp.unique()
tmp_unique = tmp_unique[~pd.isnull(tmp_unique)]

_=time.clock()
new_cats = pd.Index(tmp_unique).difference(cats)
print("Index.difference: %.3fs"%(time.clock()-_))

_=time.clock()
new_cats = pd.Index(pd.np.setdiff1d(tmp_unique, cats))
print("np.setdiff1d: %.3fs"%(time.clock()-_))

-----
>>>Index.difference: 1.976s
>>>np.setdiff1d: 0.104s

[jreback]

interesting, the is the first numpy setop that actually is fast.

ok, sure pull-requests are welcome (including an asv benchmark).

[jreback]

xref #11279

note that you would have to use base forms for some of the index types (e.g. .values)

so might need to upgrade tests for this (in fact should consolidate all of the test_difference* tests in test_index.py) and move them to Base for generic testing.

[max-sixty]

@Winand I had a go at speeding this up, in the issue @jreback referenced. I didn't get it over the finish line, please do take the torch!

My understanding is that set is actually very fast. The slow part of the current implementation is the boxing & unboxing of values, for indexes that need to do conversions for each element for list(self). So if you can delegated to .values, then set should be reasonable. numpy may still be faster - worth comparing apples to apples