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

[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тыс элементов и перестановок нарушен предел времени выполнения.

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

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

[volvo]

резко возрастет скорость переброски итераторов

За счет чего?

[passat]

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

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

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

[passat]

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

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

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

Сообщение отредактировано: passat - 25.04.2009 14:57

[volvo]

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]

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

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

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

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

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

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

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

Сообщение отредактировано: passat - 28.04.2009 12:52

[passat]

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

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