Feature Request: lRank

[belov1985]

Please, add support to determine the index of a member in a list.

P. S.
I have array with unique numbers stored in the redis list. And there is no reason to use sorted set (overhead, when member equal score :()

Tnx.

[belov1985]

Just answer, wait for this feature in near redis builds or not? :)

[antirez]

Hi, this command will likely not be implemented as it is both an O(N) command and one that usually is felt as needed only when there is some error in the data layout design.

But the good news is that with scripting in 2.6 you can implement it with very little Lua code if you really need it. However the reason for using a sorted set in this context is that is the right data structure to use. Think about this:

• If you want LINDEX or alike, you are hoping your list is small enough, otherwise it is unusable form a performance point of view.
• But if your list is small, you can use a sorted set since now with 2.4 they are specially encoded when they are small, so no additional memory is used compared to a list (or very little additional memory).

Conclusion? Use 2.6 scripting if you really want it, but likely you want to change your implementation.

Closing the issue. Thanks for submitting anyway!

Cheers,
Salvatore

[dmportella]

Please check my stackoverflow question it will explain what i am doing and hopefully give a reason why i wanted to added this feature

http://stackoverflow.com/questions/8899111/get-the-index-of-an-item-by-value-in-a-redis-list

[dmportella]

I am using a list as a reversible queue, so items change places all the time just, basically a roulette that moves around and at any one time i want to know the index of an item.

[yehosef]

lindex is also O(N) - I don't think that the complexity should be a factor here. Even if the overhead of a sorted set is the same, the use case is different - with a sorted set I have to maintain my score ahead of time, with a list I don't. I can push/pop, etc.

[ThisGuyCodes]

We are also using a list as a reversible queue (specifically in rq). These queues can get considerably large, and by far the most common operation is adding or removing to them. Luckily these operations are O(1) in redis, but now we desire a way to locate a jobs position in the queue (more specifically, the list of jobs ahead of it

I understand sorted sets are the recommended solution, but I don't see how that's reasonable here: adding and removing from sorted sets is O(log(N)), which would not be ok, we add/remove from our lists some orders of magnitude more frequently than we try to do this check.

I would also like to point out that a command that is already provided (lrem) does exactly what's needed here, but deletes keys rather than returns an index; so I don't see how the complexity argument applies (LSET, and LINDEX, are also O(N))

In fact, there are several commands that already do the sort of work required, but have problems associated with using them.

We could use LINSERT as a hack by inserting junk values if it returned the element position modified instead of the resulting total length, or LRANGE with some arbitrary incremental value, but then we'd duplicate a ton of work since LRANGE is O(start+retrieved), and returning the whole list with a LRANGE while less complex as O(N) in the worst case (end of the list) is still more complex in practice than stopping at the desired value, incurs an unnecessary search on the list client side, and brings with it other complications (large lists = long network transfer time + potentially doesn't fit in memory on the client, redis boxes in production environments are often on specially large-memory instances).

Even if it's not a straightforward scan, is there some more redis-like solution here? I know I could use a lua script but my general rule of thumb is if I have to use a script in redis for something so small (specifically: other than so commands can interact with each other atomically) then there's likely a better way. So when working with a list used as a queue, is the best solution really to turn the most common operation from O(1) to O(log(N))? (plus, I don't know about about maintaining this list, would I have to decrement every member by one when removing, and get the previous highest when adding? Or can I avoid that and just keep adding, but what are the integer size limits here?)

[mattsta]

I would also like to point out that a command that is already provided (lrem) does exactly what's needed here, but deletes keys rather than returns an index;

That's a good point. There's also discussion in the comments at http://redis.io/commands/lrem