SortedSets

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']
490
>>> 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(_)
10