I have released v0.3.4 of the orderedstructs package that contains a high performance SkipList implemented in C++ with Python bindings. A SkipList behaves as an always sorted list with, typically, O(log(n)) cost for insertion, look-up and removal. This makes it ideal for such operations as computing the rolling median of a large dataset.
The characteristics of this SkipList implementation include:
- No capacity restrictions apart from available memory. - Works with any C++ type <T> that has meaningful comparison operators. - The C++ SkipList can be compiled as thread safe. - The Python SkipList is thread safe. - Python SkipLists can be long/float/bytes/object types, the latter can have user defined comparison functions. - With Python 3.8+ SkipLists can be combined with the multiprocessing.shared_memory https://docs.python.org/3/library/multiprocessing.shared_memory.html#module-multiprocessing.shared_memory module for concurrent operation on large arrays. For example concurrent roling medians https://skiplist.readthedocs.io/en/latest/rolling_median.html#rolling-median-in-python-with-multiprocessing-shared-memory which speed up near linearly with the number of cores. - The implementation is extensively performance tested in C++ and Python.
There are a some novel features to this implementation:
- A SkipList is a probabilistic data structure but we have deterministic tests that work for any (sane) random number generator. See testing a probabalistic data structure http://skiplist.readthedocs.io/en/latest/test_notes.html#testing-a-probabilistic-structure - This SkipList can dynamically generate visualisations of its current internal state. See visualising a skiplist http://skiplist.readthedocs.io/en/latest/visualisations.html#skiplist-visualisation-label
Project source: https://github.com/paulross/skiplist PyPi: https://pypi.org/project/orderedstructs/ Documentation: http://skiplist.readthedocs.io/en/latest/index.html