Functions that rely on hash tables are incorrect for complex numbers

[jschendel]

It looks like various functions that rely on hash tables fail when complex numbers are present, as it appears they only use the real component.

Consider the following list of values:

In [2]: x = [0, 1j, 1, 1+1j, 1+2j]

In [3]: x
Out[3]: [0, 1j, 1, (1+1j), (1+2j)]

Using value_counts:

In [4]: pd.value_counts(x)
Out[4]:
(1+0j)    3
0j        2
dtype: int64

Using unique:

In [5]: pd.unique(x)
Out[5]: array([ 0.,  1.])

Using duplicated:

In [6]: pd.Series(x).duplicated()
Out[6]:
0    False
1     True
2    False
3     True
4     True
dtype: bool

Using isin:

In [7]: pd.Series(x).isin([1j, 1+1j, 1+2j])
Out[7]:
0    False
1    False
2    False
3    False
4    False
dtype: bool

In [8]: pd.Series(x).isin([0, 1])
Out[8]:
0    True
1    True
2    True
3    True
4    True
dtype: bool

Using factorize fails as described in #16399, and multiple other functions fail in similar ways (rank, nunique, mode, etc.).

Note that these appear to work if the dtype is explicitly set to object instead of complex64:

In [9]: pd.Series(x, dtype=object).isin([0, 1])
Out[9]:
0     True
1    False
2     True
3    False
4    False
dtype: bool

Output of pd.show_versions()

INSTALLED VERSIONS

commit: 51c5f4d
python: 3.6.1.final.0
python-bits: 64
OS: Windows
OS-release: 10
machine: AMD64
processor: Intel64 Family 6 Model 78 Stepping 3, GenuineIntel
byteorder: little
LC_ALL: None
LANG: None
LOCALE: None.None

pandas: 0.21.0rc1+26.g51c5f4d
pytest: 3.1.2
pip: 9.0.1
setuptools: 27.2.0
Cython: 0.25.2
numpy: 1.13.1
scipy: 0.19.1
pyarrow: 0.6.0
xarray: 0.9.6
IPython: 6.1.0
sphinx: 1.5.6
patsy: 0.4.1
dateutil: 2.6.0
pytz: 2017.2
blosc: None
bottleneck: None
tables: 3.4.2
numexpr: 2.6.2
feather: 0.4.0
matplotlib: 2.0.2
openpyxl: 2.4.8
xlrd: 1.1.0
xlwt: 1.3.0
xlsxwriter: 0.9.8
lxml: 3.8.0
bs4: None
html5lib: 0.999
sqlalchemy: 1.1.13
pymysql: None
psycopg2: None
jinja2: 2.9.6
s3fs: None
fastparquet: 0.1.0
pandas_gbq: None
pandas_datareader: None

[jreback]

yep, complex doesn't have much testing, nor likely is fully supported. nice first test.

@jschendel

pandas/pandas/core/algorithms.py

Line 80 in f5cc078

# ignore the fact that we are casting to float

@jreback
I can take a look (uint8 as well) if nobody is assigned to this.

[jreback]

@heckeop sure

After a bit of digging, it seems that the issue, at least for value_counts, boils down to implementing a way to hash complex numbers with khash.
https://github.com/pandas-dev/pandas/blob/master/pandas/_libs/src/klib/khash_python.h

• We could define khcomplex64_t and treat the 64 bits as uint64 when hashing, much like the code base already does for double type.
  

  pandas/pandas/_libs/src/klib/khash.h

  Lines 128 to 136 in f8ace5f

  	typedef unsigned long long khuint64_t;
  	typedef signed long long khint64_t;
  	#endif
  	typedef double khfloat64_t;
  	typedef khint32_t khint_t;
  	typedef khint_t khiter_t;

  
  

  pandas/pandas/_libs/src/klib/khash_python.h

  Lines 23 to 37 in f8ace5f

  	// correct for all inputs but not -0.0 and NaNs
  	#define kh_float64_hash_func_0_NAN(key) (khint32_t)((asint64(key))>>33^(asint64(key))^(asint64(key))<<11)
  	// correct for all inputs but not NaNs
  	#define kh_float64_hash_func_NAN(key) ((key) == 0.0 ? \
  	kh_float64_hash_func_0_NAN(0.0) : \
  	kh_float64_hash_func_0_NAN(key))
  	// correct for all
  	#define kh_float64_hash_func(key) ((key) != (key) ? \
  	kh_float64_hash_func_NAN(Py_NAN) : \
  	kh_float64_hash_func_NAN(key))
  	#define kh_float64_hash_equal(a, b) ((a) == (b) || ((b) != (b) && (a) != (a)))

• If 128 bit complex numbers are desired, maybe we can hash the 64 bits independently and hash the result pair.

We should then be able to add the complex type to

pandas/pandas/_libs/hashtable_func_helper.pxi.in

Lines 14 to 19 in f8ace5f

	dtypes = [('float64', 'float64', 'float64_t'),
	('uint64', 'uint64', 'uint64_t'),
	('object', 'pymap', 'object'),
	('int64', 'int64', 'int64_t')]
	}}

[joshlk]

As a quick fix, could we treat complex numbers as objects and use the generic hasher?

@TomAugspurger

This is a dev branch to get feedback on some ideas.

The generic hasher seems to work, but here are a few observations

1. An Index can only contain hashable types. So complex values get converted to objects.
2. From what I understand so far, algos that rely on hashing mostly fall into two categories, those that require sorting and those that don't. Since complex numbers are not ordered, hashing algorithms should not try to order the index (e.g. groupby(key, sort=False))

Still need to test mode, rank and interpolate