为什么Java中的字符串比较(CompareTo)比C#更快？

Question

EDIT3:

运用

StringComparer comparer1 = StringComparer.Ordinal;

代替

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

解决了运行时问题.

---

我已经在Java和C#中对排序算法(例如Quicksort,Mergesort)做了一些基准测试.

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

Quicksort的一些示例运行时:

C#

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

Java的

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

然后我使用分析工具完成了测量:C#使用75%的运行时进行字符串比较(即CompareTo),而Java仅使用2%的运行时进行比较.

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

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

这是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;
}

}

Quicksort然后测量如下:

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

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

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根据是否指定序数字符串比较器来改变方法.这是多以序号比较器速度更快,至少在我的箱子.

Answer 2

我不是百分百肯定,但我认为在C#中.Net平台默认情况下会执行一些扩展检查,例如正确跳过注释或空格unicode字符和Java,默认情况下可能不会这样做.我认为Java的运行时执行简单的字节2字节比较,但我在这里可能是非常错误的,因为我已经触及了使用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对于字符串与字符串的比较,静态更快.