Оптимальный алгоритм для списка задач (очередь с приоритетом). Как добавить запись в середину очереди без её смещения?

Question

[Роман Башарин]

Приветствую коллеги, на днях при разработке todo list'а возникла проблема, пока не разрешенная. Задача:
Есть список из пронумерованных записей (на самом деле их несколько, но для простоты возьмем один), нумерация определяет приоритет задач. Предположим, у нас есть массив из 5 задач [0, 1, 2, 3, 4], у нас возникла необходимость добавить ещё одну задачу на 2 по важности место, в итоге всё, что начиналось с 1-цы смещается на +1. Проблема начинается с того, что мы должны сразу же писать данные в БД, в данном случае только при 1 действии будет сделан 1 insert и 5 update'ов. Теперь предположим, что у нас список из 100 записей и 2000 активных клиентов. Одно перемещение задачи через drag'n'drop влечет за собой несколько десятков перезаписей в БД, если не тысяч.
Проблемы бы не было, если приложение крутилось на клиенте и по нажатии "Сохранить" шла бы некая оптимизированная перезапись, но приложение должно быть нативным, без всяких лишних кнопок, писать нужно сразу в БД.
Костыли-варианты:
1) Новый индекс будет среднее значение между вставляемыми числами (между 3 и 4, будет вставлено 3,5. А между 3 и 3,5 -> 3,25 и т.д.). При запросе массива будет ранжирования по возрастанию, но подобные float'ы (56,21875) будут сильно забивать базу и придётся писать костыль, чтобы перезаписывать эти индексы раз в сутки на нормальные
2) Индекс будет по типу "я следую за". Выдаем произвольные id'шники записям, далее отдельным параметром говорим после кого должна идти эта запись. В таком случае "внедряя" запись в середину очереди из млн. записей мы будем вносить в БД всего лишь 2 правки - того, кто был вставлен, и того у кого-нужно обновить связь. Но тут опять же придётся писать какое-то костыльное решение для построения этих взаимосвязей при отрисовке, делать генерацию хэшей айдишников, что не лучше float'ов.
3) Делать 50, 100 и т.д. update'ов в бд

Comments

[TekVanDo]

Непонятно почему не завести поле 'priority' и его сделать float, а id писать по человечески?

[Роман Башарин]

TekVanDo: сейчас так и есть. id по человечески, приоритет был как int и всё работало, пока перемещение было возможным только в конец списка, сейчас же можно произвольно менять очередность. Проблему описал выше.

Answer 1

[Роман Башарин]

0) Я правильно понял, что в первой таблице у нас хранятся обычные записи с id. Во второй по каждому клиенту мы храним массив по таблице вида

array(
  'priority0' => 'id345',
  'priority1' => 'id63452',
  'priority2' => 'id23',
  'priority3' => 'id9123'
)

И при изменении приоритета какой-либо из задач мы перезаписываем весь этот массив? С точки зрения лёгкости кода хороший вариант, но массивы будут довольно большие, т.к. в реальной ситуации таблиц несколько, кол-во задач по каждому человеку может доходить до нескольких сотен. Написать легко, но думаю будут проблемы с производительностью. Мне вот интересно, данную задачу ведь решили в той же Asana, да в принципе любом tasktracker-сервисе. Мне кажется что-есть какая-то математическая модель которая данную проблему как раз и решает.
1, 3 ---
2. На словах вариант красив, но пока не понятна реализация в коде. Видимо это должен быть foreach который будет формировать новый упорядоченный массив. При условии, что у нас 500 задач, это будет 500 циклов, пока сложно сказать, каким именно образом будет идти сопоставление, есть некоторые сомнения, что это будет супер быстро. Думаю, насколько это конкурентно по быстродействию с остальными вариантами.

Comments

[x67]

