Xpoint
   [напомнить пароль]

Оптимальный способ приведения списка к заданному порядку элементов

Метки: [без меток]
2007-12-24 13:07:40 [обр] GRAy(0/259)[досье]

Предположим имеется некий список. Список этот подразумевает некоторую изначальную упорядоченность в соответствии с которой каждому из элементов присвоен порядковый номер. Есть так же единственно возможная операция над этим списком - поместить элемент X (всегда принадлежащий данному списку) в позицию Y (не "дальше" чем начало или конец). Изначально список формируется на "сервере" но потом отдаётся на "клиента" где пользователь может отсортировать его по своему усмотрению перемещая любые элементы "вниз" или "вверх". Перемещивание происходит пошагово т.е. элемент не смещается за один шаг более чем на одну позицию - но "сервер" об этих промежуточных перемещиниях ничего не знает. В итоге необходимо передать результат действий пользователя на "сервер" и тут встаёт вопрос - каким образом это сделать так, чтобы, в свою очередь, на сервере можно было бы минимизировать кол-во операций "вставить эл-т X в позицию Y" необходимых для приведения исходного списка к тому что натворил пользователь.
Пока что я придумал только передавать "смещение" позиции каждого элемента относительно предыдущего положения (отритцательные значения "вверх", положительные "вниз"). При этом получается, что если на "сервере" последовательно брать элементы с максимальным по модулю смещением, ставить их в нужную позицию и инкрементить/декрементить (зависит от знака смещения) смещение всех элементов между старой позицией переносимого элемента и его новой позицией, через некоторое кол-во итераций по списку я получу необходимый результат. Не уверен вот только что:

  1. это оптимально - может быть какая-то другая структура информации передаваемая от сервера клиенту позволит это сделать лучше.
  2. не изобретаю ли я велосипед ;)

Это конечно очень похоже на сортировку, но в моём случае именно ограничение на вид операции над списком на сервере и желательная минимизация их кол-ва не позволяет применить обычные алгоритмы сортировки - или я что-то не до конца понимаю?

спустя 33 минуты [обр] Thirteensmay(0/157)[досье]
А каково кол-во элементов ? ибо imho если меньше скажем 5000 то можно не парится, передавать весь список, как пары "было_id - стало_id"
спустя 22 минуты [обр] Thirteensmay(0/157)[досье]
Опять таки, если Список этот подразумевает некоторую изначальную упорядоченность т.е. если изначально элементы идут попорядку 1, 2, .. N то достаточно будет вернуть просто список "стало_id", соответственно кол-во элементов ну скажем 10000 передается без проблем. И к тому же чисто с точки зрения эргономики, большие списки - зло, надо разбивать, так что... ?
спустя 14 минут [обр] Евгений Петров(0/1055)[досье]
[<каждому из элементов присвоен порядковый номер>]
Хммм... А просто уменьшать/увеличивать этот номер и передать назад либо последовательность новых порядковых номеров (правда, придется передать все), либо массив пар [старый номер:новый номер] (только измененные) нельзя?
спустя 20 минут [обр] GRAy(0/259)[досье]
Thirteensmay[досье] Список сильно меньше 5000 ;) около 10 элементов. В моём случае надо оптимизировать не структуру передаваемой информации (т.е. не пытаться передать как можно меньше) а таким образом её организовать чтобы для приведения исходного списка к заданной пользователем сортировке потребовалось как можно меньше операций "поместить элемент X в позицию Y". Передав на сервер набор записей "было - стало" я просто добавлю ещё один этап обработки - вычесление смещений элементов.
Попробую описать конкретную ситуацию, так видимо будет понятней. Есть веб-сервис, который где-то внутри себя хранит список элементов и может выдать его по запросу. Так же у этого веб-сервиса есть метод "поместить элемент X в позицию Y" и работает он со смещением остальных элементов (т.е. как перекладывание карты в колоде с одного места на другое). Моя задача выдать пользователю в интерфейс этот список в начальном состоянии, и получив некое конечное "перемешанное" состояние (то в каком виде мне оно придёт я могу контролировать) минимальным количеством обращений к методу веб-сервиса привести его внутренний список к тому же порядку элементов.
спустя 38 минут [обр] Thirteensmay(0/157)[досье]
Опишите подробнее как работает метод "поместить элемент X в позицию Y". Создается впечатление что он у Вас чегото не доделывает ? оставляет пустышки, переписывает старые, несмещает хвосты и т.п. ? Иначе непонятно зачем инкрементить/декрементить (зависит от знака смещения) смещение всех остальных элементов ведь перекладывание карты в колоде с одного места на другое впринципе не противоречивый процесс и все автоматически "расширяется и схлопывается". Если же метод работает непротиворечиво, то получается что Вам просто надо сделать так чтобы интерфейс клиета работал также, и присылать на сервер только пары "было_id - стало_id".
спустя 7 часов [обр] Прокаев2(0/35)[досье]

