Перестановка участков последовательности Опции

[passat]

Помогите еще с одной задачкой.
Имеется последовательность натуральных чисел.
Необходимо выполнить N перестановок участков последовательности, где участок задается его началом и концом. Перестановка выполняется в начало последовательности.

Т.е. для последовательности из 6 чисел ип трех перестановках
2 4
2 4
4 4

результат должен быть 2 3 4 1 5 6 .

Количество чисел и перестановок может быть несколько сот тысяч.

Первая идея: список. В связи с чем вопрос: можно ли как-то оптимизировать порядок выполнения перестановок? Либо хотя бы порядок переброски итераторов?

Или же существует еще какое-то более интересное решение?

[volvo]

Чтоб можно было оптимизировать, надо знать, что для тебя - НЕоптимизированный вариант. Кстати. Зачем это оптимизировать? Ты не привел никаких временнЫх ограничений, и ограничений по памяти тоже не привел, кстати...

Без оптимизации: однонаправленный список + последовательный поиск элемента с нужным номером + перестановка 4-х указателей при перемещении блока в начало списка. На 100 тысячах элементов и 25 тысячах перестановок отрабатывает за 1.5 секунды. Двунаправленный список будет пожирать больше памяти, но может сэкономить время на нахождение элементов списка, расположенных ближе к его концу, чем к началу...

[passat]

Чтоб можно было оптимизировать, надо знать, что для тебя - НЕоптимизированный вариант.

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

Смущает простота лобового решения задачи.

Кстати. Зачем это оптимизировать? Ты не привел никаких временнЫх ограничений, и ограничений по памяти тоже не привел, кстати...

Если б я их знал, то, очевидно привел бы.

Без оптимизации: однонаправленный список + последовательный поиск элемента с нужным номером + перестановка 4-х указателей при перемещении блока в начало списка. На 100 тысячах элементов и 25 тысячах перестановок отрабатывает за 1.5 секунды. Двунаправленный список будет пожирать больше памяти, но может сэкономить время на нахождение элементов списка, расположенных ближе к его концу, чем к началу...

Радует, по крайней мере, что направление мысли было правильным. ??? Т.е. из двунаправленного списка я и исходил. Плюс примитивная оптимизация по месторасположению участка (конец-начало списка). Наверное, возможен анализ по сопоставлению участка с промежуточным итератором...

Жаль, что правильность решения можно оценить только после удачной сдачи.

[passat]

Как и опасался, по состоянию на данный момент для 100тыс элементов и перестановок нарушен предел времени выполнения.

Идея. Для длинных списков сделать элементы списка списками. В этом случае по идее необходимо будет выполнять больше операций перестановок участков, но зато резко возрастет скорость переброски итераторов.

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