Skip to content

SortedDict and SortedSet implementation for Python

Notifications You must be signed in to change notification settings

sepeth/python-skiplist

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

96 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

python-skiplist

Build Status Coverage Status Code Health

Skip Lists are data structure that can be used in place of balanced trees. They are easier to implement and generally faster. This library uses skip lists to implement SortedDict and SortedSet data types for Python.

SortedSet is implemented in C and it uses CPython C API, and SortedDict is a thin wrapper on top of SortedSet.

Here is a few examples:

>>> from skiplist import SortedSet, SortedDict
>>> d = SortedDict({'elma': 1, 'armut': 2, 'kel': 3, 'mahmut': 4})
>>> d
SortedDict({'armut': 2, 'elma': 1, 'kel': 3, 'mahmut': 4})
>>> del d['kel']
>>> d
SortedDict({'armut': 2, 'elma': 1, 'mahmut': 4})
>>> cities = SortedSet(['Canakkale', 'Zurih', 'Izmir', 'Bolu', 'Istanbul'])
>>> cities
SortedSet(['Bolu', 'Canakkale', 'Istanbul', 'Izmir', 'Zurih'])

Installation

$ pip install python-skiplist

Asymptotic Bounds

SortedSet Operations Average Case
add O(log N)
discard O(log N)
contains O(log N)
length O(1)
SortedDict Operations Average Case
_setitem_ O(log N)
_getitem_ O(1)
_delitem_ O(log N)

About

SortedDict and SortedSet implementation for Python

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published