Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python.announce > #3622 > unrolled thread

Release 0.3.4 of orderedstructs including a C++/Python SkipList

Back to article view | Back to comp.lang.python.announce

Contents

  Release 0.3.4 of orderedstructs including a C++/Python SkipList Paul Ross <apaulross@gmail.com> - 2021-04-29 10:44 +0100

#3622 — Release 0.3.4 of orderedstructs including a C++/Python SkipList

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.

[toc] | [standalone]

Back to top | Article view | comp.lang.python.announce

csiph-web