Skip to content

Instantly share code, notes, and snippets.

@antirez
Created June 7, 2016 16:40
Show Gist options
  • Save antirez/edb6a4b7aa32148632956c960214d9bb to your computer and use it in GitHub Desktop.
Save antirez/edb6a4b7aa32148632956c960214d9bb to your computer and use it in GitHub Desktop.

Random weighted element with Redis sorted sets

Imagine you have elements A, B and C with weights 1, 2 and 3. You compute the sum of the weights, which is 1+2+3 = 6

At this point you add all the elements into a sorted set using this algorithm:

SUM = ELEMENTS.TOTAL_WEIGHT // 6 in this case.
SCORE = 0
FOREACH ELE in ELEMENTS
    SCORE += ELE.weight / SUM
    ZADD KEY SCORE ELE
END

This means that you set:

A to score 0.16
B to score .5
C to score 1

Since this involves approximations, in order to avoid C is set to, like, 0.998 instead of 1, we just modify the above algorithm to make sure the last score is 1 (left as an exercise for the reader...).

At this point, each time you want to get a weighted random element, just compute a random number between 0 and 1 (which is like calling rand() in most languages), so you can just do:

RANDOM_ELE = ZRANGEBYSCORE key RAND() +inf LIMIT 0 1
@marswong
Copy link

it'll always get an error:

(error) ERR min or max is not a float

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment