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

Question

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

9

如果我们有一个大小为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，与一般情况相比（一般需要深度为5才能对5个元素向量进行排序），节省了1个深度。

不幸的是，对于更大的输入大小，暴力方法是不可行的。 是否有已知的方法来构建一个网络以重新排序更大的向量？ 我的N值将按几百个顺序排列，而M不会超过√N。

- finnw

1

我认为一些排序方法将数据分成几个部分，并仅对这些部分进行测试。也许您可以通过知道每个桶不能有超过某些未排序的元素数量来适应它并降低方法的成本。对于小的M值，您还可以找到未排序的元素，将它们单独排序，然后再将它们合并到完整列表中。但是这种方法无法并行化。 - DarkZeros

@DarkZeros 我认为你的第一个建议是正确的。我正在尝试使用希尔排序算法进行实验。 - finnw

一些额外的信息会很好：

N 的范围是否真的只有几百？
你期望排序算法的什么样的性能表现？如果问题规模不是很大，那么一个复杂的网络可能不值得麻烦。
到目前为止，你尝试过哪些排序算法？
根据你的问题，我理解你的意思是：“我只改变了一些元素，如果已知这些信息，是否有一种排序算法可以比常规算法快得多，或者如果大部分元素已经排序，是否有一种算法可以更快地执行”。我的理解正确吗？

- Baiz

另外：- 你在排序和排序网络领域的理解有多深？我问这个问题是为了不浪费你的时间，因为我的知识相当有限。 - Baiz

1

如果你想要对几乎有序的数据进行排序，插入排序是一个不错的选择。另一个选择是“自然合并排序”。对于几乎有序的数据，我会把希尔排序排在这两个之后。 - Taekahn

显示剩余4条评论

2个回答

1

这是一个算法，应该能够产生非常好的排序网络。可能不是所有输入大小的绝对最佳网络，但希望对实际目的足够好。

为 n < 16 存储（或可用）预计算网络
使用最优网络对最大的2^k个元素进行排序。例如：对于小于等于n的最大2的幂次，使用双调排序(bitonic sort)。
对于剩余的元素，重复步骤#2，直到未排序元素数量m < 16
使用步骤#1中已知的最优网络来排序任何剩余元素
使用归并排序网络将最小和第二小的子列表合并排序
重复步骤#5，直到只剩下一个已排序列表

所有这些步骤都可以人工完成，并将比较存储到主网络中，而不是作用于数据上。

值得指出的是，步骤#2中的（双调）网络可以并行运行，而较小的网络将先完成。这很好，因为它们完成后，从#5-6的网络就可以开始执行。

- mfa

请说明"largest 2^k"的含义。 - finnw

看起来你所描述的是一个完整的排序。鉴于您不知道输入中这些元素的位置，您在哪里利用只有M个元素可以更改的事实呢？ - finnw

我认为在不事先知道元素位置的情况下，没有办法优化已知数量的乱序排序网络。你甚至不知道这些M个元素是否按照顺序排列。唯一保证的解决方案是有效地重新排序列表。至少你知道大多数比较不会导致交换。 - mfa

“最大的2^k”指的是“小于n的最大2的幂”。我的小写字母n除了步骤2的第一次迭代外，不等于N。 - mfa

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Baiz · Accepted Answer

好的，由于评论限制长度让我无法忍受，所以我把这个作为回答发布了 :)

你应该尝试这个：

实现一个简单的使用本地内存进行排序的顺序排序（如插入排序或类似的算法）。如果您不知道怎么做 - 我可以帮助。
只让一个工作项对N个元素的块执行排序
计算每个工作组的本地内存最大大小（使用clGetDeviceInfo和CL_DEVICE_LOCAL_MEM_SIZE参数），并推导出每个工作组的最大工作项数目，因为使用此方法时，工作项数目很可能会受到本地内存量的限制。

我怀疑这个方法可能会非常有效，因为：

简单的排序可能是完全可以接受的，特别是由于数组已经在很大程度上排好序了
针对如此少量的项目进行并行化没有意义（但使用本地内存却有用！）
由于您要处理数十亿个这样的小数组，即使只有单个工作项处理这样的数组，您也将获得非常高的占用率

如果我的想法有问题，请让我知道。

编辑1：

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