Повторное ранжирование элементов без изменения рангов всех элементов

У меня есть список предметов, каждый из которых имеет ранг, связанный с ним. 

Item 1, Rank=1
Item 2, Rank=2
Item 3, Rank=3
Item 4, Rank=4
Item 5, Rank=5

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

Одно из решений, которое я придумал, состояло в том, чтобы использовать десятичные дроби и использовать тип двойной переменной Java. Так, например, если я перемещаю item5 между item2 и item3, это будет выход - 
Item 1, Rank=1
Item 2, Rank=2
Item 5, Rank=2.5
Item 3, Rank=3
Item 4, Rank=4

И так далее, 

Item 1, Rank=1
Item 2, Rank=2
Item 4, Rank=2.25
Item 5, Rank=2.5
Item 3, Rank=3

Это решение работает, но через некоторое время (~55 ходов на то же самое положение, я достигаю предела двойной переменной, и мне, вероятно, придется сбросить все ранги в этой точке)

Мне просто интересно, есть ли какой-то лучший способ решить эту проблему?

Несколько вещей, которые нужно иметь в виду.

  • мне нужно сохранить эту структуру данных в базе данных (Item, Rank), и я буду создавать веб-сервис, который получает все элементы в отсортированном порядке на основе ранга, поэтому я буду делать вызов DB, чтобы получить все элементы, отсортированные по полю ранга.
  • я буду использовать Java, поэтому я могу работать только с переменными Java.
2 4
sorting algorithm rank ranking

2 ответа:

Как насчет написания небольшой процедуры, которая равномерно распределяет Ранговые значения диапазона элементов в массиве (или списке, или чем-то еще)?

Если вы вставляете новый элемент в позицию x, вы передаете элементы диапазона x-1 .. x+1 в подпрограмму. значения рангов в начальной и конечной позиции остаются неизменными, остальные рассчитываются с четным расстоянием. В случае успеха возвращает true. Теперь, если расстояние становится слишком маленьким, вы возвращаете false, вызывающий расширяет диапазон до x-2 .. x+2 и входит в опять подпрограмма.

Вам придется позаботиться о том, чтобы не задеть границы массива или даже не исчерпать пространство значений вообще.

2

Может быть несколько решений, вот одно из которых я бы предпочел

Я бы разделил эту проблему на несколько изолированных:

  1. в вашем бэкэнде java вы хотите иметь список элементов, отсортированных каким-либо образом, с возможностью делать быстрые O(1) изменения в порядке.

Лучшая структура-двойной связанный список. Вам нужно будет использовать hashmap, чтобы быстро найти объекты по имени элемента / id в этом списке.

Вы можете хранить такую структуру в базе данных легко, просто добавьте два иностранных ключи к таблице элементов. Во время хранения вам придется обновить только затронутые строки (имея в виду, что prev/next элементы также затрагиваются при перемещении элемента). Это будет выглядеть как несколько update table set prev=?, next=? where id=?

  1. в вашем java-сервисе вы хотите как можно быстрее отобразить отсортированный список элементов, возможно, разбитый на страницы.

Лучшая структура - предварительно отсортированный массив.

Для хранения такой структуры в базе данных вам понадобится столбец, в котором будет храниться позиция (ранг). Конечно вам нужен индекс по этому поводу колонка.

Для получения такой структуры вы будете использовать очень простой, быстрый и эффективный запрос, например select item from table order by rank limit ?,?.

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

  1. вы создадите отдельный асинхронный сервис (cron job), который будет считывать данные из одной таблицы, преобразовать (пересчитать ранг для всех элементов) и хранить в другой таблице.

Здесь у вас будет два варианта: либо полностью заменить данные во 2-й таблице после calculate, либо найти diff и обновить только измененные строки. Я считаю, что полная замена проще в реализации, и на самом деле это может быть гораздо быстрее.

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

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

2