IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Перестановка участков последовательности
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

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

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

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

Или же существует еще какое-то более интересное решение?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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

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


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


Цитата

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

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

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

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

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

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

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

Жаль, что правильность решения можно оценить только после удачной сдачи. sad.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

Как думаете, идея стоит выделки или лучше возиться с оптимизацией стартовой точки, от которой будут перебрасываться итераторы.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гость






Цитата
резко возрастет скорость переброски итераторов
За счет чего?
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

Потому и спрашиваю, что, возможно, существует более остроумное решение. sad.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

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

Сообщение отредактировано: passat -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Гость






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^ лежит результат всех этих действий...
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

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

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

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

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

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

Сообщение отредактировано: passat -
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Новичок
*

Группа: Пользователи
Сообщений: 32
Пол: Мужской

Репутация: -  0  +


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

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

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 26.11.2020 19:55
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name