All Projects → ZhukovAlexander → py-skiplist

ZhukovAlexander / py-skiplist

Licence: WTFPL license
Pure python implementation of a skiplist data structure

Programming Languages

python
139335 projects - #7 most used programming language

Projects that are alternatives of or similar to py-skiplist

Chisel.prototype
Work in progress prototype for the Chisel Level Editor, for Unity
Stars: ✭ 247 (+696.77%)
Mutual labels:  mapping
osm-extracts
Each day, OSM Extracts by Interline mirrors the entire OpenStreetMap planet and creates city and region sized extracts
Stars: ✭ 34 (+9.68%)
Mutual labels:  mapping
nmt
Network mapping tool
Stars: ✭ 16 (-48.39%)
Mutual labels:  mapping
maptiles
Map tile generator. Converts an image into map tiles using ImageMagick. Map tiles can be used in Google Maps, Leaflet and other map rendering software.
Stars: ✭ 52 (+67.74%)
Mutual labels:  mapping
Spatial-Analysis-Mapping-Projects
Project Documentation, Best Practices & Procedures for Spatial Analysis and Mapping Projects
Stars: ✭ 15 (-51.61%)
Mutual labels:  mapping
gridviz
visualization of gridded statistics
Stars: ✭ 108 (+248.39%)
Mutual labels:  mapping
Gmapsfx
Java API for using Google Maps within a JavaFX application.
Stars: ✭ 233 (+651.61%)
Mutual labels:  mapping
WinDirStat.Net
A WPF implementation of WinDirStat.
Stars: ✭ 55 (+77.42%)
Mutual labels:  mapping
scale
📦 Toolkit for mapping abstract data into visual representation.
Stars: ✭ 53 (+70.97%)
Mutual labels:  mapping
JuliaAutonomy
Julia sample codes for Autonomy, Robotics and Self-Driving Algorithms.
Stars: ✭ 21 (-32.26%)
Mutual labels:  mapping
leafmap-apps
Interactive web apps created using leafmap and streamlit
Stars: ✭ 30 (-3.23%)
Mutual labels:  mapping
Papart-examples
Papart examples
Stars: ✭ 29 (-6.45%)
Mutual labels:  mapping
ufomap
UFOMap: An Efficient Probabilistic 3D Mapping Framework That Embraces the Unknown
Stars: ✭ 117 (+277.42%)
Mutual labels:  mapping
Contextily
Context geo-tiles in Python
Stars: ✭ 254 (+719.35%)
Mutual labels:  mapping
deck.gl-time-series-widget
A React Time Slider implementation for DECK.GL - (non)temporal data - by CPU filtering ⌛
Stars: ✭ 19 (-38.71%)
Mutual labels:  mapping
Ekylibre
Farm management Information System - Connecting farms to the world
Stars: ✭ 246 (+693.55%)
Mutual labels:  mapping
omnimapper
A Modular Multimodal Mapping Framework
Stars: ✭ 86 (+177.42%)
Mutual labels:  mapping
caltech samaritan
🚁〰️ Drone SLAM project for Caltech's ME 134 Autonomy class.
Stars: ✭ 35 (+12.9%)
Mutual labels:  mapping
earthengine-apps
A collection of Earth Engine Apps created using geemap, voila, and heroku
Stars: ✭ 20 (-35.48%)
Mutual labels:  mapping
mageri
MAGERI - Assemble, align and call variants for targeted genome re-sequencing with unique molecular identifiers
Stars: ✭ 19 (-38.71%)
Mutual labels:  mapping

skiplist-python

Pure python implementation of a skiplist data structure.

Build Status Coverage Status

Intro

Skip lists are a data structure that can be used in place of balanced trees. Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.

Skip lists are balanced by consulting a random number generator. Although skip lists have bad worst-case performance, no input sequence consistently produces the worst-case performance (much like quicksort when the pivot element is chosen randomly).

Example usage

>>>sl = Skiplist(foo='bar', 'spam'='eggs')
>>>sl
'skiplist({"foo": "bar", "spam": "eggs"})'
>>>
>>>sl['foo']
'bar'
>>>
>>>sl['foo'] = 'baz'
>>>sl['foo']
'baz'
>>>
>>>'spam' in sl
True
>>>
>>>del sl['spam']
>>>sl
'skiplist({"foo": "bar"})'

Skip List Structure

Each element is represented by a node, the level of which is chosen randoml when the node is inserted without regard for the number of elements in the data structure. A level i node has i forward pointers, indexed 1 through i. There is no need to store the level of a node in the node. Levels are capped at some appropriate constant MaxLevel. The level of a list is the maximum level currently in the list (or 1 if the list if empty). The header of a list has forward pointers at levels one through MaxLevel. The forward pointers of the header at levels higher than the current maximum level of the list point to NIL.

Skip List Algoritms

Skip list operations are analogous to that of a binary tree. They include: search, insert, and delete. Note that skip lists are easily extendable to support operations like "find the minimum key" or "find the next key".

Initialization

An element NIL is allocated and given a key greater than any legal key. All levels of all skip lists are terminated with NIL. A new list has level 1 and all forward pointers of the list's header point to NIL.

Search Algorithm

Search works by traversing forward pointers that do not overshoot the node containing the element being searched for. When no more progress can be made at the current level of forward pointers, the search moves down to the next level. When we can make no more progress at level 1, we must be in front of the node that contains the desired element (if it is in the list).

At what level should the search be started? William's analysis suggests that ideally we should start at level L where we expect log_{1/p}n where n is the number of elements in the list and p is the fraction of nodes in level i that also have level i+1 pointers. Starting a search at the maximum level in the list does not add more than a small constant to the expected search time.

Insertion and Deletion Algorithm

To insert or delete a node, we simply search and splice. A vector update is maintained so that when the search is complete, update[i] contains a pointer to the rightmost node of level i. The new node is of a random level. If the insertion generates a node with a greater level than the previous maximum, both Maxlevel and the appropriate portions of the update vector are updated. After each deletion, we check if we have deleted the maximum element of the list and if so, decrease the maximum level of the list.

References

Note that the project description data, including the texts, logos, images, and/or trademarks, for each open source project belongs to its rightful owner. If you wish to add or remove any projects, please contact us at [email protected].