9

只是一个简短的说明，这不是家庭作业。我只是想重温我的算法。我在 C# 中使用 MergeSort，我编写了一个可以基于泛型进行排序的递归方法：

class SortAlgorithms
{

    public T[] MergeSort<T> (T[] unsortedArray) where T : System.IComparable<T>
    {
        T[] left, right;
        int middle = unsortedArray.Length / 2;

        left = new T[middle];
        right = new T[unsortedArray.Length - middle];

        if (unsortedArray.Length <= 1)
            return unsortedArray;

        for (int i = 0; i < middle; i++)
        {
            left[i] = unsortedArray[i];
        }

        for (int i = middle; i < unsortedArray.Length; i++)
        {
            right[i - middle] = unsortedArray[i];
        }

        left = MergeSort(left);

        right = MergeSort(right);


        return Merge<T>(left, right);
    }

    private T[] Merge<T> (T[] left, T[] right) where T : System.IComparable<T>
    {
        T[] result = new T[left.Length + right.Length];

        int currentElement = 0;

        while (left.Length > 0 || right.Length > 0)
        {
            if (left.Length > 0 && right.Length > 0)
            {
                if (left[0].CompareTo(right[0]) < 0)
                {
                    result[currentElement] = left[0];
                    left = left.Skip(1).ToArray();
                    currentElement++;
                }
                else
                {
                    result[currentElement] = right[0];
                    right = right.Skip(1).ToArray();
                    currentElement++;
                }
            }
            else if (left.Length > 0)
            {
                result[currentElement] = left[0];
                left = left.Skip(1).ToArray();
                currentElement++;
            }
            else if (right.Length > 0)
            {
                result[currentElement] = right[0];
                right = right.Skip(1).ToArray();
                currentElement++;
            }
        }

        return result;
    }
}

这行得通，但速度很慢。我已经使用 System.Diagnostic.StopWatch 来检查 Array.Sort（它使用 QuickSort 算法）的性能，以与我的 MergeSort 进行比较，并且差异如此之大，我想知道我是否实施了这个错误。任何意见？

4

4 回答 4

12

我不是 C# 程序员，但问题可能出在使用这样的语句吗？

left = left.Skip(1).ToArray();

这可能以强制底层数组的深层副本的方式实现。如果是这样，这会将合并的性能从 O(n) 降低到 O(n 2 )，立即将生成的合并排序的性能从 O(n log n) 降低到 O(n 2 )。

（这是因为重复从

T(1) = O(1)

T(n) ≤ 2T(n / 2) + O(n)

有解 T(n) = O(n log n)，到

T(1) = O(1)

T(n) ≤ 2T(n / 2) + O(n 2 )

有解 T(n) = O(n 2 )。)

于 2012-08-27T20:02:52.017 回答
2

您不断地以中间数组的形式分配内存。考虑重用原始数组的方向。

于 2012-08-27T20:02:20.463 回答
1

正如其他两个答案所说，您正在到处创建新数组，为此花费大量时间和内存（我猜，您的大部分时间和几乎所有内存使用）。

再说一遍，我要补充一点，所有其他相等的递归往往比迭代慢，并使用更多的堆栈空间（甚至可能导致溢出，而​​问题足够大，而迭代不会）。

然而。合并排序非常适合多线程方法，因为您可以让不同的线程处理第一批分区的不同部分。

因此，如果我玩这个，我接下来的两个实验将是：

  1. 对于分区的第一部分MergeSort，我不会递归调用，而是启动一个新线程，直到每个核心都有一个线程在运行（在超线程的情况下，我应该按物理核心还是虚拟核心执行，本身就是我要试验的东西）。
  2. 完成后，我会尝试重新编写递归方法以在没有递归调用的情况下做同样的事情。

处理完这ToArray()件事后，看看多线程方法如何首先将工作分配给最佳数量的内核，然后让每个内核迭代地完成其工作，这确实会非常有趣。

于 2012-08-27T20:13:44.073 回答
0

首先，这里有一个类似问题的简化解决方案的链接：Java 合并排序，“合并”步骤应该用队列还是数组完成？

您的解决方案很慢，因为您反复分配新的子数组。内存分配比大多数其他操作更昂贵（您有分配成本、收集成本和缓存局部性丢失）。通常这不是问题，但如果您尝试编写严格的排序例程，那么它很重要。对于归并排序，您只需要一个目标数组和一个临时数组。

将线程分叉以并行化仍然比这贵几个数量级。因此，除非您有大量数据要排序，否则不要分叉。

正如我在上面的答案中提到的，加快合并排序的一种方法是利用输入数组中的现有顺序。

于 2012-08-28T00:05:30.223 回答