Fast Hamming distance calculation for hexadecimal strings
Project description
What does it do?
This module performs a fast bitwise hamming distance of two hexadecimal strings.
This looks like:
DEADBEEF = 11011110101011011011111011101111 00000000 = 00000000000000000000000000000000 XOR = 11011110101011011011111011101111 Hamming = number of ones in DEADBEEF ^ 00000000 = 24
This essentially amounts to
>>> import gmpy >>> gmpy.popcount(0xdeadbeef ^ 0x00000000) 24
except with Python strings, so
>>> import gmpy >>> gmpy.popcount(int("deadbeef", 16) ^ int("00000000", 16)) 24
A few assumptions are made and enforced:
this is a valid hexadecimal string (i.e., [a-fA-F0-9]+)
the strings are the same length
the strings do not begin with "0x"
Why yet another Hamming distance library?
There are a lot of fantastic (python) libraries that offer methods to calculate various edit distances, including Hamming distances: Distance, textdistance, scipy, jellyfish, etc.
In this case, I needed a hamming distance library that worked on hexadecimal strings (i.e., a Python str) and performed blazingly fast. Furthermore, I often did not care about hex strings greater than 256 bits. That length constraint is different vs all the other libraries and enabled me to explore vectorization techniques via numba, numpy, and even SSE/AVX.
Lastly, I wanted to minimize dependencies, meaning you do not need to install numpy, gmpy, cython, pypy, pythran, etc.
Eventually, after playing around with gmpy.popcount, numba.jit, pythran.run, numpy, and AVX2, I decided to write what I wanted in a raw C header. At this point, I’m using raw char* and int*, so exploring re-writing this in Fortran makes little sense. Vectorization techniques also ended up adding more overhead due to converting the hex strings to vector-register-ingestible floats from char*.
Installation
To install, ensure you have Python 2.7 or 3.4+. Run
pip install hexhamming
or to install from source
git clone https://github.com/mrecachinas/hexhamming cd hexhamming python setup.py install # or pip install .
If you want to contribute to hexhamming, you should install the dev dependencies
pip install -r requirements-dev.txt
and make sure the tests pass with
pytest -vls
Example
To use the base C++ extension, you can simply run
>>> from hexhamming import hamming_distance >>> hamming_distance("deadbeef", "00000000") 24
Benchmark
Note: For the below image, to show how optimized this is, I included the benchmark of a function that looks like
Below is a benchmark using pytest-benchmark with hexhamming==v1.3.0 my early 2016 1.2 GHz Intel m5 8 GB 1867 MHz LPDDR3 macOS Mojave (10.14.3) with Python 3.7.3 and Apple clang version 11.0.0 (clang-1100.0.33.17).
Name |
Mean (ns) |
Std (ns) |
Median (ns) |
Rounds |
Iterations |
---|---|---|---|---|---|
test_hamming_distance_bench_short_same |
182.21 |
282.187 |
140.1 |
137742 |
30 |
test_hamming_distance_bench_short |
204.275 |
353.317 |
154.156 |
183723 |
32 |
test_hamming_distance_bench_long_same |
431.369 |
553.671 |
329.5 |
132838 |
20 |
test_check_hexstrings_within_dist_bench |
419.923 |
489.503 |
330.1 |
83718 |
20 |
test_hamming_distance_bench_256 |
649.275 |
2854.9 |
505 |
172118 |
1 |
test_hamming_distance_bench_long |
3569.42 |
6408.05 |
2758 |
160591 |
1 |
Project details
Release history Release notifications | RSS feed
Download files
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.
Source Distribution
Built Distributions
Hashes for hexhamming-1.3.1-cp37-cp37m-macosx_10_14_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | f9fcf2fd0e3742af9a1b8023a1d30b03117a81ac65642b04024d7ddfefc133a9 |
|
MD5 | bd7b75b3f9ad616d1ba7ff1f22b4f66a |
|
BLAKE2b-256 | bece579002d0158eef058fc812c28a659e2beb0ea96ecfe44966e5b04bc6d408 |
Hashes for hexhamming-1.3.1-cp27-cp27m-macosx_10_13_x86_64.whl
Algorithm | Hash digest | |
---|---|---|
SHA256 | 294da6f2699be3ca28610d0a187e27c59c1743ce59b09500a0d823c63b00a671 |
|
MD5 | d8971c3b5212c34cbba473512d00e98a |
|
BLAKE2b-256 | 9fa636ab7fa744a0e31c10ef3f1ec2153a00404825335454bc6b3880b8436075 |