Вопрос по algorithm, sorting, performance – Существует ли специализированный алгоритм, более быстрый, чем быстрая сортировка, для изменения порядка данных ACEGBDFH?

5

У меня есть некоторые данные, поступающие от оборудования. Данные поступают в блоки по 32 байта, и потенциально есть миллионы блоков. Блоки данных разбиты на две половины следующим образом (буква - один блок):

<code>A C E G I K M O B D F H J L N P
</code>

или если пронумерованы

<code>0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15
</code>

Сначала все блоки с четными индексами, затем нечетные блоки. Существует ли специальный алгоритм для правильного переупорядочения данных (в алфавитном порядке)?

Ограничения в основном на пространстве. Я не хочу выделять другой буфер для переупорядочения: просто еще один блок. Но я также хотел бы сохранить количество ходов на низком уровне: простая быстрая сортировка была бы O (NlogN). Есть ли более быстрое решение в O (N) для этого особого случая переупорядочения?

Сортировка не может быть выполнена в сложности O (n). Shiplu Mokaddim
Ладно, у меня, похоже, есть часть «миллионов блоков», предполагающая, что здесь есть что-то большее, чем я предполагал в своем ответе. Для уточнения: если бы было 16 блоков вместо 16, куда бы пошли дополнительные два блока? Возможно ли в вашем случае 18 блоков, или это будет запрещено? Как я понимаю это сейчас после перечитывания, это то, что вы получаете по шаблону:Odd numbered block even numbered blocks а не фиксированный шаблон из 16 блоковA C E G I K M O B D F H J L N P, возможно, повторяется, как я и предполагал. Это верно LiKao
@ shiplu.mokadd.im: В общем случае это правда, но эти данные уже частично отсортированы amit
Вам действительно нужно объяснить, как ваши данные частично сортируются. Это просто разделено на две отсортированные половины? Или две половинки всегда содержат нечетные / четные элементы соответственно? interjay
Когда вы говорите «всегда следующим образом», вы имеете в виду, что порядок всегда такой, как задано - первый блок первый, второй девятый, третья секунда и т. д.? если так, то, конечно, вы можете просто написать код, чтобы переставить их явно? andrew cooke

Ваш Ответ

6   ответов
7

сортировка в классическом смысле не нужна вообще. Вам не нужно никаких сравнений, так как вы уже знаете заранее, какой из двух заданных точек данных.

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

Вот пример ваших данных:

0 2 4 6 8 10 12 14 1 3  5  7  9 11 13 15
0 1 2 3 4 5  6  7  8 9 10 11 12 13 14 15

Теперь вычислим обратное (я пропущу этот шаг, потому что мне здесь лень, предположим, что приведенная выше перестановка на самом деле уже обратная).

Вот циклическая форма:

(0)(1 8 4 2)(3 9 12 6)(5 10)(7 11 13 14)(15)

Так что если вы хотите изменить порядок последовательности, как это, вы должны сделать

# first cycle
# nothing to do

# second cycle
swap 1 8
swap 8 4
swap 4 2

# third cycle
swap 3 9
swap 9 12
swap 12 6

# so on for the other cycles

Если бы вы сделали это для инверсии вместо исходной перестановки, вы бы получили правильную последовательность с проверенным минимальным числом перестановок.

РЕДАКТИРОВАТ:

Подробнее об этом см., Например, главу о перестановках в TAOCP.

Но какой смысл в том, что вычисление циклической формы перестановки равно O (N ^ 2)? Или я не знаком с алгоритмом O (N)? -1 пока не уточнишь. : D Можете ли вы как-то сгенерировать его в O (N) для произвольного N для конкретной формы, которую имеют его данные? svinja
@ svinja как пишет ОП, данные поступают вalways так, как он описал. Предварительный расчет для произвольного N не требовался и не требовался. Gunther Piez
Тогда как я могу вычислить перестановку для любого количества блоков N (четное N) без использования большого количества памяти? Didier Trosset
@ svinja Хорошо, забудь об этом :-) Глупый я. Как я мог понятьalways в вопросе, как будто это означало какalways ... Gunther Piez
Он приходит в такой форме (упорядоченные коэффициенты, затем упорядоченные четные), но он может быть длиной в миллионы блоков, а не только в 16. По крайней мере, я так понимаю, иначе «миллионы блоков» не имеют смысла. svinja
0

