在Redis列表中,通过值获取一个项的索引

17

我创建了一个redis列表,目前将其用作反转的队列。我的问题是,我想能够通过值获取该队列/列表中项的索引。

示例

如果我有一个包含以下值的列表:

{"dan","eduardo","pedro"}

索引将会是:

0 : "dan"
1 : "eduardo"
2 : "pedro"
我想通过传入一个值来获取它在我的列表中的索引。 比如像"eduardo",返回'1'。 如果可能的话,怎么做呢? 我应该说一下,我正在对我的列表执行队列命令,从顶部删除项目并将它们添加到底部。 我目前正在使用node.js 0.6.6和最新的redis模块以及最新的redis版本2.4.4。 我希望仅在redis-cli中找到解决方案。 除了必须仅使用redis而没有外部进程之外,没有其他限制,但如果您想使用带有lua的EVAL命令,请使用它。 编辑 我认为我的答案可能在有序集上而不是队列上。

1
Redis已经发展壮大,截至Redis 6.0.6,现在有一个解决方案可以完全做到这一点。您能否更改您接受的答案并选择显示解决方案的答案?谢谢! - seinecle
6个回答

12
使用有序集合实现队列。
将成员添加到有序集合中,并使用时间戳作为分值。
> ZADD queue 1326990501 foo 1326990502 bar 1326990503 baz 1326990504 qux
(integer) 4

使用ZRANGE命令可以按先进先出的顺序返回成员。

LIFO:

使用ZREVRANGE命令可以按后进先出的顺序返回成员。

> ZRANGE queue 0 0
"foo"

后进先出:

> ZREVRANGE queue 0 0
"qux"

使用ZRANK可以找到成员的索引。ZRANK操作的时间复杂度为O(log(N))。

> ZRANK queue bar
(integer) 1

如果我在集合中移动项目,得分会自动更新吗?例如,如果所有得分都是1到100,如果我将集合中的第一个项目更改为101,其他项目的得分不会改变,对吗? - dmportella
我不确定我理解这个问题。如果您更改排序集合中成员的分数,它的排名(索引)也可能会发生变化。任何给定成员的排名取决于排序集合中所有其他成员的分数。因此,为什么ZRANK是O(log(N))。我不确定这是否回答了您的问题,但您可以在redis-cli中尝试使用排序集合,您可能会找到您要寻找的答案。 - Simon Klee
改进一下,我认为你已经解决了大部分问题,但是管理一个排序集合上的分数,它像一个队列一样运作,其中项目从顶部移动到底部,可能会反转,例如从底部移动到顶部的项目会产生很多开销,因为项目每250毫秒就会移动一次。别误会,你的答案很好,但我无法承受得起分数管理的开销。 - dmportella

10

我不知道Nodejs客户端的详细信息,但以下是在Lua中实现非常简单的indexOf命令的代码。

在我的文件indexof.lua中,我有以下代码:

local key = KEYS[1]
local obj = ARGV[1]
local items = redis.call('lrange', key, 0, -1)
for i=1,#items do
    if items[i] == obj then
        return i - 1
    end
end 
return -1

让我们向mylist推送一些值。

> rpush mylist foo bar baz qux
(integer) 4

我们可以使用lua脚本来查找列表中任何值的索引。该命令的时间复杂度为O(N)。

$ redis-cli --eval indexof.lua mylist , bar
(integer) 1

bar 的索引为 1。

> lindex mylist 1
"bar"

nil 的索引为 -1

$ redis-cli --eval indexof.lua mylist , nil
(integer) -1

请查看 EVAL 命令的更多文档


3
这是一个有趣的Lua使用示例。然而,代价是完整复制列表,再加上Lua中的线性搜索。它只适用于小型列表。对于大型列表,它会使Redis循环停滞数秒并且消耗过多内存。 - Didier Spezia
1
这个答案提供的解决方案是否是一个好选择,取决于应用程序。根据问题描述,没有迹象表明队列的大小。为了具有较低的内存开销,我们需要使用不同的搜索算法,并且为此列表必须按值排序。此外,如果这是在大量项目上执行的操作,我认为使用zrank和排序集合听起来更像是一个更好的解决方案。 - Simon Klee
队列长度最多可达10000项,且会不断变化,每200毫秒有元素出队或入队。 - dmportella