То есть вопрос стоит о минимизации операций ?

Например, пользователь переставил 2 элемента
12345(4->2)
14235(4->2)
13425

Но программа должна выполнить только одну операцию
12345(2->4)
13425

спустя 11 часов [обр] GRAy(0/259)[досье]
Прокаев2[досье] Ага
спустя 5 часов [обр] Thirteensmay(0/157)[досье]

О как !
Ну ниче, можно попробовать забодать.

Для начала оптимизируем так чтобы
4 -> 2
4 -> 2
превращалось в 2 -> 4
Это не сложно.
Делаем 1 проход по исходному списку, на каждой итерации сравниваем пары
исходного
1, 2, 3, 4, 5
и конечного
1, 3, 4, 2, 5
списков, т.е. 1 - 1, 2 - 3, 3 - 4 и т.д.
Если i пара несовпадает, то элемент исходного списка с индексом равным значению i эл-та конечного списка, перемещается в i позицию. Т.е. мы уравниваем пару. Подразумеваю что сдвиги в исходном списке происходят автоматически. На следующей итерации конечный список сравниваем с уже преобразованным на предыдущей итерации исходным списком.
Таким образом мы решаем задачу оптимизации 4 -> 2 а не 2 -> 4.
Т.е. например
1, 2, 3, 4, 5 (при любом кол-ве перестановок)
преобразуется в
1, 4, 2, 3, 5
за одну перестановку 4 -> 2.
Назовем это восходящей стратегией оптимизации ;) мля..

Однако при попытке сделать так для 2 -> 4 получится фигня.
Тут нужен другой подход, нисходящий, реализуется он элементарно, но в свою очередь не совместим с первым.
Остановимся на первом, он хоть и не оптимален с точки зрения 2 -> 4, но по крайней мере считает правильно,
только вместо 2 -> 4 выдаст 3 -> 2, 4 -> 3.
Однако можно попробовать это компенсировать, и это самое интересное, не уверен, но можно предположить что
3 -> 2, 4 -> 3 эквивалентно 4 -> 2 при восходящем подходе, и 2 -> 4 при нисходящем.

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

Сразу очевидно, что если некий расчет нам дал
3 -> 1
5 -> 2
5 -> 3
5 -> 4
то цепочка 5 -> 3 -> 1 не может быть реализована, т.к. она разорвана 5 -> 2 т.е. операцией другого контекста,
следовательно, выделение схлопывание и инвертирование можно производить только для сплошных цепочек.

Ествественно, при реализации сего чуда перестановки сначало надо проводить на списке-эмуляторе,
записывать эти перестановки, потом пытатся оптимизировать нисходящие цепочки,
и только после этого выполнять результирующие перестановки в реальном объекте.

Если 3 -> 2, 4 -> 3 эквивалентно 4 -> 2 при восходящем подходе, и 2 -> 4 при... - неудачное предположение,
то при выделении нисходящих цепочек можно щитать кол-во звеньев, и если их больше чем прямых восходящих перестановок,
то можно принимать решение о том что основным подходом расчета надо принять нисходящий.

В результате имеем идеальную оптимизацию за один проход, не налагая ограничений на пользователя, вроде...
?

спустя 4 дня [обр] GRAy(0/259)[досье]
Thirteensmay[досье] С наступающим! ;)
Честно говоря нифига не понял из ваших поясний ;)
Будет больше времени - постараюсь разобраться.
Powered by POEM™ Engine Copyright © 2002-2005