معرفی شرکت ها
cykhash-2.0.1
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشتر
تبلیغات ما
مشتریان به طور فزاینده ای آنلاین هستند. تبلیغات می تواند به آنها کمک کند تا کسب و کار شما را پیدا کنند.
مشاهده بیشترتوضیحات
cython wrapper for khash-sets/maps, efficient implementation of isin and unique
| ویژگی | مقدار |
|---|---|
| سیستم عامل | - |
| نام فایل | cykhash-2.0.1 |
| نام | cykhash |
| نسخه کتابخانه | 2.0.1 |
| نگهدارنده | [] |
| ایمیل نگهدارنده | [] |
| نویسنده | Egor Dranischnikow |
| ایمیل نویسنده | - |
| آدرس صفحه اصلی | https://github.com/realead/cykhash |
| آدرس اینترنتی | https://pypi.org/project/cykhash/ |
| مجوز | MIT |
# 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
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.
## 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=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
### `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=np.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.
## Compatibility between cykhash-versions:
There are different levels of compatibility:
* for code using only pure python interface
* for code using cython/cdef-interface and built against a particular cykash version
Ther rules are as follows:
* there is no warranty for major versions mismatch: i.e. code written with cykhash `1.x.y` might not run with cykhash `2.z.w` and vice versa.
* if only pure python interface is used, code for the same major version will ran for version with higher minor version, i.e. code for cykhash `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)
* if cython's `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.
## History:
### Release 2.0.1 (05.02.2022):
* Tests work for Python 3.11
* Tests work for numpy 1.24
* Drops support for Python 3.6 and Python 3.7
#### 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
نحوه نصب
نصب پکیج whl cykhash-2.0.1:
pip install cykhash-2.0.1.whl
نصب پکیج tar.gz cykhash-2.0.1:
pip install cykhash-2.0.1.tar.gz