да, идея в этом. Но все должно быть в целых числах, без всяких строк. Для 2000 пользователей в минуту, активно сортирующих список из ста задач это будет перезапись 1,6 мб. Но это 2000 запросов по 800 байт (ключ int4+приоритет int4)*100, а не 32000 запросов по 20 байт(условно говоря).
Да, большие массивы в базах данных так хранить не очень удобно, но навряд ли у вас будут очень большие массивы.
2 вариант вполне хорош, когда задач немного. Советую в первую очередь вам оценить реальную нагруженность вашего сервиса пользователями и возможности серверного железа. Дальше уже можно делать выводы)

[Роман Башарин]

x67: пока выбрал вариант 2. При отрисовке страницы будет формироваться новый цикл на основе соответствия id задачи с атрибутом "я следую за 'id-родителя' Даже если у нас миллион задач, то построение нового массива займёт от силы несколько сотен миллисекунд, но при работе с этой таблицей на одну смену приоритета будет всего 2 перезаписи в базе. Та же Асана перед отрисовкой приложения думает несколько секунд, около 5 что ли.

[x67]

Роман: не забудь про удаление записей и возможные глюки(я следую за несуществующим объектом)

[Роман Башарин]

x67: да, разумеется, это самая очевидная проблема, на данный момент она уже решена. Теперь на запись в БД приоритетов стандартно всего 2 запроса делается, для той которую вставили и той которую сместили . Теперь возникла сложность с оптимизацией первоначальной отрисовки. Мы предполагаем, что элементы в наборе первоначально разбросаны в произвольном порядке, значит обычный цикл нам не подходит, приходится крутить foreach в while https://gist.github.com/anonymous/fcac6e1b1e042db5... в гисте указал свой код и там же пример массива который приходит из базы по каждой записи. В случае 10-20 задач, проверил через microtime скорость исполнения, пишет 0 секунд. типа супер быстро. Но мне с образовательной точки зрения интересно, как подобный алгоритм можно оптимизировать.

[x67]

Роман: я добавил бы поле ttBefore. Тогда за каждый проход цикла мы заполняем массив и сверху и снизу, условием выхода из цикла будет принадлежность элемента и к ttbefore и к ttafter. Я почти уверен, на больших объемах данных эффективнее будет модифицированная сортировка пузырьком или расчёской. Модификация в том, что если, к примеру, ттафтер первого элемента указывает не на второй, то ты второй меняешь местами с третьим, а не первый со вторым, как в случае пузырька

[Роман Башарин]

x67: Спасибо за совет, не знал про такие виды сортировок, я в принципе ничего про это не знаю. Может посоветуете литературу по алгоритмам, сортировкам и т.д. для не математиков? Где словами, а не формулами объясняют))

Answer 2

[x67]

может изменить структуру данных - хранить в одной таблице запись-ключ, а в другой для каждого клиента хранить матрицу или словарь с парами ключ - приоритет(ключ уникален для задания, значит мы получим сопоставление задания с приоритетом). Каждое добавление записи/задания влечет добавление записи в таблицу 1 и изменение записи в таблице 2. Изменение приоритета задания влечет только одно изменение записи в таблице 2. Сортировка, сопоставление происходит на стороне клиента, на сервер посылается уже готовый новый словарь. Каждый запрос будет больше весить, но что нам 1 запрос размером в 15 пар ключ-приоритет для среднего пользователя?
1 ваш вариант, имхо, сферический костыль, консервированный в жидком вакууме
2 вариант красив, но его нужно проработать и просчитать
3 вариант вообще не вариант естественно)

Answer 3

[vasiliev]

Задавать приоритеты как (0,100,200,300,400). Если надо вставить задачу между двумя другими, устанавливать её приоритет как округлённое до целого среднее. Если оказалось очень много записей и полученное число совпадает с одним из соседних, проводить пересчет приоритетов.

Comments

[Роман Башарин]

Я этот вариант рассматривал, это как вариация моего 1 примера, только там флоаты, а у вас int'ы. Этот вариант не подходит, если у нас в списке несколько тысяч задач или десятки тысяч. Такие числа хранить в БД довольно не прилично)