将数组解交错？

Question

假设我有一个隔行扫描数据数组,例如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

编辑2:我找到了一个nlogn算法,给定一个O(n)数组旋转函数,或者初始大小是2的幂

像这样工作:

1a2b3c4d5e6f7g,"块大小"= 1初始,

分成大块的组*4 1a2b 3c4d 5e6f 7g

交换每组的内部2块12ab 34cd 56ef 7g

重复块大小=块大小*2

12ab34cd 56ef7g(读数:56 ef 7 g) - > 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);
}

编辑3我猜正确的术语是deinterleave,而不是deinterlace

Answer 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.

有一个维基百科页面,处理一般情况下的就地矩阵转置.我想,非方矩阵的算法可以直接应用.

你可以使用慢速(不确定是否为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)进行批量操作,则提供一个访问器函数,并转换索引而不是移动任何字节.写这样的函数几乎是微不足道的:如果index小于max/2,则返回entry 2*index,否则返回entry 2*(index-max/2)+1.