Версия для печати темы

Нажмите сюда для просмотра этой темы в обычном формате

Форум «Всё о Паскале» _ Задачи _ Перестановка участков последовательности

Автор: passat 1.04.2009 20:02

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

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

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

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

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

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

Автор: volvo 1.04.2009 22:11

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

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

Автор: passat 3.04.2009 21:51

Цитата

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

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

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

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

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

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

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

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

Автор: passat 6.04.2009 17:03

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

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

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

Автор: volvo 6.04.2009 19:07

Цитата
резко возрастет скорость переброски итераторов
За счет чего?

Автор: passat 6.04.2009 20:41

Положим, что количество элементов 10000 и каждый вложенный список имеет 100 элементов. Тогда к последнему доберемся за 100+100 = 200 шагов., что в 50раз меньше. Естесственно, придется пожертвовать тем, что вместо одной перестановки участков придется выполнить, к примеру, три.

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

Потому и спрашиваю, что, возможно, существует более остроумное решение. sad.gif

Автор: passat 25.04.2009 18:56

На линейном списке превышен предел времени исполнения. Тратит приблизительно 4сек. Это с оптимизацией относительно начала/конца списка. Можно, конечно, попробовать оптимизацию относительно еще среднего итератора, но, боюсь, данные подобраны так, что не прокатит.
На вложенном списке без оптимизации положение улучшается только на некоторых тестах - реальный выигрыш во времени в 3-7раз. Но все равно пару тестов не проходят.

Чую, есть какая-то хитрая структура, позволяющая перебрасывать итераторы за логарифмическое время, но не знаю какая.

Помогите, пожалуйста. Нужно срочно.

Автор: volvo 26.04.2009 14:11

passat, а тебе что, обязательно какая-то

Цитата
хитрая структура
нужна? У тебя ограничения на используемую память есть? Компилятор какой? Вот тебе простейшее решение (тестировалось на FPC), 2 массива (обычных, статических массива, тест гонялся на размерах 100-200 тысяч + несколько сот тысяч перестановок) нужного размера + встроенный Move... Выигрыш относительно списков - более 2.5 раз (точнее - 2.62 .. 2.68, на разных значениях transform_count)

  for i := 1 to arrsize do begin
arr1[i] := i; arr2[i] := 0;
end;
_from := @arr1; _to := @arr2;

for i := 1 to transform_count do begin
// тут получаешь transform_start_pos, transform_finish_pos для итерации #I
_to^ := _from^;
pp := transform_finish_pos - transform_start_pos + 1;
move(_from^[transform_start_pos], _to^[1], pp*sizeof(longint));
move(_from^[1], _to^[pp+1], (transform_start_pos - 1)*sizeof(longint));

p := _from; _from := _to; _to := p;
end;
// в результате - в _from^ лежит результат всех этих действий...

Автор: passat 28.04.2009 14:23

Компилятор Delphi 7 или Free Pascal. Либо на C++ MS VisualStudio до 2005 включительно. Язык, вообще говоря, не принципиален.
Ограничений по памяти вроде нет.

А за счет чего получается выигрыш в сравнении со списком? Тут же мы имеем время n^2, правильно?

Оптимизированное даже по трем итераторам на линейном списке решение не проходит проверку на время. Вложенные списки дают выигрыш кое-где, но все тесты все равно не проходит smile.gif. Видать, тесты подобраны так, что вложенный список быстро вырождается в линейный и тогда получаем даже проигрыш.
Данные по времени выполнения сервер печатает странные: тесты с большим временем принимает, а с меньшим - нет. То ли сервер слишком умный, то ли я отсталый.

За подсказку спасибо. Реализацию уже почти добил, надо попробовать сдать. Но к сожалению что-то подсказывает, что этого может быть недостаточно.

А есть ли структура, которая работает за логарифмическое время? Хотя б ссылку на это чудо... А то горю sad.gif

Заранее спасибо.

ПС. А не получится ли в случае, если решение все же пройдет, зависимое от языка решение?

Автор: passat 29.04.2009 17:25

Не прошла задачка по времени. А жаль. sad.gif

Видимо, есть все же какая-то структура с логарифмическим временем доступа. Чисто теоретически это должно быть какое-то дерево, но непонятно какое. И как его строить. sad.gif