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 Paul Ross. _______________________________________________ Python-announce-list mailing list -- python-announce-list@python.org To unsubscribe send an email to python-announce-list-le...@python.org https://mail.python.org/mailman3/lists/python-announce-list.python.org/ Member address: arch...@mail-archive.com
