24

编辑3：

使用

StringComparer comparer1 = StringComparer.Ordinal;

代替

IComparable v
IComparable w
comparer1.Compare(v, w)

解决了运行时问题。

我在 Java 和 C# 中对排序算法（例如 Quicksort、Mergesort）做了一些基准测试。

我使用 Java 7 和 .NET Framework 4.5 来实现和执行我的算法。它表明所有算法都可以使用 Java 实现更好的运行时。

快速排序的一些示例运行时：

C＃

  1. n=1000000 4433 毫秒
  2. n=2000000 10047 毫秒

爪哇

  1. n=1000000 1311 毫秒
  2. n=2000000 3164 毫秒

然后我使用分析工具进行了测量：C# 使用 75% 的运行时进行字符串比较（即 CompareTo），而 Java 仅使用 2% 的运行时进行比较。

为什么字符串比较在 C# 中如此昂贵，而在 Java 中则不然？

编辑：我还测试了 C# 排序函数 Arrays.sort(INPUT) 对于 n=1000000 它可以达到大约 3000 毫秒，所以我不认为代码是问题所在。但无论如何：

这是快速排序的代码：

public class Quicksort {

public static void sort(IComparable[] a) {
    sort(a, 0, a.Length - 1);
}

private static void sort(IComparable[] a, int lo, int hi) { 
    if (hi <= lo) return;
    int j = partition(a, lo, hi);
    sort(a, lo, j-1);
    sort(a, j+1, hi);
}

private static int partition(IComparable[] a, int lo, int hi) {
    int i = lo;
    int j = hi + 1;
    IComparable v = a[lo];
    while (true) { 

        while (less(a[++i], v))
            if (i == hi) break;

        while (less(v, a[--j]))
            if (j == lo) break; 


        if (i >= j) break;

        exch(a, i, j);
    }

    exch(a, lo, j);

    return j;
}


public static IComparable select(IComparable[] a, int k) {
    if (k < 0 || k >= a.Length) {
        throw new Exception("Selected element out of bounds");
    }
    Rnd.Shuffle(a);
    int lo = 0, hi = a.Length - 1;
    while (hi > lo) {
        int i = partition(a, lo, hi);
        if      (i > k) hi = i - 1;
        else if (i < k) lo = i + 1;
        else return a[i];
    }
    return a[lo];
}


private static bool less(IComparable v, IComparable w) {
    return (v.CompareTo(w) < 0);
}
    
private static void exch(Object[] a, int i, int j) {
    Object swap = a[i];
    a[i] = a[j];
    a[j] = swap;
}

}

然后按如下方式测量快速排序：

Stopwatch.Restart();
Quicksort.sort(stringArray);
Stopwatch.Stop();

EDIT2：有人想看 Java 版本。完全一样，我只是使用 Comparable 而不是 IComparable 和 Array.length 而不是 Array.Length

4

2 回答 2

24

所以我认为代码不是问题

我不敢苟同。在这两种情况下，您都没有比较相同的事物。诚然，您还没有向我们展示如何生成字符串等，这并没有帮助，但是 Java 和 .NET 执行不同的默认字符串比较。

从Java的String.compareTo：

按字典顺序比较两个字符串。

而来自.NET的String.CompareTo：

此方法使用当前区域性执行单词（区分大小写和区域性）比较。

毫不奇怪，这比进行纯粹的字典比较慢。

当仅将 .NET 与自身进行比较时，很容易看出这一点......

using System;
using System.Diagnostics;
using System.Text;

class Test
{
    static void Main()
    {
        string[] source = GenerateRandomStrings();
        string[] workingSpace = new string[source.Length];

        CopyAndSort(source, workingSpace);
        Stopwatch sw = Stopwatch.StartNew();
        for (int i = 0; i < 1000; i++)
        {
            CopyAndSort(source, workingSpace);
        }
        sw.Stop();
        Console.WriteLine("Elapsed time: {0}ms", 
                          (long) sw.Elapsed.TotalMilliseconds);
    }

    static string[] GenerateRandomStrings()
    {
        Random rng = new Random();
        string[] ret = new string[10000];
        for (int i = 0; i < ret.Length; i++)
        {
            ret[i] = GenerateRandomString(rng);
        }
        return ret;
    }

    static string GenerateRandomString(Random rng)
    {
        char[] chars = new char[30];
        for (int i = 0; i < chars.Length; i++)
        {
            chars[i] = (char) rng.Next('A', 'z' + 1);
        }
        return new string(chars);
    }

    static void CopyAndSort(string[] original, string[] workingSpace)
    {
        Array.Copy(original, 0, workingSpace, 0, original.Length);
        Array.Sort(workingSpace);
        // Array.Sort(workingSpace, StringComparer.Ordinal);
    }
}

自己尝试一下，CopyAndSort根据您是否指定序数字符串比较器来改变方法。使用序数比较器要快得多，至少在我的盒子上。

于 2013-03-05T00:50:34.920 回答
9

我不是 100% 确定，但我认为在 C# 中，.Net 平台默认情况下可能会执行一些扩展检查，例如正确跳过注释或空白 unicode 字符，而 Java 默认情况下可能不会执行这些检查。我认为 Java 的运行时执行更简单的 byte-2-byte 比较，但我在这里可能非常错误，因为我已经很长时间没有接触到在 Java 中使用编码的细节了，所以这纯粹是猜测。

另一件事：这两个平台之间的默认比较行为可能存在一些差异。如果您只使用默认值，没有任何精确设置，我猜您只是隐含地要求不同的行为。

至少在.Net 中有很多字符串比较选项。可能发生的情况是，您只是采用了看起来相似的函数，但实际上与 Java 进行了不同的比较。您是否尝试过详细的重载，例如http://msdn.microsoft.com/en-us/library/cc190416.aspx？请注意，这是一种static使用方式略有不同的方法：

var result1 = "mom".CompareTo("dad");
var result2 = string.Compare("mom", "dad", ...);

请调查ComparisonOptions 和/或CultureInfo 设置，并调整它们以使整体行为尽可能地匹配Java 的行为。此外，如果有更多重载，您可能也必须在 Java 端选择不同的重载。

此外，另一个区别可能有点棘手，您正在测试的 CompareTo 方法是IComparable<T>接口的实现，旨在交叉比较实现此接口的各种对象，而静态Compare方法旨在仅比较字符串。它们可以简单地针对不同的事物进行优化。如果它们之间会有任何性能差异，我敢打赌静态Compare对于字符串与字符串的比较来说更快。

于 2013-03-05T00:27:16.853 回答