Wicked
Новичок
Работа с наборами очередей
Всем известно, что такие структуры данных как деревья (двоичные, b-tree, и т.д.), кучи и т.д. вполне пригодны для хранения приоритезированных очередей и позволяют делать быстрые вставки и выборки.
Рассмотрим более общий случай:
Допустим, у нас есть несколько именованных очередей: q1, q2, q3, ... Как в memcacheq.
У нас также есть разборщики очередей, которые могут каждый раз хотеть наиболее важную задачу:
а) из некоторого заранее неизвестного набора очередей - худший случай;
б) из некоторого заранее известного набора очередей (например, всегда выбирает выбирает либо из (q1, q2), либо из (q3, q4), либо из (q1, q5)) - лучший случай; Удобно об этом мыслить в терминах тегов для очередей.
Но пока что известные мне стратегии выбора наиболее приоритетной задачи из множества очередей сводятся к простому перебору: мы смотрим на самую приоритетную задачу в каждой из очередей и из них выбираем нужную. Это довольно неплохо на практике в случае, когда:
1) кол-во очередей, участвующих в выборках - мало, даже если самих очередей - туча.
2) техническая реализация сервера очередей позволяет делать такое атомарное действие. В том же memcacheq, насколько я понимаю, если мы сделаем мультигет, он выберет по топовой задаче из каждой очереди, и удалит их у себя.
Если говорить о выборки из тегов, то мне даже видится следующее возможное улучшение: каждый тег тоже может представлять из себя вспомогательную приоритезированную очередь ("очередь тега") с кол-вом задач = сумме кол-в задач во всех "оригинальных очередях", отмеченным этим тегом. Каждая их задач в "очереди тега" имеет приоритет задачи из оригинальной очереди и содержит в себе только имя оригинальной очереди. Т.е. процесс выборки топовой задачи из тега сводится к:
1) выбрали топовую задачу из очереди тега.
2) из нее поняли, из какой оригинальной очереди нужно выбрать задачу с детальным описанием.
3) выбрали топовую задачу из той оригинальной очереди.
Еще теги можно реализовать с помощью куч, тогда оверхед по месту будет вообще несущественным, просто нужно будет их как-то перезаполнять. Но остается проблема с поддержанием целостности между очередями тегов и основными очередями, т.е. такое должен уметь делать сам сервер очередей.
Собственно вопросы:
1) может быть существует какая-нибудь структура данных именно для быстрой работы с наборами очередей? На ум приходит что-то типа r-tree, но вот именно она не годится. Моих знаний пока не хватает, но постараюсь найти и сам
2) знаете ли вы какие-нибудь open-source проекты, где были бы решены подобные проблемы?
Всем известно, что такие структуры данных как деревья (двоичные, b-tree, и т.д.), кучи и т.д. вполне пригодны для хранения приоритезированных очередей и позволяют делать быстрые вставки и выборки.
Рассмотрим более общий случай:
Допустим, у нас есть несколько именованных очередей: q1, q2, q3, ... Как в memcacheq.
У нас также есть разборщики очередей, которые могут каждый раз хотеть наиболее важную задачу:
а) из некоторого заранее неизвестного набора очередей - худший случай;
б) из некоторого заранее известного набора очередей (например, всегда выбирает выбирает либо из (q1, q2), либо из (q3, q4), либо из (q1, q5)) - лучший случай; Удобно об этом мыслить в терминах тегов для очередей.
Но пока что известные мне стратегии выбора наиболее приоритетной задачи из множества очередей сводятся к простому перебору: мы смотрим на самую приоритетную задачу в каждой из очередей и из них выбираем нужную. Это довольно неплохо на практике в случае, когда:
1) кол-во очередей, участвующих в выборках - мало, даже если самих очередей - туча.
2) техническая реализация сервера очередей позволяет делать такое атомарное действие. В том же memcacheq, насколько я понимаю, если мы сделаем мультигет, он выберет по топовой задаче из каждой очереди, и удалит их у себя.
Если говорить о выборки из тегов, то мне даже видится следующее возможное улучшение: каждый тег тоже может представлять из себя вспомогательную приоритезированную очередь ("очередь тега") с кол-вом задач = сумме кол-в задач во всех "оригинальных очередях", отмеченным этим тегом. Каждая их задач в "очереди тега" имеет приоритет задачи из оригинальной очереди и содержит в себе только имя оригинальной очереди. Т.е. процесс выборки топовой задачи из тега сводится к:
1) выбрали топовую задачу из очереди тега.
2) из нее поняли, из какой оригинальной очереди нужно выбрать задачу с детальным описанием.
3) выбрали топовую задачу из той оригинальной очереди.
Еще теги можно реализовать с помощью куч, тогда оверхед по месту будет вообще несущественным, просто нужно будет их как-то перезаполнять. Но остается проблема с поддержанием целостности между очередями тегов и основными очередями, т.е. такое должен уметь делать сам сервер очередей.
Собственно вопросы:
1) может быть существует какая-нибудь структура данных именно для быстрой работы с наборами очередей? На ум приходит что-то типа r-tree, но вот именно она не годится. Моих знаний пока не хватает, но постараюсь найти и сам
2) знаете ли вы какие-нибудь open-source проекты, где были бы решены подобные проблемы?