использование битов адреса `abcd <-> dabc '(с abcd отдельных битов индекса) Как:

#include <stdio.h>

#define ROTATE(v,n,i) (((v)>>(i)) | (((v) & ((1u <<(i))-1)) << ((n)-(i))))

/******************************************************/
int main (int argc, char **argv)
{
unsigned i,a,b;

for (i=0; i < 16; i++) {
        a = ROTATE(i,4,1);
        b = ROTATE(a,4,3);

        fprintf(stdout,"i=%u a=%u b=%u\n", i, a, b);
        }

return 0;
}

/******************************************************/
3

a0 a2 a4 ... A 14 a1 a3 a5 ... A 15

и вы хотите, чтобы это отсортировано по

b0 b1 b2 ... б 15

При некотором переупорядочении перестановка может быть записана так:

a0 -> b0

a8 -> b1
a1 -> b2
a2 -> b4
a4 -> b8

a9 -> b3
a3 -> b6
a6 -> b 12
a 12 -> b9

a 10 -> b5
a5 -> b 10

a 11 -> b7
a7 -> b 14
a 14 -> b 13
a 13 -> b 11

a 15 -> b 15

Так что, если вы хотите отсортировать на месте только с одним дополнительным пробелом блока во временномt, это можно сделать в O (1) с помощью

t = a8;   a8 = a4;  a4 = a2;  a2 = a1;  a1 = t

t = a9;   a9 = a12; a12= a6;  a6 = a3;  a9 = t

t = a10; a10 = a5;  a5 = t

t = a11; a11 = a13; a13 = a14; a14 = a7; a7 = t

Редактировать
Общий случай (для N! = 16), если он разрешим в O (N), на самом деле является интересным вопросом. Я подозреваю, что циклы всегда начинаются с простого числа, которое удовлетворяетp < N/2 && N mod p != 0 и индексы повторяются как я П + 1 = 2in мод N, но я не могу доказать это. Если это так, вывод алгоритма O (N) тривиален.

@ drhirsh: Ладно, по-вашему, вы можете получить свопы напрямую, не рассчитывая сначала обратное значение. И вам не нужно большое количество временных, как я, путем обмена в противоположном направлении. Думаю, в следующий раз мне понадобится еще немного времени, чтобы усовершенствовать свои первые идеи. +1 за это хорошее уточнение. LiKao
Спасибо, это еще один способ написать ответ ЛиКао. Теперь, как я могу сделать это для любого количества блоков N (N четное)? Didier Trosset
1

Тождественны к указанному, то вы можете «заранее запрограммировать» (т.е. избежать всех сравнений) оптимальное решение (которое будет иметь минимальное число перестановок для перехода от строки, заданной к ABCDEFGHIJKLMNOP и которое для чего-то Этот маленький, вы можете работать вручную - см. ответ ЛиКао).

Я не вижу, как здесь появляется расстояние редактирования. Расстояние редактирования обычно относится к типу изменений удаления / вставки / замены из одной последовательности в другую, а не к перестановкам. Если вам нужна перестановка, это то, что вы должны использовать. LiKao
о, извини, хотя я включал в себя замену символов. будет обновлять. andrew cooke
По крайней мере, стандартное расстояние редактирования не включает свопы. Может быть, есть специализированная версия. Если вы можете найти его, мне бы очень хотелось внести изменения в алгоритм, чтобы он учитывал обмены. LiKao
0

0 2 4 6 8 10 12 14 1 3 5 7 9 11 13 15

Начните с 14 и переместите все четные числа на место (8 перестановок). Вы получите это:

0 1 2 9 4 6 13 8 3 10 7 12 11 14 15

Теперь вам нужно еще 3 свопа (9 с 3, 7 с 13, 11 с 13 с 7).

Всего 11 свопов. Не общее решение, но оно может дать вам несколько советов.

-2

Похожие вопросы