Solution of segment swap task. Detail info in readme.
Даны фиксированные целые числа 0<m<n<p и часть массива b[m: p-1], рассматриваемая как два сегмента:
b[m: n-1] длиной i и b[n: p-1] длиной j.
Поменять местами два сегмента, используя лишь постоянный (не зависящий от m, n, и p)
объём дополнительной памяти (не сдвигая элементы, только путём обмена!). Нужно получить: b [n: p-1] b [m: n-1]
Пример: "abcde fgh", i=5, j=3 => "fgh abcde"
Подается строка переменной длинны, индекс конца первого сегмента.
Этих данных достаточно для выполнения задачи тк остальные можно получить на их базе.
Передаваемая строка должна быть длиной > 2.
Индекс сегмента должен не превышать длины строки.
Строка, длинной равной исходной и с переставленными по условию сегментами.
Строку, разбитую на 2 подстроки переменной длины нужно преобразовать так,
чтобы первый сегмент стал вторым, а второй первым.\
Для начала рассмотрим наивную реализацию алгоритма решения.
Само решение интуитивно понятно и заключается в последовательном сдвиге всех элементов строки.
Рассмотрим на примере:
"abcde fgh", i=5, j=3
1: "bcdefgha"
2: "cdefghab"
3: "defghabc"
4: "efghabcd"
5: "fghabcde"
После этого получим решение.
Проблема данного метода в том, что приходится
делать много обменов в рамках каждой итерации алгоритма.
А именно, каждый раз нам придется делать кол-во обменов, равное длине строки.
Количество сдвигов будет равно длине первого сегмента.
Следовательно, сложность примерно равна O(p*m)
Второй вариант решения более хитрый.
Если в алгоритме №1 мы основывали решение на так называемом сдвиге строки,
то в данном решении основопологающей будет процедура переворота подстроки.
То есть операция вида "abc" => "cba"
Заметим, что после отражения строки "abcde fgh" => "hgfedcba"
строка будет отличаться от желаемой порядком букв в обоих сегментах.
Это означает, что если мы применим операцию переворота для обоих сегментов,
то получим искомый ответ.
Рассмотрим на примере:
"abcde fgh", i=5, j=3
1: "hgfedcba"
2: "fghabcde"
После этого получим решение.
Данное решение является более оптимальным. Тк процедура разворота строки
содержит в себе кол-во обменов равное длине строки деленной на 2.
Кол-во разворотов в любом случае будет равняться 3.
Первый разворот займет p/2 обменов.
Второй разворот займет i/2 обменов.
Третий разворот займет j/2 обменов.
Получим, что данный алгоритм должен работать быстрее, чем первый
Для того чтобы проверить правильность наших суждений реализуем алгоритмы, и проведем замеры.
input: abcdefgh 5
Reverse segment swap: 3852400 4802300 25672600
Simple segment swap: 481500 534600 408400
input: abcdefgh 3
Reverse segment swap: 353800 427300 427200
Simple segment swap: 686000 385300 311400
input: defghabcdefghabc 3
Reverse segment swap: 572000 393200 495100
Simple segment swap: 361400 307600 384900
input: defghabcdefghabc 13
Reverse segment swap: 4091000 403800 3401200
Simple segment swap: 820700 873900 307900
input: abcdefghabcdefghabcdefgh 8
Reverse segment swap: 288700 3808200 1621800
Simple segment swap: 391000 448000 803700
input: abcdefghabcdefghabcdefgh 20
Reverse segment swap: 249900 897100 3266300
Simple segment swap: 519300 334500 280800
Следующие испытания были проведены подряд с небольшим
перерывом при средней нагрузке компьютера.
Результаты могут отличаться в связи с системной нагрузкой.
Также, проводились тесты в которых был изменен порядок вызова функций,
результаты особо не отличаются.
Вдобавок, сложность данных алгоритмов может заметно различаться от реализации.