如何原地对数组进行去交错操作？

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的幂次方时，此算法都会失败，所以我又回到了起点。

编辑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）

- TylerGlaiel

---

通常情况下，这是一个不容易在原地完成的任务。在DSP算法中非常常见，已经有相当多的研究关于如何高效地完成此任务。也许这种情况有一个简单且高效的解决方案，我会等待有人来否定我的看法。 - Mysticial

是的，这是用于音频引擎的。我想我可以将初始数组填充到2的幂，但那样我会浪费空间，还不如使用临时变量。 - TylerGlaiel

@GlaielGamer 对于大小为60或4000的块，填充到最近的幂可能比加倍数组要小得多。 - ssube

你知道数组的大小吗？它是恒定的还是只有少量常数？ - TonyK

是的，我是指反交错，我的错误。 - TylerGlaiel

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），则最终的选项是提供访问器函数，并转换索引，而不是移动任何字节。这样的函数几乎可以轻松编写：如果索引小于max/2，则返回2*index处的条目，否则返回2*(index-max/2)+1处的条目。

- vhallac

---

好的，谢谢。这正是我需要的。虽然不完全是我所需要的，但知道它不能在没有临时存储的情况下完成，也是一个令人满意的答案。 - TylerGlaiel

关于你的编辑：是的，n^2对于几兆大小的数组来说太慢了。 - TylerGlaiel

@GlaielGamer 那是我目前能想到的最好的答案。如果我能想到更好的，我会更新答案。 - vhallac

是的，这仍然是一个有趣的问题，但我已经找到了一个解决方法，可以满足我的需求。 - TylerGlaiel

Answer 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 的增长。

- AShelly

---

这太棒了！可以进行的一个优化是使用单个位移一次性完成所有乘以2的操作：https://wandbox.org/permlink/3qEUWMOAbBW5T6gQ 此外，从绘图中可以看出，所需时间介于O(n^1.118)和O(n^1.13)之间，因此比O(n lg n)更差。然而，对于解交错1GiB字符，计算索引需要约10亿次操作，并且少于1毫秒即可完成（大部分时间用于交换），因此对于合理数量的数据（<1TiB），这基本上是O(n)。 - Artyer

很高兴能够帮到你。如果你有兴趣反过来做，我在这里描述了一个相关的算法（https://cs.stackexchange.com/q/105604/58310）。顺便说一下，你的链接好像有问题。 - AShelly

这里有一个不同的链接，应该可以使用：https://godbolt.org/z/Pjrn6YGsx。将循环次数与x的对数比例绘制成图表并不显示一条直线，但在对数-对数比例上它似乎是线性的，这意味着它是指数级的。 - Artyer

Answer 3

如果您不关心结果数组的顺序，我能想到的最快方法是使用“头”和“尾”索引进行连续交换。

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;
}

对于您的示例情况，经过2次迭代后，结果将为15243cbdae。

- bobbymcr

---

然后将两半部分作为第二步进行排序。 - Mooing Duck

它们应该不被排序，只保持与原始数组相同的顺序，例如，如果数组是KZUHYDIA，则结果应为KUYIZHDA。 - TylerGlaiel