Tại sao so sánh String (CompareTo) nhanh hơn trong Java so với trong C#?

Question

EDIT3:

Sử dụng

StringComparer comparer1 = StringComparer.Ordinal; 

thay vì

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

Giải quyết được vấn đề thời gian chạy.

---

Tôi đã thực hiện một số tiêu chuẩn về các thuật toán sắp xếp (ví dụ: Quicksort, Mergesort) trong Java và C#.

Tôi đã sử dụng Java 7 và .NET Framework 4.5 để triển khai và thực thi các thuật toán của mình. Nó cho thấy rằng tất cả các thuật toán có thể đạt được thời gian hoạt động tốt hơn bằng cách sử dụng Java.

Một số runtimes ví dụ cho Sắp xếp nhanh:

C#

1. n = 1000000 4433 ms
2. n = 2000000 10.047 ms

Java

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

Sau đó, tôi đã thực hiện các biện pháp sử dụng công cụ profiling: C# sử dụng 75% thời gian chạy để so sánh chuỗi (ví dụ: CompareTo), trong khi Java chỉ sử dụng 2% thời gian chạy để so sánh.

Tại sao so sánh chuỗi quá đắt trong C# chứ không phải trong Java?

EDIT: Tôi cũng đã thử nghiệm hàm sắp xếp C# Arrays.sort (INPUT) nó có thể đạt được khoảng 3000 ms cho n = 1000000, vì vậy tôi không nghĩ rằng mã đó là vấn đề. Nhưng dù sao:

Dưới đây là các mã cho Sắp xếp nhanh:

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

} 

Sắp xếp nhanh được đo sau đó như sau:

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

EDIT2: Ai đó muốn xem phiên bản Java. Nó chính xác giống như tôi chỉ sử dụng Comparable thay vì IComparable và Array.length thay vì Array.Length

Answer 1

vì vậy tôi không nghĩ rằng mã là vấn đề

tôi xin trân trọng khác nhau. Bạn không so sánh những điều tương tự trong cả hai trường hợp. Phải thừa nhận rằng nó không giúp bạn cũng không cho chúng tôi biết cách bạn tạo chuỗi, v.v. Nhưng Java và .NET thực hiện các so sánh chuỗi mặc định khác nhau.

Từ Java String.compareTo:

So sánh hai chuỗi thứ tự từ điển.

Và từ NET của String.CompareTo:

Phương pháp này thực hiện một từ (case-sensitive và văn hóa nhạy cảm) so sánh bằng cách sử dụng văn hóa hiện hành.

Không có gì ngạc nhiên khi điều này chậm hơn so với so sánh hoàn toàn bằng từ điển.

Thật dễ dàng để thấy điều này khi chỉ so sánh NET với chính nó ...

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

Hãy thử nó cho mình, cách thay đổi CopyAndSort phương pháp dựa vào việc bạn chỉ định một chuỗi Comparer thứ tự hay không. Đó là nhiều hơn nhanh hơn với bộ so sánh thứ tự, ít nhất là trên hộp của tôi.

Answer 2

Tôi không chắc chắn 100%, nhưng tôi nghĩ rằng trong C# nền tảng .Net có thể làm theo mặc định một số kiểm tra mở rộng như thích hợp bỏ qua các chú giải hoặc các ký tự unicode khoảng trắng và Java có thể không làm chúng theo mặc định. Tôi nghĩ rằng thời gian chạy của Java thực hiện so sánh byte-2 byte đơn giản hơn, nhưng tôi có thể rất sai ở đây, vì nó đã khá lâu kể từ khi tôi chạm vào chi tiết làm việc với các mã hóa trong Java, do đó, đó là phỏng đoán thuần túy.

Một điều khác: có thể có một số khác biệt trong hành vi so sánh mặc định giữa hai nền tảng đó.Nếu bạn chỉ sử dụng các giá trị mặc định, không có bất kỳ cài đặt chính xác nào, tôi đoán bạn chỉ đơn giản là yêu cầu các hành vi khác nhau.

Ít nhất trong. Net có nhiều tùy chọn so sánh chuỗi. Nó có thể xảy ra mà bạn chỉ đơn giản là lấy chức năng tìm kiếm tương tự mà thực sự làm một so sánh khác nhau của Java. Bạn đã thử với quá tải chi tiết như http://msdn.microsoft.com/en-us/library/cc190416.aspx chưa? Lưu ý rằng đây là một phương pháp static được sử dụng chút khác nhau:

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

Hãy điều tra các ComparisonOptions và/hoặc cài đặt CultureInfo, và điều chỉnh chúng để các hành vi tổng thể phù hợp với hành vi của Java càng sát càng tốt. Ngoài ra, bạn có thể phải chọn một tình trạng quá tải khác ở phía Java, nếu có nhiều hơn.

Ngoài ra, một sự khác biệt có thể là thực tế hơi phức tạp, phương pháp CompareTo mà bạn đang thử nghiệm thực hiện giao diện IComparable<T> có nghĩa là so sánh các đối tượng khác nhau thực hiện giao diện này và phương pháp tĩnh Compare chỉ so sánh các chuỗi. Chúng đơn giản có thể được tối ưu hóa cho những thứ khác nhau. Nếu có bất kỳ sự khác biệt về hiệu năng nào giữa chúng, tôi sẽ đặt cược static Compare là nhanh hơn cho các so sánh chuỗi-vs-string.