c# - 并行双向选择排序

Question

我编写了代码来并行实现双向选择排序。我使用了 c# 和 parallel.invoke 函数。并行调用了 2 个循环，一个用于查找最小值，一个用于查找最大值。然而，它没有排序。我想知道问题是因为这种类型的排序无法并行处理，因为每个循环都依赖于另一个循环中存在的数据？...还是我的代码有问题？

Parallel.Invoke(
            () => 
                {                        
                    for (int i=0; i < array.Length / 2; i++)
                    {
                        int m;
                        int min = i;
                        for (m = i + 1; m < array.Length - 1; m++)
                            if (array[m] < array[min])
                                min = m;
                        //swap
                        int temp = array[min];
                        array[min] = array[m];
                        array[m] = temp;
                    }
                },
                () => 
                    {
                        for (int m = 0; m < array.Length / 2; m++)
                        {
                            int length = array.Length - 1;
                            int max = length - m;
                            int k;
                            for (k = length--; k > 0; k--)
                                if (array[k] > array[max])
                                    max = k;
                            //swap
                            int temp = array[max];
                            array[max] = array[k];
                            array[k] = temp;
                        }
                });

Answer 1

我认为如果您在 1 个线程的同一循环中搜索最小值和最大值会更容易:(java 代码，但我假设您会理解原理)

    int minimum, maximum;
    int k = size();
    for(int i = 0; i < size(); ++i)
    {
        --k;
        minimum = i;
        maximum = k;
        if(k - i <= 0)
            break;
        for(int j = i; j <= k; ++j)
        {
            if(greaterThan(minimum, j))
                minimum = j;
            if(lessThan(maximum, j))
                maximum = j;
        }

        if(minimum != i)
        {
            swap(minimum, i);
            if(maximum == i)
                maximum = minimum;
        }
        if(maximum != k)
            swap(maximum, k);
    }

你的代码的问题是这样的:

假设这是数组:

[5, 4, 3, 2, 1]

第 0 次迭代:第一个线程将找到最小元素放在索引 0 上
第一个线程在索引 4 处找到最小元素
迭代 0:第二个线程将找到最大的元素放在索引 4
第二个线程在索引 0 处找到最大元素

您已经看到这不会很好地结束，因为两个线程将在索引 0 和 4 之间执行交换，导致与现在相同的情况。

另一个问题是，如果您的第一个线程从 m -> array.length - 1 循环。如果同时线程 2 从索引 k 移动最小元素(它不需要，因为它正在搜索最大值)通过交换“最大”。索引“max”<“m”。这意味着第一个线程永远不会找到下一个最小值，因为它被移动到了它的位置之前。

编辑:经过考虑，我认为不可能实现选择排序的直接并行版本。我最初推荐的版本确实无法正常工作，因为算法每次都找到相同的最小值，因为它没有更改输入数组。

可能的是只对数组的前半部分使用线程 1 执行选择排序(并且只允许它在该半部分找到最小值)，而数组的后半部分用于第二个线程。最后，您可以使用合并排序算法合并两半。

这样你总是可以使用 2 个以上的线程；例如说“p”线程数量。每个负责输入数组的 N/p 部分，“N”是输入大小。最后，您只需将每个部分与合并排序算法合并即可。我自己从未实现过它，所以我不能说它是否有效，但我认为会有更好的算法来并行化(比如合并排序本身)。

PS:关于上面贴出的代码。我认为除了这一部分之外，一切看起来都很简单:

            if(maximum == i)
                maximum = minimum;

就是这样处理的:
. . .我 。 . . k
[1, 4, 3, 1, 5]

因此 i = 1 和 k = 3(索引)。

算法会发现:
最大值 = 索引 1
最小 = 索引 3

将索引i上的最小值交换后，情况就变成了这样:
. . .我 。 . . k
[1, 1, 3, 4, 5]

表示最大值(整数 4)实际上从索引“i”移动到索引“最小值”。如果我们执行 swap(maximum, k)，结果会很糟糕。这就是为什么我们需要更新位于索引 i 处的最大元素的索引。