Де-чередовать массив на месте?

Предположим, у меня есть массив чересстрочных данных, например 1a2b3c4d5e, и я хочу деинтерлейсировать его в массив, который выглядит как 12345abcde, на месте (без временного буфера). Каким будет самый быстрый способ сделать это?

Что я до сих пор это

template<typename T>
void deinterlace(T* arr, int length){
  if(length<=1) return;

  int i = 1;
  for(i = 1; i*2<length; i++){
    //swap i with i*2
    T temp = arr[i];
    arr[i] = arr[i*2];
    arr[i*2] = temp;
  }
  deinterlace(arr+i, length-i);
}

который, к сожалению, не работает с массивами, не имеющими мощности 2 по размеру

отредактируйте: этот алгоритм терпит неудачу при больших мощностях 2 в любом случае, поэтому я думаю, что снова на квадрате 0

edit 2: для этого я нашел алгоритм nlogn, заданный либо функцией поворота массива O (n), либо начальным размером, равным 2

работает так:

1a2b3c4d5e6f7g, "размер блока" = 1 начальный,

расщепляется на группы размером куска * 4 1a2b 3c4d 5e6f 7g

поменять внутренние 2 куска каждой группы 12ab 34cd 56ef 7g

повторить с размером блока = размер блока * 2

12ab34cd 56ef7g (читай: 56 ef 7 г) → 1234abcd 567efg

1234abcd567efg → 1234567abcdefg

template<typename T>
void deinterlace(T* arr, int length, int group_ct = 1){
  if(group_ct*2 >= length) return;

  for(int i = 0; i<length; i+=group_ct*4){
    int rot_count = group_ct;

    int i1 = i + group_ct;
    int i2 = i+group_ct*4 - group_ct;

    if(i2+group_ct > length){
      i2 = i1 + (length-i1)/2+group_ct/2;
    }

    rotate(arr, i1, i2, group_ct);

  }

  deinterlace(arr, length, group_ct * 2);
}

edit 3 Я думаю, что правильный термин является обратным, а не деинтерлейсом

Ответ 1

Это по существу проблема переноса матрицы. Ваш массив

[1 a]
[2 b]
[3 c]
[4 d]

эквивалентно 1, a, 2, b, 3, c, 4, d, если он представлен как вектор (сначала читая строки). Транспонирование этой матрицы:

[1 2 3 4]
[a b c d]

что эквивалентно 1, 2, 3, 4, a, b, c, d.

Существует страница wikipedia, в которой рассматривается перенос матрицы на месте для общих случаев. Я думаю, что алгоритм для не квадратной матрицы был бы непосредственно применим.

Существует медленный (не уверенный, если O (n ^ 2) или хуже, и это будет поздно) алгоритм, который вы можете использовать. Идея состоит в том, чтобы поместить подматрицу из положения i в положение 2*i. Например:

START: 1a2b3c4d5e6f
1(a2)...         -> 1(2a)...
12(ab3)...       -> 12(3ab)...
123(abc4)...     -> 123(4abc)...
1234(abcd5)...   -> 1234(5abcd)...
12345(abcde6)... -> 12345(6abcde)..
123456(abcdef)   -> DONE

Первым элементом массива является индекс 0. На шаге 1 вы выбираете суб-массив a[1:2] и поворачиваете его вправо (все участники переходят в следующее место, а последний запускается). На следующем шаге вы выбираете a[2:4] и вращаете его и т.д. Убедитесь, что вы не поменяли последний под-массив a[n/2:n].

И последний вариант, если вам не нужно выполнять массовые операции для производительности (например, memcpy), заключается в предоставлении функции доступа и преобразовании индекса вместо перемещения любых байтов. Такая функция почти тривиальна для записи: если индекс меньше max/2, верните запись в 2*index, в противном случае верните запись в 2*(index-max/2)+1.

Ответ 2

Ваша оригинальная идея почти сработает для деинтерлейсинга на месте. Вам просто нужно учитывать тот факт, что когда вы меняете элемент на место, вы перемещаете элемент, который формула ожидает найти там.

Итак, во-первых, определите функцию source_index: учитывая идеально чередующийся массив длины N и индекс i, верните элемент, который должен быть в i. Первая половина - из каждого другого четного элемента, последняя половина - из любого другого нечетного.

int source_index(int i, int length) {
  int mid = length-length/2;

  if (i<mid) {
    return i*2;
  }
  return (i-mid)*2+1;
}

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

template<typename T>
void deinterlace(T* arr, int length){
  if(length<=1) return;

  int i = 1;
  for(i = 1; i<length; i++){
    int j = source_index(i, length);
    while (j<i) { //walk the chain of swaps
      j = source_index(j, length);
    }
    T temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

Это делает ровно N обменов. Количество вызовов на source_index несколько хаотично, но, похоже, демонстрирует рост NlgN.

Ответ 3

Если вы не заботитесь о порядке результирующего массива, самым быстрым способом, о котором я могу думать, является выполнение последовательных свопов с использованием индекса "head" и "tail".

int head = 1;
int tail = length - 2;
while (head < tail)
{
    T temp = arr[head];
    temp = arr[head];
    arr[head] = arr[tail];
    arr[tail] = temp;
    head += 2;
    tail -= 2;
}

Для вашего примера, результатом будет 15243cbdae после 2 итераций.