为什么在Java中字符串比较（CompareTo）比C#快？

Question

编辑3：

使用

StringComparer comparer1 = StringComparer.Ordinal;

替代

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

解决了运行时问题。

---

我在Java和C#中实现和执行了一些排序算法（例如Quicksort，Mergesort），并进行了基准测试。结果显示，使用Java可以使所有算法的运行时间更短。

以下是Quicksort的一些示例运行时间：

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

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

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

为什么在C#中字符串比较如此昂贵，而在Java中却不是这样？

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

以下是Quicksort的代码：

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();

编辑2：有人想看Java版本。它完全相同，只是我使用Comparable而不是IComparable，并使用Array.length而不是Array.Length。

- Mad A.

---

请展示你正在使用的代码。有许多因素可能会影响这个问题。 - Jon Skeet

我对这里发生的事情有一个“怀疑”，但我正在等待看代码。 - Jon Skeet

@RBarryYoung 我觉得他在这里并没有试图提出任何主张。我猜他正在做正确的事情，试图确定可能的原因，然后再得出结论。但确实我们需要看到测试方法来帮助他们解决这个问题。 - AaronLS

Java 版本也请附上。 - kritzikratzi

Java中的字符串驻留（interning）在C#中为什么没有？ - devoured elysium

如果这就是全部的代码，那么很可能你糟糕的基准测试方法正在扭曲你所得到的数字。在我看来，它们不可靠。 - Stephen C

Answer 1

我不认为代码有问题。 我持不同意见。在两种情况下，您没有进行相同的比较。尽管您还没有向我们展示如何生成字符串等内容，但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方法。使用序数比较器会更快，至少在我的计算机上是这样。

- Jon Skeet

---

你为什么在测量之前调用 CopyAndSort 一次？这是为了确保每次运行都以相同的 workingSpace 状态（即已排序）开始吗？ - poke

不，这是为了确保我们开始测量之前已经进行了即时编译。 - Jon Skeet

Answer 2

我不太确定，但我认为在C#中，.Net平台可能默认执行一些扩展检查，例如正确跳过注释或空白的Unicode字符，并且Java可能默认不执行它们。我认为Java的运行时会执行更简单的逐字节比较，但我可能非常错误，因为我很久没有涉及Java中的编码工作细节了，所以这只是猜测。

另一个问题是：这两个平台之间可能存在默认比较行为上的差异。如果您只使用默认设置而没有任何精确的设置，我想您可能隐式请求了不同的行为。

至少在.Net中有许多字符串比较选项。您可能只是选择了外观相似但实际执行的不同比较操作的函数。您尝试过像http://msdn.microsoft.com/en-us/library/cc190416.aspx这样的详细重载吗？请注意，这是要稍微不同地使用的静态方法。

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

请检查ComparisonOptions和/或CultureInfo设置，调整它们以尽可能接近Java的行为。此外，如果Java端有多个overload，您可能还需要选择一个不同的overload。

另外，另一个差异可能是相当棘手的事实，您正在测试的CompareTo方法是实现IComparable接口的，该接口旨在交叉比较实现此接口的各种对象，而静态Compare方法仅设计用于比较字符串。它们可能仅针对不同的优化。如果它们之间有任何性能差异，我敢打赌，静态Compare在字符串与字符串比较方面更快。

- quetzalcoatl

---

我也测试了C#的排序方法Arrays.Sort(input)和Collection.Sort()，但对于n=1000000，运行时间为3000毫秒，因此Java仍然快了300%。 - Mad A.

默认的无参数 Arrays.Sort 和 Collection.Sort 总是使用最通用的 IComparable 接口，因为它没有其他选项。这些函数旨在“易于使用”而不是“最快”或“最轻”。它们甚至必须检查 LHS 和 RHS 是否具有相同的类型，这会进一步影响性能。为了精细地调整性能，您可能需要使用排序算法，至少采用 comparer 或 comparison delegate，以便您可以指定确切的比较行为。但是，请让我再说一遍：我所写的一切只是猜测。 - quetzalcoatl

尝试使用StringComparer.Ordinal指定比较方式进行相同的测试。基本上，Java默认使用序数比较，而.NET则不是。 - Jon Skeet

@JonSkeet 您说得对。我使用了StringComparer，n=1000000时运行时间为1545毫秒。 - Mad A.

重要的是使用哪种StringComparer。StringComparer.Ordinal可以让它基本上与Java的工作方式相同。 - Jon Skeet