24

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 ミリ秒

ジャワ

  1. n=1000000 1311ミリ秒
  2. n=2000000 3164 ミリ秒

次に、プロファイリング ツールを使用して測定を行いました。C# はランタイムの 75% を文字列比較 (CompareTo) に使用しましたが、Java はランタイムの 2% しか比較に使用しませんでした。

JavaではなくC#で文字列比較が非常に高価なのはなぜですか?

編集: 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 のバージョンを見たいと思っていました。IComparable の代わりに Comparable を使用し、Array.Length の代わりに Array.length を使用するのとまったく同じです。

4

2 に答える 2

24

だから私はコードが問題だとは思わない

失礼ですが同意できません。どちらの場合も同じものを比較していません。確かに、文字列の生成方法などを示していないことは役に立ちませんが、Java と .NET は異なるデフォルトの文字列比較を実行します。

Java からString.compareTo:

2 つの文字列を辞書順に比較します。

そして.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 のランタイムはより単純なバイト 2 バイトの比較を実行すると思いますが、Java でのエンコーディングの操作の詳細に触れてからかなり時間が経っているため、ここでは非常に間違っている可能性があります。

もう 1 つ: これら 2 つのプラットフォーム間で、デフォルトの比較動作にいくつかの違いがある可能性があります。正確な設定を行わずにデフォルトのみを使用すると、暗黙的に異なる動作を要求しただけだと思います。

少なくとも .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 に答える