[Feature Reequest]

[GoogleCodeExporter]

Hi, 

The project I am currently working in, needed a fast leaderboard module.
I've got several approach / technical solutions, and redis is one of them,
thanx to the future zset feature.

Anyway, I needed a way to retrieve the rank of an element within a zset. I
am using the following code (with the linked modifications the rest of the
code).
Hope you will be able to consider my request, an eventually use (a part of)
this code

regards

Bertrand

static void zrankCommand(redisClient *c) {
    robj *o;

    o = lookupKeyRead(c->db,c->argv[1]);
    if (o == NULL) {
        addReply(c,shared.nullbulk);
        return;
    } else {
        if (o->type != REDIS_ZSET) {
            addReply(c,shared.wrongtypeerr);
        } else {

            zset *zsetobj = o->ptr;
            zskiplist *zsl = zsetobj->zsl;
            zskiplistNode *ln;
            dictEntry *de;

            de = dictFind(zsetobj->dict,c->argv[2]);
            if (!de) {
                addReply(c,shared.nullbulk);
            } else {
                int cpt = 1;
                double *score = dictGetEntryVal(de);

                ln = zsl->tail;
                while (ln->score != *score) {
                    ln = ln->backward;
                    cpt ++;
                }
                addReplyDouble(c, cpt);
            }
        }
    }
}

Original issue reported on code.google.com by Bertrand...@gmail.com on 30 Nov 2009 at 5:32

Attachments:

• 0001-implement-the-zrank-command.patch

[GoogleCodeExporter]

sorry for the typo and the poor post title

Original comment by Bertrand...@gmail.com on 30 Nov 2009 at 5:33

[GoogleCodeExporter]

Hello! This is a nice idea in theory... but in practice it's an O(N) operation! 
This is not 
going to scale so this only gives the illusion of solving a problem in my 
opinion. I'll 
leave this issue open to think better about it.

Cheers,
Salvatore

Original comment by anti...@gmail.com on 30 Nov 2009 at 5:52

[GoogleCodeExporter]

I notice that adds into the sorted sets is O(log(n)), so I think you could get 
a rank
in at least log(n) as well. This is assuming you're using some kind of tree to 
do the
sorting. Basically, at every node in the tree, you store the total number of 
elements
to the left and to the right.

So when you are navigating to a leaf you can use the number of elements you 
know to
be less than it so far. If your child-nodes are linked back to the parent nodes 
and
your hash structure is linked to the tree, then you could even find the node and
count up through the parents.

The hard part is maintaining those left and right sizes on inserts, removes, and
depending on your tree re-balancing.

Original comment by tyler...@gmail.com on 17 Dec 2009 at 11:22

[GoogleCodeExporter]

This feature is now available on git (as a log(N) operation). Docs at: 
http://code.google.com/p/redis/wiki/ZrankCommand

Original comment by pcnoordh...@gmail.com on 17 Mar 2010 at 4:27

• Changed state: Fixed