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