SortedSet structure closely modelled after Redis' sorted sets

pip install sortedsets==1.0



Sorted set is data structure that maps unique keys to scores. The following operations are allowed on sorted set:

  • Iteration in order or scores (both ascending and descending)
  • Get score for key (same performance as for dict)
  • Get index for key (O(log n), n is sizeof the set)
  • Get key for index (O(log n))
  • Slicing by index (O(m + log n), m is length of slice)
  • Slicing by score (O(m + log n), m is length of slice)
  • Item/slice deletion by index and score (same performance as for slicing)
  • Insertion with any score has O(log n) performance too

The data structure is modelled closely after Redis' sorted sets. Internally it consists of a mapping between keys and scores, and a skiplist for scores.

The use cases for SortedSets are following:

  • Leaderboard for a game
  • Priority queue (that support task deletion)
  • Timer list (supports deletion too)
  • Caches with TTL-based, LFU or LRU eviction
  • Search databases with relevance scores
  • Statistics
  • Replacement for collections.Counter with faster most_common()

Example Code

Let's model a leaderboard:

>>> from sortedsets import SortedSet
>>> ss = SortedSet()

Insert some players into sortedset (with some strange made up scores):

>>> for i in range(1, 1000):
...    ss['player' + str(i)] = i*10 if i % 2 else i*i

Let's find out score for player:

>>> ss['player20'], ss['player21']
(400, 210)

Let's find out their rating positions:

>>> ss.index('player20'), ss.index('player21')
(29, 17)

Let's find out players that have score similar to one's:

>>> ss['player49']
>>> ss.by_score[470:511]
<SortedSet {'player22': 484, 'player47': 470, 'player49': 490, 'player51': 510}>
>>> for k, v in _.items():
...   print(k, v)
player47 470
player22 484
player49 490
player51 510

Let's find out players on the rating page 25:

>>> page, pagesize = 25, 10
>>> ss.by_index[page*pagesize:page*pagesize + pagesize]
<SortedSet {'player437': 4370, 'player439': 4390, 'player441': 4410, 'player443': 4430, ...}>
>>> len(_)