Feature request: SRANDMEMBERS

[Running Turtle]

SRANDMEMBER returns only 1 random element from a set.

To obtain say, 10 random elements, I could issue the command ten times, but there would be no guarantee that all the 10 elements would be unique.

Therefore, it would be great if  SRANDMEMBERS key, nbrOfUniqueElements could be implemented.

If there's another trivial way to achieve this, please let me know.

[Pieter Noordhuis]

The problem is the same on the server side. Redis would have to sample
random members until it has samples 10 unique ones. This can be hard
when the set only contains 11 members, while it should be
straightforward when there are a million.

One way to solve this is to copy the set to a new key (SUNIONSTORE),
and use SPOP to get random members. Because it removes members from
the set, you are guaranteed not to get the same element twice. If you
want 10 random members, call SPOP 10 times. The only downside to this
approach is that it becomes quite costly because of the copy operation
when the set is large.

Cheers,
Pieter

> --
> You received this message because you are subscribed to the Google Groups
> "Redis DB" group.
> To view this discussion on the web visit
> https://groups.google.com/d/msg/redis-db/-/nokqMHIgamoJ.
> To post to this group, send email to redi...@googlegroups.com.
> To unsubscribe from this group, send email to
> redis-db+u...@googlegroups.com.
> For more options, visit this group at
> http://groups.google.com/group/redis-db?hl=en.

[Salvatore Sanfilippo]

Hi dudes I'm actually implementing this operating right now. It's on
my todo list since ages and I think there are a few ways to implement
it in a fast way.

Let's pick MAGIC=2 (but the right value will be chosen with
redis-benchmark in an empirical way).

Command is SRANDMEMBERS <count>

First observation: if there is no count a bulk reply is returned. With
count a multi-bulk reply is returned (even if count is == 1 of
course).

Ok, so:

1) If SET_SIZE < count ---> Just serve the request with SMEMBERS as
the user asked for all the elements.
2) if SETSIZE < count * MAGIC ---> Serve the request populating a
dictionary with all the Set members, than remove elements one after
one with dictGetRandomKey() + dictDel(), so that the dictionary has
count elmenets at the end.
3) If SETSIZE >= count * MAGIC ---> Serve the request adding random
elements obtained with dictGetRandomKey() to a dictionary, not
counting duplicated elements.

In this way we always avoid pathological behaviour, making sure the
operation is reasonably fast in all the circumstances.

I think it's worth adding since:

1) We have a semantically free third argument to exploit.
2) There is no return type change for the vanilla request.
3) This is the kind of stuff that sucks done client side and it is
easy to do the wrong way.
4) Lua scripting is surely an alternative from this point of view, but
because of the "random" behaviour of the command and the subtleness
needed to implement it efficiently, it's worth a few C lines of code.
5) It is an *extremely* general operation asked by the community for
years at this point.

Exect it to it 2.6 / unstable branches in a few hours at max. An
announcement will follow.

Cheers,
Salvatore

--
Salvatore 'antirez' Sanfilippo
open source developer - VMware
http://invece.org

Beauty is more important in computing than anywhere else in technology
because software is so complicated. Beauty is the ultimate defence
against complexity.
— David Gelernter

[Running Turtle]

Excellent news. Cheers !

[Salvatore Sanfilippo]

Hello all, I just finished a first implementation of the new variant
of SRANDMEMBER.
It still lacks testing and so forth, I'll work on it tomorrow.

The code (surprisingly non trivial at all) ->
https://github.com/antirez/redis/compare/srandmember

What follows is a "demo" of how the command works.
Note that we are still in a malleable development stage so if you see
something odd with the API please tell me.

$ ls
add.rb census-dist-female-first.txt

$ cat add.rb
require 'rubygems'
require 'redis'

r = Redis.new
r.del(:set)
File.open("census-dist-female-first.txt").each_line{|l|
r.sadd(:set,l.split(" ")[0])
}

$ ruby add.rb
$ redis-cli
redis 127.0.0.1:6379> scard set
(integer) 4275

redis 127.0.0.1:6379> srandmember set
"ZADA"

redis 127.0.0.1:6379> srandmember set 5
1) "DEANA"
2) "ROCHEL"
3) "ELYSE"
4) "MARGO"
5) "MALKA"

redis 127.0.0.1:6379> srandmember set 3
1) "TISH"
2) "LEZLIE"
3) "BRITTA"

redis 127.0.0.1:6379> srandmember set -5 (Note: negative allows
repeated elements)
1) "ROMANA"
2) "JAMES"
3) "BLAKE"
4) "BETH"
5) "ROMANA"
redis 127.0.0.1:6379>

$ redis-benchmark -P 32 -q -n 1000000 ping
ping: 431034.50 requests per second
$ redis-benchmark -P 32 -q -n 1000000 srandmembers set 5
srandmembers set 5: 165782.48 requests per second
$ redis-benchmark -P 32 -q -n 1000000 srandmembers set -5
srandmembers set -5: 167869.73 requests per second

[Chris Love]

Grazie Mille Salvatore!!!!

We have been waiting for this :)

Thanks again

Chris

[Felix Gallo]

Actually this would be straightforward on the server side; probably the easiest thing to do would be to copy and modify setTypeRandomElement in t_set.c to loop on dictGetRandomKey() instead of just getting one, and return multiple values; see existing code below.

F.

int setTypeRandomElement(robj *setobj, robj **objele, int64_t *llele) {

    if (setobj->encoding == REDIS_ENCODING_HT) {

        dictEntry *de = dictGetRandomKey(setobj->ptr);

        *objele = dictGetKey(de);

    } else if (setobj->encoding == REDIS_ENCODING_INTSET) {

        *llele = intsetRandom(setobj->ptr);

    } else {

        redisPanic("Unknown set encoding");

    }


    return setobj->encoding;

}