cython wrapper for khash-sets/maps, efficient implementation of isin and unique
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.
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
Attention: On Linux/Mac python-dev should be installed for that (see also https://stackoverflow.com/questions/21530577/fatal-error-python-h-no-such-file-or-directory) and MSVC on Windows.
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.
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=np.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
uniqueFinding 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,)
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
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 nans 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.
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 nans should be treated as equivalent.
isin_int64, isin_int32, isin_float64, isin_float32isin 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.isin can be order of magnitude faster than the numpy's or pandas' versions.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_int64, unique_int32, unique_float64, unique_float32np.ctypeslib.as_array (recommended) or np.frombuffer (less safe, as memory can get reinterpreted) can be used to create numpy arrays.unique_stable_xxx-versions, which needs somewhat more memory.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.
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).
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
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
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=np.bool_)
>>> isin_int64(b, lookup, result) # running time O(b.size)
>>> assert np.sum(result.astype(np.int_)) == 42
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]
See (https://github.com/realead/cykhash/blob/master/doc/README_API.md) for a more detailed API description.
See (https://github.com/realead/cykhash/blob/master/doc/README_PERFORMANCE.md) for results of performance tests.
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.
There are different levels of compatibility:
Ther rules are as follows:
1.x.y might not run with cykhash 2.z.w and vice versa.2.0.x will run with cykhash 2.1.y (but not the other way around: that means new functions could be added to pure python interface)cdef interface is used, i.e. a cython-extension was build using pxi-files from cykhash, then versions are compartible only if the the minor versions are the same, e.g. 2.0.x could be replaced by 2.0.y in the installation, but when replacing with 2.1.z the dependent cython-extension must be rebuilt.any, all, none and count_ifkeys(), 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.").reversed()-method, setdefault(key, default) isn't possible without default because None cannot be inserted in the mapFAQs
cython wrapper for khash-sets/maps, efficient implementation of isin and unique
We found that cykhash demonstrated a healthy version release cadence and project activity because the last version was released less than a year ago. It has 1 open source maintainer collaborating on the project.
Did you know?
Socket for GitHub automatically highlights issues in each pull request and monitors the health of all your open source dependencies. Discover the contents of your packages and block harmful activity before you install or update your dependencies.
Security News
Research
The Socket Research Team breaks down a malicious wrapper package that uses obfuscation to harvest credentials and exfiltrate sensitive data.
Research
Security News
Attackers used a malicious npm package typosquatting a popular ESLint plugin to steal sensitive data, execute commands, and exploit developer systems.
Security News
The Ultralytics' PyPI Package was compromised four times in one weekend through GitHub Actions cache poisoning and failure to rotate previously compromised API tokens.