sorting - 修改少量元素后对向量重新排序

Question

如果我们有一个之前已排序的大小为 N 的向量，并用任意值替换最多 M 个元素(其中 M 是远小于N)，是否有一种简单的方法可以比完全排序以更低的成本(即生成深度减小的排序网络)对它们进行重新排序？

例如，如果N=10且M=2，则输入可能是

10 20 30 40 999 60 70 80 90 -1

注意:修改元素的索引是未知的(直到我们将它们与周围的元素进行比较。)

<小时/>

这是一个我知道解决方案的示例，因为输入大小很小，我能够通过强力搜索找到它:

如果 N = 5 并且 M 为 1，则这些将是有效输入:

0 0 0 0 0     0 0 1 0 0     0 1 0 0 0     0 1 1 1 0     1 0 0 1 1     1 1 1 1 0

0 0 0 0 1     0 0 1 0 1     0 1 0 0 1     0 1 1 1 1     1 0 1 1 1     1 1 1 1 1

0 0 0 1 0     0 0 1 1 0     0 1 0 1 1     1 0 0 0 0     1 1 0 1 1

0 0 0 1 1     0 0 1 1 1     0 1 1 0 1     1 0 0 0 1     1 1 1 0 1

例如，如果先前排序的向量为 0 1 1 1 1 并且第 4 个元素被修改，则输入可能为 0 1 1 0 1，但没有形成 0 1 0 1 0 作为有效输入的方法，因为它与任何排序向量至少有 2 个元素不同。

这将是一个有效的排序网络，用于重新排序这些输入:

>--*---*-----*-------->
   |   |     | 
>--*---|-----|-*---*-->
       |     | |   |
>--*---|-*---*-|---*-->
   |   | |     |
>--*---*-|-----*---*-->
         |         |
>--------*---------*-->

我们不关心该网络无法对某些无效输入进行排序(例如0 1 0 1 0。)

这个网络的深度为 4，与一般情况相比节省了 1 ( a depth of 5 generally necessary to sort a 5-element vector 。)

不幸的是，对于较大的输入大小，暴力方法不可行。

是否有已知的方法来构建网络以对更大的向量进行重新排序？

我的 N 值约为几百，M 不会比 √N 多多少。

Answer 1

好吧，我将其作为答案发布，因为评论长度的限制让我发疯:)

你应该尝试一下:

• 在本地内存上实现简单的顺序排序(插入排序或类似的排序)。如果您不知道如何操作 - 我可以提供帮助。
• 只有一个工作项对 N 个元素的 block 执行排序
• 计算每个工作组的本地内存最大大小(使用CL_DEVICE_LOCAL_MEM_SIZE调用clGetDeviceInfo)并得出每个工作组的最大工作项数，因为通过这种方法，您的工作项数量很可能会受到本地内存量的限制。

我怀疑这可能会工作得很好，因为:

• 简单的排序可能就完全没问题，特别是因为数组已经在很大程度上排序了
• 并行处理如此少量的项目并不值得(但是使用本地内存是值得的!)
• 由于您正在处理数十亿个这样的小数组，因此即使只有单个工作项处理这样的数组，您也会获得很大的占用率

如果您对我的想法有疑问，请告诉我。

编辑1:

我刚刚意识到我使用了一种可能会让其他人感到困惑的技术:我对使用本地内存的建议是不用于同步或对单个输入向量/数组使用多个工作项。我只是用它来获得较低的读/写内存延迟。由于我们使用相当大的内存块，我担心使用私有(private)内存可能会导致交换减慢全局内存，而我们却没有意识到。这也意味着您必须为每个工作项分配本地内存。每个工作项将访问其自己的本地内存块并将其用于排序(独占)。我不确定这个想法有多好，但我读到使用过多的私有(private)内存可能会导致交换到全局内存，唯一注意到的方法是查看性能(不确定我是否正确) )。