在修改了少量元素后重新排序向量

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 0 1如果先前排序的向量是0 1 1 1 1 并且第4个元素被修改,但是没有办法形成0 1 0 1 0有效输入,因为它与任何有序向量的至少2个元素不同.

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

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

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

并且该网络具有深度4,与一般情况相比节省1(对于5元素向量进行排序通常需要5的深度.)

不幸的是,对于较大的输入尺寸,蛮力方法是不可行的.

是否有一种已知的方法来构建网络以重新排序较大的向量？

我ñ值将是几百的顺序,用中号比√不更ñ.

Answer 1

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

你应该尝试一下这个：

• 在本地内存上实现简单的顺序排序（插入排序或类似的排序）。如果你不知道怎么做——我可以帮忙。
• 只有一个工作项对 N 个元素的块执行排序
• 计算每个工作组的本地内存的最大大小（使用 调用clGetDeviceInfo）CL_DEVICE_LOCAL_MEM_SIZE并得出每个工作组的最大工作项数，因为使用这种方法，您的工作项数很可能会受到本地内存量的限制。

我怀疑这可能会很好地发挥作用，因为：

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

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

编辑1：

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