Помогите еще с одной задачкой.
Имеется последовательность натуральных чисел.
Необходимо выполнить N перестановок участков последовательности, где участок задается его началом и концом. Перестановка выполняется в начало последовательности.
Т.е. для последовательности из 6 чисел ип трех перестановках
2 4
2 4
4 4
результат должен быть 2 3 4 1 5 6 .
Количество чисел и перестановок может быть несколько сот тысяч.
Первая идея: список. В связи с чем вопрос: можно ли как-то оптимизировать порядок выполнения перестановок? Либо хотя бы порядок переброски итераторов?
Или же существует еще какое-то более интересное решение?
Чтоб можно было оптимизировать, надо знать, что для тебя - НЕоптимизированный вариант. Кстати. Зачем это оптимизировать? Ты не привел никаких временнЫх ограничений, и ограничений по памяти тоже не привел, кстати...
Без оптимизации: однонаправленный список + последовательный поиск элемента с нужным номером + перестановка 4-х указателей при перемещении блока в начало списка. На 100 тысячах элементов и 25 тысячах перестановок отрабатывает за 1.5 секунды. Двунаправленный список будет пожирать больше памяти, но может сэкономить время на нахождение элементов списка, расположенных ближе к его концу, чем к началу...
Как и опасался, по состоянию на данный момент для 100тыс элементов и перестановок нарушен предел времени выполнения.
Идея. Для длинных списков сделать элементы списка списками. В этом случае по идее необходимо будет выполнять больше операций перестановок участков, но зато резко возрастет скорость переброски итераторов.
Как думаете, идея стоит выделки или лучше возиться с оптимизацией стартовой точки, от которой будут перебрасываться итераторы.
Положим, что количество элементов 10000 и каждый вложенный список имеет 100 элементов. Тогда к последнему доберемся за 100+100 = 200 шагов., что в 50раз меньше. Естесственно, придется пожертвовать тем, что вместо одной перестановки участков придется выполнить, к примеру, три.
Конечно, к концу перестановок наверняка вложенный список выродится в линейный, но... других решений, кроме введения в рассмотрение еще и внутреннего итератора и анализа положения начала и конца участка относительно этих трех итераторов (долго и скучно), пока не вижу .
Потому и спрашиваю, что, возможно, существует более остроумное решение.
На линейном списке превышен предел времени исполнения. Тратит приблизительно 4сек. Это с оптимизацией относительно начала/конца списка. Можно, конечно, попробовать оптимизацию относительно еще среднего итератора, но, боюсь, данные подобраны так, что не прокатит.
На вложенном списке без оптимизации положение улучшается только на некоторых тестах - реальный выигрыш во времени в 3-7раз. Но все равно пару тестов не проходят.
Чую, есть какая-то хитрая структура, позволяющая перебрасывать итераторы за логарифмическое время, но не знаю какая.
Помогите, пожалуйста. Нужно срочно.
passat, а тебе что, обязательно какая-то
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^ лежит результат всех этих действий...
Компилятор Delphi 7 или Free Pascal. Либо на C++ MS VisualStudio до 2005 включительно. Язык, вообще говоря, не принципиален.
Ограничений по памяти вроде нет.
А за счет чего получается выигрыш в сравнении со списком? Тут же мы имеем время n^2, правильно?
Оптимизированное даже по трем итераторам на линейном списке решение не проходит проверку на время. Вложенные списки дают выигрыш кое-где, но все тесты все равно не проходит . Видать, тесты подобраны так, что вложенный список быстро вырождается в линейный и тогда получаем даже проигрыш.
Данные по времени выполнения сервер печатает странные: тесты с большим временем принимает, а с меньшим - нет. То ли сервер слишком умный, то ли я отсталый.
За подсказку спасибо. Реализацию уже почти добил, надо попробовать сдать. Но к сожалению что-то подсказывает, что этого может быть недостаточно.
А есть ли структура, которая работает за логарифмическое время? Хотя б ссылку на это чудо... А то горю
Заранее спасибо.
ПС. А не получится ли в случае, если решение все же пройдет, зависимое от языка решение?
Не прошла задачка по времени. А жаль.
Видимо, есть все же какая-то структура с логарифмическим временем доступа. Чисто теоретически это должно быть какое-то дерево, но непонятно какое. И как его строить.