1

我编写了代码来并行实现双向选择排序。我使用了 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;
                        }
                });
4

1 回答 1

2

我认为如果您在 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 “通过交换。索引“max”<“m”。这意味着第一个线程永远不会找到下一个最小值，因为它在它的位置之前被移动了。

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

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

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

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”移动到索引“最小值”。如果我们执行交换（最大，k），结果会很糟糕。这就是为什么我们需要更新最大元素的索引，如果它位于索引 i 处。

于 2013-05-28T12:44:08.580 回答