Ratel
Skip list is a data structure that allows fast search within an ordered sequence of elements and a probabilistic alternative to Balanced Trees.It is also easier to implement. This library uses redis skip list to implement SortedSet data types for Python
This library modified in four ways:
- This implementation is allowed to repeated scores.
- The comparison is not just by score but by key data.
- It's a doubly linked list with the backward being only at "level 1". This allows to traverse the list from tail to head, useful for zrevrange.
- This implementation is combined with dict data structure for fast search.
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 redis skip lists to implement SortedSet data types for Python.
SortedSet is implemented in Python and C with high performance.
Here is a few examples:
from boost_collections.zskiplist.zset_node import ZsetNode
from boost_collections.zskiplist.zset_obj import ZsetObj
zset_obj = ZsetObj()
elements = [ZsetNode('a', 1), ZsetNode('a', 2), ZsetNode('c', 2)]
# multi elements added
zset_obj.zadd(elements=elements)
# multi elements added nx
zset_obj.zadd(elements=elements, 'nx')
# one element added
zset_obj.zadd(elements=ZsetNode('d', 1))
# zincrby
zset_obj.zincrby(ZsetNode('a', 1), 'incr')
# zcard
zset_obj.zcard()
# zscore
zset_obj.zscore('a')
# zrange
zset_obj.zrange(0, -1, True)
# zrevrange
zset_obj.zrevrange(0, 1, True)
# zrange_by_score
zset_obj.zrange_by_score(1, 0, 2, 0)
# zrevrange_by_score
zset_obj.zrevrange_by_score(1, 0, 2, 0)
Compatibility
- Python 2.7, 3.5+
Installation
pip install ratel
or
https://github.com/524243642/ratel
cd ratel
python setup.py install
Time Complexity
| ZsetObj Operations | Average Case |
|---|---|
| zadd | O(log N) |
| zincrby | O(log N) |
| zrem | O(log N) |
| zscore | O(1) |
| zcard | O(1) |
| zrange | O(log(N) + M) |
| zrevrange | O(log(N) + M) |
| zfloor | O(log N) |
| zlower | O(log N) |
| zrange_by_score | O(log(N) + M) |
| zrevrange_by_score | O(log(N) + M) |
Release
0.3.4 2018-12-04 zadd zincrby zrem zscore zcard zrange zrevrange
0.4.0 2018-12-23 zfloor zlower
0.4.1 2019-01-23 shields.io access
0.5.0 2019-04-25 zrange_by_score zrevrange_by_score
1.0.0 2020-11-23 stable version released
1.0.1 2020-11-24 python 3.7+ supported
License
MIT
Contributing
Welcome to feedback and improvements.Please submit a pull request!
1 maintainer
Metadata
1 maintainer
Release files for ratel 1.0.1
For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.
Source distribution (sdist)
| File | Size | Uploaded | |
|---|---|---|---|
| ratel-1.0.1.tar.gz | 13.5 kB | Details |
Release files / ratel-1.0.1.tar.gz
| Download URL | ratel-1.0.1.tar.gz |
|---|---|
| Size | 13.5 kB |
| Tags | Source |
|
SHA-256 checksum How to use checksums |
2770fb8818969ae1415f8d37fb85c4854e1a4b325b43c654c1e05ed22eebc9c7
|
|
BLAKE2b-256 checksum How to use checksums |
5917c980aa1a5064125300565dd15742d848eced1c166646c600d89fde2edffa
|
| Upload date | |
|
Uploaded using Trusted Publishing? What is trusted publishing? |
No |
| Uploaded via |
twine/3.2.0 pkginfo/1.6.1 requests/2.23.0 setuptools/50.3.2 requests-toolbelt/0.9.1 tqdm/4.46.0 CPython/3.8.3
|
