Очередь/база данных для планирования событий?

Question

В какой-то момент я, вероятно, создам свою собственную, но тем временем; есть язык-родовое событие планировщик взятие например: {time, priority, action} в качестве входных данных, то есть распределяемые через черепки, а также поддерживает:

• Епдиеие (PUSH) в O (1)
• Dequeue (поп) в O (войти п)
• следующих запланированная (найти-мин) в O (1)
• произвольного удаления в O (Log N), например: с помощью второй очереди приоритета, обозначенного delete_queue

Искал в Redis , но не смог найти пропе r для него.

Answer 1

Я не думаю, что вы можете реализовать такую ​​очередь с Redis с точным условием сложности, которое вы описываете для каждой операции.

Что вы можете сделать с Redis, используя zset. Внутренне zset реализуется как стандартная хеш-таблица плюс список пропусков (отсортированный по счету и значению). Таким образом, вы можете использовать оценку для хранения временных меток и значение для кодирования как приоритета, так и действия. Порядок в zset - это оценка сначала, а затем само значение (лексикографически сравнивается). Поэтому идея состоит в том, чтобы выбрать представление значения, лексикографический порядок которого соответствует логическому порядку, который вам нужен для приоритета. Здесь я предполагаю, что время имеет приоритет над приоритетом (т. Е. Приоритет используется только для заказа элементов, когда они имеют одну и ту же метку времени).

Например:

# timestamp=0, priority=3 
zadd myqueue 0 03-action1 

# timestamp=10, priority=2 
zadd myqueue 10 02-action3 

# timestamp=10, priority=1 
zadd myqueue 10 01-action2 

# The dequeuing order will be action1,action2,action3 
# (because of priorities) 

Я считаю, что сложность различных операций будет:

• Enqueue O (журнал N) [используя Zadd]
• DEQUEUE O (журнал N) [с помощью zremrangebyrank]
• следующий запланированный объект O (1) [используя zrange для извлечения первого элемента]
• произвольный del ete O (log n) [using zrem]

Они отличаются тем, что вы ищете, но они не так уж плохи.