c# - 为什么 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 实现更好的运行时。

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

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 毫秒，所以我认为代码不是问题所在。但无论如何:

这是快速排序的代码:

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

Answer 1

so i don't think the code is the problem

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

来自 Java 的 String.compareTo :

Compares two strings lexicographically.

来自 .NET 的 String.CompareTo :

This method performs a word (case-sensitive and culture-sensitive) comparison using the current culture.

这比进行纯粹的字典比较慢也就不足为奇了。

仅将 .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 方法。使用序数比较器要快得多，至少在我的盒子上是这样。