# cykhash

cython wrapper for khash-sets/maps, efficient implementation of `isin` and `unique`

## About:

  * Brings functionality of khash (https://github.com/attractivechaos/klib/blob/master/khash.h) to Python and Cython and can be used seamlessly in numpy or pandas.

  * Numpy's world is lacking the concept of a (hash-)set. This shortcoming is fixed and efficient (memory- and speedwise compared to pandas') `unique` and `isin` are implemented.

  * Python-set/dict have big memory-footprint. For some datatypes the overhead can be reduced by using khash by factor 4-8.

## Installation:

The recommended way to install the library is via `conda` package manager using the `conda-forge` channel:

    conda install -c conda-forge cykhash

You can also install the library using `pip`. To install the latest release:

    pip install cykhash

To install the most recent version of the module:

    pip install https://github.com/realead/cykhash/zipball/master

## Dependencies:

To build the library from source, Cython>=0.28 is required as well as a c-build tool chain.

See (https://github.com/realead/cykhash/blob/master/doc/README4DEVELOPER.md) for dependencies needed for development.

## Quick start

#### Hash set and isin

Creating a hashset and using it in `isin`:

    # prepare data:
    >>> import numpy as np 
    >>> a = np.arange(42, dtype=np.int64)
    >>> b = np.arange(84, dtype=np.int64)
    >>> result = np.empty(b.size, dtype=bool)

    # actually usage
    >>> from cykhash import Int64Set_from_buffer, isin_int64

    >>> lookup = Int64Set_from_buffer(a) # create a hashset
    >>> isin_int64(b, lookup, result)    # running time O(b.size)
    >>> isin_int64(b, lookup, result)    # lookup is reused and not recreated


### `unique`

Finding `unique` in `O(n)` (compared to numpy's  `np.unique` - `O(n*logn)`) and smaller memory-footprint than pandas' `pd.unique`:

    # prepare input
    >>> import numpy as np
    >>> a = np.array([1,2,3,3,2,1], dtype=np.int64)
    
    # actual usage:
    >>> from cykhash import unique_int64
    >>> unique_buffer = unique_int64(a) # unique element are exposed via buffer-protocol

    # can be converted to a numpy-array without copying via
    >>> unique_array = np.ctypeslib.as_array(unique_buffer)
    >>> unique_array.shape
    (3,)


### Hash map

Maps and sets handle `nan`-correctly (try it out with Python's dict/set):

    >>> from cykhash import Float64toInt64Map
    >>> my_map = Float64toInt64Map() # values are 64bit integers
    >>> my_map[float("nan")] = 1
    >>> my_map[float("nan")]
    1



## Functionality overview

### Hash sets

`Int64Set`, `Int32Set`, `Float64Set`, `Float32Set` ( and `PyObjectSet`) are implemented. They are more or less drop-in replacements for Python's `set`. Furthermore, given the Cython-interface, efficient extensions of functionality are easily done.


The biggest advantage of these sets is that they need about 4-8 times less memory than the usual Python-sets and are somewhat faster for integers or floats. 

As `PyObjectSet` is somewhat slower than the usual `set` and needs about the same amount of memory, it should be used only if all `nan`s should be treated as equivalent.

The most efficient way to create such sets is to use `XXXXSet_from_buffer(...)`, e.g. `Int64Set_from_buffer`, if the data container at hand supports buffer protocol (e.g. numpy-arrays, `array.array` or `ctypes`-arrays). Or `XXXXSet_from(...)` for any iterator.


### Hash maps

`Int64toInt64Map`, `Int32toInt32Map`, `Float64toInt64Map`, `Float32toInt32Map` ( and `PyObjectMap`) are implemented. They are more or less drop-in replacements for Python's `dict` (however, not every piece of `dict`'s functionality makes sense, for example `setdefault(x, default)` without `default`-argument, because `None` cannot be inserted, also the khash-maps don't preserve the insertion order, so there is also no `reversed`). Furthermore, given the Cython-interface, efficient extensions of functionality are easily done.

Biggest advantage of these sets is that they need about 4-8 times less memory than the usual Python-dictionaries and are somewhat faster for integers or floats.


As `PyObjectMap` is somewhat slower than the usual `dict` and needs about the same amount of memory, it should be used only if all `nan`s should be treated as equivalent.

### isin

  * implemented are `isin_int64`, `isin_int32`, `isin_float64`, `isin_float32`
  * using hash set instead of arrays in `isin` function has the advantage, that the look-up data structure doesn't have to be reconstructed for every call, thus reducing the running time from `O(n+m)`to `O(n)`, where `n` is the number of queries and `m`-number of elements in the look up array.
  * Thus cykash's `isin` can be order of magnitude faster than the numpy's or pandas' versions.

#### all, none, any, and count_if

  * siblings functions of `isin_XXX` are:
      * `all_XXX`/`all_XXX_from_iterator` which return `True` if all elements of the query array can be found in the set.
      * `any_XXX`/`any_XXX_from_iterator` which return `True` if at least one element of the query array can be found in the set.
      * `none_XXX`/`none_XXX_from_iterator` which return `True` if none of  elements from the query array can be found in the set.
      * `count_if_XXX`/`count_if_XXX_from_iterator` which return the number of elements from the query array can be found in the set.
  * `all_XXX`, `any_XXX`, `none_XXX` and `count_if_XXX` are faster than using `isin_XXX` and applying numpy's versions of these function on the resulting array.
  * `from_iterator` version works with any iterable, but the version for buffers are more efficient.

### unique

  * implemented are `unique_int64`, `unique_int32`, `unique_float64`, `unique_float32`
  * returns an object which implements the buffer protocol, so `np.ctypeslib.as_array` (recommended) or `np.frombuffer` (less safe, as memory can get reinterpreted) can be used to create numpy arrays.
  * differently as pandas, the returned uniques aren't in the order of the appearance. If order of appearence is important use `unique_stable_xxx`-versions, which needs somewhat more memory.
  * the signature is `unique_xxx(buffer, size_hint=0.0)` the initial memory-consumption of the hash-set will be `len(buffer)*size_hint` unless `size_hint<=0.0`, in this case it will be ensured, that no rehashing is needed even if all elements are unique in the buffer.

As pandas uses maps instead of sets internally for `unique`, it needs about 4 times more peak memory and is 1.6-3 times slower.


### Floating-point numbers as keys

There is a problem with floating-point sets or maps, i.e. `Float64Set`, `Float32Set`, `Float64toInt64Map` and `Float32toInt32Map`: The standard definition of "equal" and hash-function based on the bit representation don't define a meaningful or desired behavior for the hash set:

   * `NAN != NAN` and thus it is not equivalence relation
   * `-0.0 == 0.0` but `hash(-0.0)!=hash(0.0)`, but `x==y => hash(x)==hash(y)` is neccessary for set to work properly.

This problem is resolved through following special case handling:

   * `hash(-0.0):=hash(0.0)`
   * `hash(x):=hash(NAN)` for any not a number `x`.
   * `x is equal y <=> x==y || (x!=x && y!=y)`

A consequence of the above rule, that the equivalence classes of `{0.0, -0.0}` and `e{x | x is not a number}` have more than one element. In the set these classes are represented by the first seen element from the class.

The above holds also for `PyObjectSet` (this behavior is not the same as fro Python-`set` which shows a different behavior for nans).

### Examples:

#### Hash sets

Python: Creates a set from a numpy-array and looks up whether an element is in the resulting set:

    >>> import numpy as np
    >>> from cykhash import Int64Set_from_buffer
    >>> a =  np.arange(42, dtype=np.int64)
    >>> my_set = Int64Set_from_buffer(a) # no reallocation will be needed
    >>> 41 in my_set 
    True
    >>> 42 not in my_set
    True

Python: Create a set from an iterable and looks up whether an element is in the resulting set:

    >>> from cykhash import Int64Set_from
    >>> my_set = Int64Set_from(range(42)) # no reallocation will be needed
    >>> assert 41 in my_set and 42 not in my_set

Cython: Create a set and put some values into it:

    from cykhash.khashsets cimport Int64Set
    my_set = Int64Set(number_of_elements_hint=12)  # reserve place for at least 12 integers
    cdef Py_ssize_t i
    for i in range(12):
       my_set.add(i)
    assert 11 in my_set and 12 not in my_set

#### Hash maps

Python: Creating `int64->float64` map using `Int64toFloat64Map_from_buffers`:

    >>> import numpy as np
    >>> from cykhash import Int64toFloat64Map_from_buffers
    >>> keys = np.array([1, 2, 3, 4], dtype=np.int64)
    >>> vals = np.array([5, 6, 7, 8], dtype=np.float64)
    >>> my_map = Int64toFloat64Map_from_buffers(keys, vals) # there will be no reallocation
    >>> assert my_map[4] == 8.0

Python: Creating `int64->int64` map from scratch:

    >>> import numpy as np
    >>> from cykhash import Int64toInt64Map

    # my_map will not need reallocation for at least 12 elements
    >>> my_map = Int64toInt64Map(number_of_elements_hint=12)
    >>> for i in range(12):  my_map[i] = i+1
    >>> assert my_map[5] == 6


#### isin

Python: Creating look-up data structure from a numpy-array, performing `isin`-query

    >>> import numpy as np
    >>> from cykhash import Int64Set_from_buffer, isin_int64
    >>> a = np.arange(42, dtype=np.int64)
    >>> lookup = Int64Set_from_buffer(a)

    >>> b = np.arange(84, dtype=np.int64)
    >>> result = np.empty(b.size, dtype=bool)

    >>> isin_int64(b, lookup, result)    # running time O(b.size)
    >>> assert np.sum(result.astype(np.int)) == 42


#### unique

Python: using `unique_int64`:

    >>> import numpy as np
    >>> from cykhash import unique_int64
    >>> a = np.array([1,2,3,3,2,1], dtype=np.int64)
    >>> u = np.ctypeslib.as_array(unique_int64(a)) # there will be no reallocation
    >>> assert set(u) == {1,2,3}

Python: using `unique_stable_int64`: 

    >>> import numpy as np
    >>> from cykhash import unique_stable_int64
    >>> a = np.array([3,2,1,1,2,3], dtype=np.int64)
    >>> u = np.ctypeslib.as_array(unique_stable_int64(a)) # there will be no reallocation
    >>> assert list(u) == [3,2,1] 



## API

See (https://github.com/realead/cykhash/blob/master/doc/README_API.md) for a more detailed API description.

## Performance

See (https://github.com/realead/cykhash/blob/master/doc/README_PERFORMANCE.md) for results of performance tests.

## Trivia

* This project was inspired by the following stackoverflow question: https://stackoverflow.com/questions/50779617/pandas-pd-series-isin-performance-with-set-versus-array.

* pandas also uses `khash` (and thus was a source of inspiration), but wraps only maps and doesn't wrap sets. Thus, pandas' `unique` needs more memory as it should. Those maps are also never exposed, so there is no way to reuse the look-up structure for multiple calls to `isin`.

* `khash` is a good choice, but there are other alternatives, e.g. https://github.com/sparsehash/sparsehash. See also https://stackoverflow.com/questions/48129713/fastest-way-to-find-all-unique-elements-in-an-array-with-cython/48142655#48142655 for a comparison for different `unique` implementations.

* A similar approach for sets/maps in pure Cython: https://github.com/realead/tighthash, which is quite slower than khash.

* There is no dependency on `numpy`: this library uses buffer protocol, thus it works for `array.array`, `numpy.ndarray`, `ctypes`-arrays and anything else. However, some interfaces are somewhat cumbersome (which type should be created as answer?) and for convenient usage it might be a good idea to wrap the functionality so objects of right types are created.

## History:

#### Release 2.0.0 (09.11.2021):

  * Implementation of `any`, `all`, `none` and `count_if`
  * Hash-sets are now (almost) drop-in replacements of Python's sets
  * Breaking change: iterator from maps doesn't no longer returns items but only keys. However there are following new methods `keys()`, `values()` and `items()`which return so called mapvies, which correspond more or less to dictviews (but for mapsview doesn't hold that "Dictionary order is guaranteed to be insertion order.").
  * Hash-Maps are now (almost) drop-in replacements of Python's dicts. Differences: insertion order isn't preserved, thus there is also no `reversed()`-method, `setdefault(key, default)` isn't possible without `default` because `None` cannot be inserted in the map
  * Better hash-functions for float64, float32, int64 and int32 (gh-issue #4).
  * Breaking change: different names/signatures for maps
  * supports tracemalloc for Py3.6+
  * supports Python 3.10

#### Release 1.0.2 (30.05.2020):

  * can be installed via conda-forge to all operating systems
  * can be installed via pip in a clean environment (Cython>=0.28 is now fetched automatically)

#### Release 1.0.1 (27.05.2020):

  * released on PyPi

#### Older:

  * 0.4.0: uniques_stable, preparing for release
  * 0.3.0: PyObjectSet, Maps for Int64/32 and also Float64/32, unique-versions
  * 0.2.0: Int32Set, Float64Set, Float32Set
  * 0.1.0: Int64Set