Алгоритм на месте для проведения массива
https://cs.stackexchange.com/questions/332
-
16-10-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Вам дают массив из $ 2n $ Elements
$$ a_1, a_2, dots, a_n, b_1, b_2, dots b_n $$
Задача состоит в том, чтобы переоценить массив, используя алгоритм на месте, так что результирующий массив выглядит как
$$ b_1, a_1, b_2, a_2, dots, b_n, a_n $$
Если требование на месте не было, мы могли бы легко создать новый массив и копировать элементы, дающие алгоритм $ mathcal {o} (n) $.
С требованием на месте, алгоритм разделения и завоевания увеличивает алгоритм как $ theta (n log n) $.
Итак, вопрос:
Есть ли $ mathcal {o} (n) $ Algorithm, который также является на месте?
(Примечание: вы можете предположить модель RAM с равномерной стоимостью, поэтому на месте переводится на $ mathcal {o} (1) $ ограничение пространства).
Решение
Вот ответ, который подробно останавливается на алгоритме из бумаги, связанной Джо: http://arxiv.org/abs/0805.1598
Сначала давайте рассмотрим $ Theta (n log n) $ Алгоритм, который использует разделение и победит.
1) Разделите и победите
Нам дано
$$ a_1, a_2, dots, b_1, b_2, dots b_n $$
Теперь использовать разделение и завоевание, для некоторых $ m = theta (n) $, мы стараемся получить массив
$ $
и повторять.
Обратите внимание, что часть $$ b_1, b_2, dots b_m, a_ {m+1}, dots a_n $$ циклический сдвиг
$$ a_ {M+1}, dots a_n, b_1, dots b_m $$
по $ m $ места
Это классика и может быть сделана на месте три изменения и в $ mathcal {o} (n) $ время.
Таким образом, разделение и завоевание дают вам $ Theta (n log n) $ алгоритм с рекурсией, похожей на $ T (n) = 2t (n/2) + theta (n) $.
2) Циклы перестановки
Теперь еще один подход к проблеме - рассмотреть перестановку как набор непрерывных циклов.
Перестановка дается (при условии, что начинается с $1$)
$$ j mapsto 2j mod 2n+1 $$
Если бы мы как -то точно знали, что такое циклы, используя постоянное дополнительное пространство, мы могли бы понять перестановку, выбрав элемент $ A $, определить, куда идет этот элемент (используя вышеуказанную формулу), поместите элемент в целевое место во временном пространстве, поместите элемент $ A $ в этом целевом месте и продолжайте вдоль цикла. Как только мы закончим с одним циклом, мы перейдем к элементу следующего цикла и следуем за этим циклом и так далее.
Это дало бы нам $ mathcal {o} (n) $ Алгоритм времени, но он предполагает, что мы «каким-то образом знали, каковы были точные циклы» и пытаемся сделать это книжное ведение в рамках $ mathcal {o} (1) $ Ограничение пространства - это то, что затрудняет эту проблему.
Здесь в статье используется теория чисел.
Можно показать, что в случае, когда $ 2n + 1 = 3^k $, элементы на позициях $1$, $ 3, 3^2, dots, 3^{k-1} $ находятся в разных циклах, и каждый цикл содержит элемент в положении $ 3^m, m ge 0 $.
Это использует тот факт, что $2$ является генератором $ ( mathbb {z}/3^k)^*$.
Таким образом, когда $ 2n+1 = 3^k $, следующий за велосипедным подходом дает нам $ mathcal {o} (n) $ Алгоритм времени, как и для каждого цикла, мы точно знаем, с чего начать: силы $3$ (включая $1$) (они могут быть рассчитаны в $ mathcal {o} (1) $ пространство).
3) Окончательный алгоритм
Теперь мы объединяем два вышеуказанных: циклы разделителя и завоевания + перестановки.
Мы делаем разделение и побеждаем, но выбираем $ m $ чтобы 2 млн долларов+1 $ это сила $3$ а также $ m = theta (n) $.
Таким образом, вместо этого при повторении на обе «половинках» мы повторяем только один и делаем $ Theta (n) $ Дополнительная работа.
Это дает нам повторение $ T (n) = t (cn) + theta (n) $ (для некоторых $ 0 lt c lt 1 $) и, таким образом, дает нам $ mathcal {o} (n) $ время, $ mathcal {o} (1) $ Космический алгоритм!
Другие советы
Я почти уверен, что нашел алгоритм, который не полагается на теорию чисел или теорию цикла. Обратите внимание, что есть несколько деталей, которые нужно выработать (возможно, завтра), но я уверен, что они сработают. Я провожу руку, так как должен спать, а не потому, что пытаюсь скрыть проблемы :)
Позволять A быть первым массивом, B секунда, |A| = |B| = N и предположить N=2^k для некоторых k, для простоты. Позволять A[i..j] быть подражающим A с индексами i сквозь j, включительно. Массивы на 0 на основе 0. Позволять RightmostBitPos(i) вернуть (0 на основе) позицию самого правого бита, который является «1» i, считая справа. Алгоритм работает следующим образом.
GetIndex(i) {
int rightPos = RightmostBitPos(i) + 1;
return i >> rightPos;
}
Interleave(A, B, N) {
if (n == 1) {
swap(a[0], b[0]);
}
else {
for (i = 0; i < N; i++)
swap(A[i], B[GetIndex(i+1)]);
for (i = 1; i <= N/2; i*=2)
Interleave(B[0..i/2-1], B[i/2..i-1], i/2);
Interleave(B[0..N/2], B[N/2+1..N], n/2);
}
}
Давайте возьмем массив из 16 чисел, и давайте просто начнем интерлиацию их с помощью свопов, и посмотрим, что произойдет:
1 2 3 4 5 6 7 8 | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8 | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8 | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8 | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8 | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8 | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8 | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16
Особый интерес представляет первую часть второго массива:
|
| 1
| 2
| 2 3
| 4 3
| 4 3 5
| 4 6 5
| 4 6 5 7
| 8 6 5 7
Паттерн должен быть ясен: мы поочередно добавляем число к концу и заменяем самое низкое число на большое количество. Обратите внимание, что мы всегда добавляем число, которое на один выше, чем самое высокое число, которое у нас уже есть. Если бы мы каким -то образом смогли выяснить, какое число является самым низким в любой момент времени, мы можем сделать это легко.
Теперь мы идем к более широким примерам, чтобы увидеть, сможем ли мы увидеть шаблон. Обратите внимание, что нам не нужно исправлять размер массива, чтобы построить приведенный выше пример. В какой -то момент мы получаем эту конфигурацию (вторая строка вычитает 16 с каждого числа):
16 24 20 28 18 22 26 30 17 19 21 23 25 27 29 31
0 8 4 12 2 6 10 14 1 3 5 7 9 11 13 15
Теперь это ясно показывает шаблон: «1 3 5 7 9 11 13 15» - все это 2 друг от друга », 2 6 10 14» - все это на 4, а «4 12» - 8 - это 8 друг от друга. Поэтому мы можем разработать алгоритм, который рассказывает нам, каким будет следующее наименьшее число: механизм в значительной степени точно так же, как работают бинарные числа. У вас есть немного за последнюю половину массива, немного за вторую четверть и так далее.
Если нам поэтому нам разрешено достаточно места для хранения этих битов (нам нужны биты $ n $, но наша вычислительная модель позволяет это - указатель в массиве также нуждается Обращение в $ O (1) $ время амортизируется.
Поэтому мы можем получить первую половину массива в его чередованное состояние в $ O (n) $ Time и $ O (n) $ Shap. Тем не менее, мы должны исправить вторую половину нашего массива, которая, кажется, все испорчена («8 6 5 7 13 14 15 16»).
Теперь, если мы сможем «сортировать» первую половину этой второй части, мы получим «5 6 7 8 13 13 14 15 16», и рекурсивно проведите эту половину: мы перемещаем массив в $ O (n ) $ Time ($ O ( log n) $ Рекурсивные вызовы, каждый из которых вдвое сокращает размер входа). Примечание нам не нужен стек, так как эти вызовы являются хвостыми рекурсивными, поэтому наше пространство остается $ O (1) $.
Теперь вопрос в том, есть ли какой -то шаблон в той части, которую нам нужно сортировать? Попытка 32 числа дает нам "16 12 10 14 9 11 13 15", чтобы исправить. Обратите внимание, что у нас здесь такой же шаблон! «9 11 13 15», «10 14» и «12» сгруппированы так же, как мы видели ранее.
Теперь хитрость заключается в том, чтобы рекурсивно переплетать эти подразделы. Мы переплетаем «16» и «12» на «12 16». Мы переплетаем «12 16» и «10 14» на «10 12 14 16». Мы переплетаем «10 12 14 16» и «9 11 13 15» к «9 10 11 12 13 14 15 16 16». В этом роде первую часть.
Как и выше, общая стоимость этой операции составляет $ O (n) $. Добавляя все это, нам все еще удается получить общее время работы $ O (n) $.
Пример:
Interleave the first half:
1 2 3 4 5 6 7 8 | 9 10 11 12 13 14 15 16
9 2 3 4 5 6 7 8 | 1 10 11 12 13 14 15 16
9 1 3 4 5 6 7 8 | 2 10 11 12 13 14 15 16
9 1 10 4 5 6 7 8 | 2 3 11 12 13 14 15 16
9 1 10 2 5 6 7 8 | 4 3 11 12 13 14 15 16
9 1 10 2 11 6 7 8 | 4 3 5 12 13 14 15 16
9 1 10 2 11 3 7 8 | 4 6 5 12 13 14 15 16
9 1 10 2 11 3 12 8 | 4 6 5 7 13 14 15 16
9 1 10 2 11 3 12 4 | 8 6 5 7 13 14 15 16
Sort out the first part of the second array (recursion not explicit):
8 6 5 7 13 14 15 16
6 8 5 7 13 14 15 16
5 8 6 7 13 14 15 16
5 6 8 7 13 14 15 16
5 6 7 8 13 14 15 16
Interleave again:
5 6 7 8 | 13 14 15 16
13 6 7 8 | 5 14 15 16
13 5 7 8 | 6 14 15 16
13 5 14 8 | 6 7 15 16
13 5 14 6 | 8 7 15 16
Sort out the first part of the second array:
8 7 15 16
7 8 15 16
Interleave again:
7 8 | 15 16
15 8 | 7 16
15 7 | 8 16
Interleave again:
8 16
16 8
Merge all the above:
9 1 10 2 11 3 12 4 | 13 5 14 6 | 15 7 | 16 8
Вот не-рекурсивный алгоритм линейного времени на месте, чтобы переоценить две половинки массива без дополнительного хранения.
Общая идея проста: пройти через первую половину массива слева направо, обменивая правильные значения на место. Когда вы продвигаетесь, еще предстоит использовать левые значения, заменяющиеся в пространство, освобождаемое правыми значениями. Единственный трюк - выяснить, как их снова вытащить.
Мы начинаем с массива размера n разделенного на 2 почти равные половины.
[ left_items | right_items ]
Когда мы обрабатываем это, это становится
[ placed_items | remaining_left_items| swapped_left_items | remaining_right_items]
Пространство свопа растет со следующей схемой: а) выращивать пространство, удалив смежный правый элемент и заменив новый элемент слева; Б) поменяйте самый старый предмет новым предметом слева. Если левые элементы пронумерованы 1..n, этот шаблон выглядит как
step swapspace index changed
1 A: 1 0
2 B: 2 0
3 A: 2 3 1
4 B: 4 3 0
5 A: 4 3 5 2
6 B: 4 6 5 1
7 A: 4 6 5 7 3
...
Последовательность, из которой изменился индекс, точно OEI A025480, который можно рассчитать с помощью простого процесса. Это позволяет найти место обмена, учитывая только количество добавленных до сих пор элементов, что также является индексом текущего элемента, размещенного.
Это вся информация, которую нам нужно, чтобы заполнить 1 -ю половину последовательности в линейное время.
Когда мы доберемся до средней точки, у массива будет три части:[ placed_items | swapped_left_items | remaining_right_items]Если мы сможем разобраться в замене предметов, мы уменьшили проблему до половины размера и можем повторить.
Чтобы не разбрызгивать пространство свопа, мы используем следующее свойство: последовательность, построенная N Чередующиеся операции добавления и SWAP_OLDEST будут содержать N/2 Предметы, где их возраст дается A025480(N/2)..A025480(N-1). (Целостное разделение, меньшие значения старые).
Например, если левая половина первоначально удерживала значения 1..19, то пространство свопа будет содержать [16, 12, 10, 14, 18, 11, 13, 15, 17, 19]. Анкет A025480 (9..18) [2, 5, 1, 6, 3, 7, 0, 8, 4, 9], который является именно списком индексов элементов от самых старых к самым новым.
Таким образом, мы можем разобраться в нашем пространстве свопа, продвигаясь через него и обмениваясь S[i] с S[ A(N/2 + i)]. Анкет Это также линейное время.
Остальное осложнение заключается в том, что в конечном итоге вы достигнете позиции, где правильное значение должно быть в более низком индексе, но оно уже было заменено. Легко найти новое место: просто сделайте расчет индекса снова, чтобы обнаружить, куда был заменен элемент. Может быть необходимо следовать за цепью на несколько шагов, пока вы не найдете неослабное место.
На этом этапе мы объединили половину массива и сохранили порядок незаметных частей в другой половине, с точно N/2 + N/4 замены. Мы можем продолжить через остальную часть массива в общей сложности N + N/4 + N/8 + .... свопы, которые строго меньше, чем 3N/2.
Как рассчитать A025480:
Это определено в OEI как a(2n) = n, a(2n+1) = a(n). Альтернативная формулировкаa(n) = isEven(n)? n/2 : a((n-1)/2). Анкет Это приводит к простому алгоритму, использующему побитовой операции:
index_t a025480(index_t n){
while (n&1) n=n>>1;
return n>>1;
}
Это амортизированная операция O (1) по всем возможным значениям для N. (1/2 нужен 1 сдвиг, 1/4 необходимо 2, 1/8 необходимо 3, ...). Анкет Существует еще более быстрый метод, который использует небольшую таблицу поиска, чтобы найти положение наименее значительного нулевого бита.
Учитывая это, вот реализация в C:
static inline index_t larger_half(index_t sz) {return sz - (sz / 2); }
static inline bool is_even(index_t i) { return ((i & 1) ^ 1); }
index_t unshuffle_item(index_t j, index_t sz)
{
index_t i = j;
do {
i = a025480(sz / 2 + i);
}
while (i < j);
return i;
}
void interleave(value_t a[], index_t n_items)
{
index_t i = 0;
index_t midpt = larger_half(n_items);
while (i < n_items - 1) {
//for out-shuffle, the left item is at an even index
if (is_even(i)) { i++; }
index_t base = i;
//emplace left half.
for (; i < midpt; i++) {
index_t j = a025480(i - base);
SWAP(a + i, a + midpt + j);
}
//unscramble swapped items
index_t swap_ct = larger_half(i - base);
for (index_t j = 0; j + 1 < swap_ct ; j++) {
index_t k = unshuffle_item(j, i - base);
if (j != k) {
SWAP(a + midpt + j, a + midpt + k);
}
}
midpt += swap_ct;
}
}
Это должен быть довольно благоприятный для кеша алгоритм, поскольку доступ к 2 из 3 мест данных доступен последовательно, а объем обработанных данных строго уменьшается. Этот метод можно вывести из Внешний в связи с отрицанием is_even Проверьте в начале петли.
