Перестановка участков последовательности |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Перестановка участков последовательности |
passat |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
Помогите еще с одной задачкой.
Имеется последовательность натуральных чисел. Необходимо выполнить N перестановок участков последовательности, где участок задается его началом и концом. Перестановка выполняется в начало последовательности. Т.е. для последовательности из 6 чисел ип трех перестановках 2 4 2 4 4 4 результат должен быть 2 3 4 1 5 6 . Количество чисел и перестановок может быть несколько сот тысяч. Первая идея: список. В связи с чем вопрос: можно ли как-то оптимизировать порядок выполнения перестановок? Либо хотя бы порядок переброски итераторов? Или же существует еще какое-то более интересное решение? |
volvo |
Сообщение
#2
|
Гость |
Цитата резко возрастет скорость переброски итераторов За счет чего? |
passat |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
Положим, что количество элементов 10000 и каждый вложенный список имеет 100 элементов. Тогда к последнему доберемся за 100+100 = 200 шагов., что в 50раз меньше. Естесственно, придется пожертвовать тем, что вместо одной перестановки участков придется выполнить, к примеру, три.
Конечно, к концу перестановок наверняка вложенный список выродится в линейный, но... других решений, кроме введения в рассмотрение еще и внутреннего итератора и анализа положения начала и конца участка относительно этих трех итераторов (долго и скучно), пока не вижу . Потому и спрашиваю, что, возможно, существует более остроумное решение. |
passat |
Сообщение
#4
|
Новичок Группа: Пользователи Сообщений: 32 Пол: Мужской Репутация: 0 |
На линейном списке превышен предел времени исполнения. Тратит приблизительно 4сек. Это с оптимизацией относительно начала/конца списка. Можно, конечно, попробовать оптимизацию относительно еще среднего итератора, но, боюсь, данные подобраны так, что не прокатит.
На вложенном списке без оптимизации положение улучшается только на некоторых тестах - реальный выигрыш во времени в 3-7раз. Но все равно пару тестов не проходят. Чую, есть какая-то хитрая структура, позволяющая перебрасывать итераторы за логарифмическое время, но не знаю какая. Помогите, пожалуйста. Нужно срочно. Сообщение отредактировано: passat - |
Текстовая версия | 29.04.2024 9:23 |