9

使用 LPOS 命令(自 6.0.6 版本起可用)可以获取 Redis 列表中元素的索引。

根据文档

  • 命令 - LPOS key element [FIRST rank] [COUNT num-matches] [MAXLEN len]
  • 该命令返回 Redis 列表中匹配元素的索引。
  • 当未指定任何选项时,默认情况下,它将从头到尾扫描列表,查找“element”的第一个匹配项。如果找到了元素,则返回其索引(列表中以零为基础的位置)。否则,如果没有找到匹配项,则返回 NULL。

所以在您的情况下,对于键为 users 的列表{"dan","eduardo","pedro"}

LPOS users eduardo

必须返回1。我个人没有在lua脚本中使用过它,因此不提供脚本,但我相信应该很简单。


这是现在(截至版本6.0.6)的正确答案。它需要点赞。 - David Parks
已更新为被接受的答案,感谢您让我们知道。 - dmportella

8

现在你可能已经注意到了,Redis不支持这样的操作(难过的表情)。

尽管有人对为什么需要这样的操作进行了一些很好的解释,但看起来Salvatore不会很快实现它。

基本上有两种解决方法(正如其他答案所指出的):

  • 使用自定义lua脚本查找列表中的索引;
  • 使用带有时间戳作为分数和ZRANK索引的排序集(而不是列表)。

由于第一个方法的时间复杂度为O(N),而后者只有O(log(N)),所以你可能可以想象哪个更胜一筹。

无论如何我决定进行测试*:

╔════════════════╦═══════════════════════╦══════════════════════╗
║                ║ Sorted Set with ZRANK ║ List with lua script ║
╠════════════════╬═══════════════════════╬══════════════════════╣
║  1000 elements ║   0.0638264 seconds   ║   0.2723238 seconds  ║
╠════════════════╬═══════════════════════╬══════════════════════╣
║ 10000 elements ║   00.4484714 seconds  ║  41.0661683 seconds  ║
╚════════════════╩═══════════════════════╩══════════════════════╝

是的,仅对一万个元素进行操作就需要惊人的41秒。

* 在Windows 7上,使用Redis 2.8(MSOpenTech port),.NET 4编译器优化和StackExchange.Redis 1.0.488。


5
根据redis.io问题列表中的第140个票据,提出了一个功能请求:lRank。"嗨,这个命令可能不会被实现,因为它既是一个O(N)命令,而且通常只在数据布局设计存在错误时才会被感觉到需要。" Salvatore Sanfilippohttps://github.com/antirez/redis/issues/140上说道。我不太确定为什么想要通过值找出项目的索引可能会是数据设计上的错误。但是他明确表示可以使用lua代码和/或排序集合。所以总之,除了使用lua脚本,没有其他方法可以找到列表中项目的索引。然而,根据实现方式,即数据设计,考虑使用排序集合可能更好。

1
使用有序集合(ZADD等)可以使用ZRANK
编辑:我的旧答案不起作用,因为您的列表会发生更改,尽管它使用RPUSH仅增长的列表。
您可以将索引与值(或其哈希)一起存储为键:
set listvalue listindex

为了保持你的 Redis 有条理,你可以在那些键前加上列表名称的前缀:
set listname:listvalue listindex

我不确定你的意思,能否提供一个例子? - dmportella
我认为使用排序集会起作用,但是如果我想保持正确的数字,我需要在对表进行每次更改时更新每个人的index.score。 - dmportella
ZRANK返回有序集合中键的排名(即索引)。 - mtsr
这没问题,我理解。但是我认为我仍然需要更新分数,以改变项目的顺序,以模仿队列行为。 - dmportella
1
啊哈,是的。这就是有序集合的概念。如果你再次对相同成员进行ZADD,它的分数将更新为新的分数。或者你可以使用ZINCRBY来增加/减少分数而不需要先查找。但这主要用于优先队列,而不是LIFO或FIFO。 - mtsr

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接