Получить индекс элемента по значению в повторном списке

Question

У меня есть список повторного создания, который я создал, я использую его в качестве очереди в тот момент, когда время от времени меняются местами. Моя проблема в том, что я хотел бы иметь возможность получить индекс элемента в этой очереди / списке по значению.

* ** 1003 тысяча два * Пример

Если у меня есть список со следующими значениями:

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

Индексы будут:

0 : "dan"
1 : "eduardo"
2 : "pedro"

Я хочу быть в состоянии передать значение, чтобы получить индекс этого значения в моем списке.

Как "eduardo" и получить обратно "1".

Возможно ли это, если да, как бы вы это сделали?

Также я должен сказать, что я выполняю команды очереди в своем списке, удаляя элементы сверху и добавляя их внизу.

В настоящее время я использую node.js 0.6.6 и последний модуль redis с последней версией redis 2.4.4.

Я рад за решение только в Redis-Cli.

Кроме того, нет никаких других ограничений, тогда должно быть возможно сделать это только с помощью redis, без внешнего процесса и т. Д., Однако, если вы хотите использовать команду EVAL с lua go для этого.

Редактировать

Кроме того, я думаю, что мой ответ может быть в отсортированных наборах, а не в очередях.

Answer 1

Я не знаю подробностей клиента nodejs для этого, но ниже приведена реализация очень простой команды indexOf в lua.

В моем файле 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

Посмотрите http://redis.io/commands/eval дополнительную документацию по команде EVAL.

Answer 2

Использование отсортированных наборов для реализации очереди.

Добавление участников и использование метки времени в качестве оценки.

> ZADD queue 1326990501 foo 1326990502 bar 1326990503 baz 1326990504 qux
(integer) 4

Вы можете возвращать элементы в порядке FIFO и LIFO, используя ZRANGE и ZREVRANGEсоответственно.

FIFO:

> ZRANGE queue 0 0
"foo"

LIFO:

> ZREVRANGE queue 0 0
"qux"

Чтобы найти индекс члена, используйте ZRANK.ЗРАНК ОПЕРАЦИЯ (log (N))

> ZRANK queue bar
(integer) 1

Answer 3

Как вы уже можете сказать, Redis не поддерживает такую ​​операцию (грустное лицо).

Хотя кто-то сделал несколько неплохих замечаний о том, почему такая операция имеет смысл , выглядиткак Сальваторе не будет реализовывать это в ближайшее время.

В основном есть два обходных пути (как указано в других ответах):

• Используйте собственный скрипт 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 ), .NET 4 с включенной оптимизацией компилятора и StackExchange.Redis 1.0.488.

Answer 4

Согласно заявке 140 в списке вопросов о redis.io

Запрос функции: lRank

"Привет, эта команда, скорее всего, не будет реализована, поскольку онаэто и команда O (N), и та, которая обычно считается необходимой только тогда, когда есть какая-то ошибка в дизайне макета данных. " Salvatore Sanfilippo on https://github.com/antirez/redis/issues/140.

Я не совсем уверен, почему и как желание найти индекс элемента по значению может быть ошибкой в ​​дизайне данных.Однако он ясно дает понять, что вы можете использовать код lua и / или отсортированные наборы.

Таким образом, в итоге нет способа узнать индекс элемента вперечислите другие, кроме , используя скрипт lua .

Однако в зависимости от реализации, то есть дизайна данных, может быть лучше рассмотреть отсортированные наборы вместо списков.

Answer 5

Используя отсортированные наборы (ZADD и т. Д.), Вы можете использовать ZRANK .

Редактировать: мой старый ответ ниже не работает, потому что ваш список меняется, хотя и меняется ссписок, который увеличивается только с помощью RPUSH.

Вы можете сохранить индекс со значением (или его хеш-кодом) в качестве ключа:

set listvalue listindex

Чтобы организовать перерисовку, вы можете использовать префиксэти ключи со списком имен:

set listname:listvalue listindex