So sánh nhanh nhất (được xây dựng trong) cho các loại chuỗi trong C#

Question

Phương pháp so sánh được xây dựng sẵn nhất nhanh nhất cho các loại chuỗi trong C# là gì? Tôi không quan tâm đến ý nghĩa đánh máy/ngữ nghĩa: mục tiêu là sử dụng bộ so sánh trong các danh sách được sắp xếp để tìm kiếm nhanh trong các bộ sưu tập lớn. Tôi nghĩ rằng chỉ có hai phương pháp: Compare và CompareOrdinal. Nhanh nhất là gì?

Ngoài ra, có phương pháp nhanh hơn cho các so sánh chuỗi đó không?

Answer 1

Tôi giả sử bạn muốn có so sánh nhỏ hơn/bằng/lớn hơn thay vì bình đẳng; bình đẳng là một chủ đề hơi khác nhau, mặc dù các nguyên tắc cơ bản giống nhau. Nếu bạn thực sự chỉ tìm kiếm sự hiện diện của trong một cái gì đó như một số SortedList, tôi sẽ xem xét sử dụng một số Dictionary<string, XXX> để thay thế - bạn có thực sự cần tất cả việc sắp xếp đó không?

String.CompareOrdinal hoặc sử dụng quá tải String.Compare cho phép so sánh được cung cấp và chỉ định so sánh thứ nguyên (phân biệt chữ hoa chữ thường), ví dụ: String.Compare(x, y, StringComparison.Ordinal) sẽ là nhanh nhất.

Về cơ bản so sánh thứ tự chỉ cần cần phải đi bộ hai chuỗi, ký tự theo ký tự, cho đến khi tìm thấy sự khác biệt. Nếu nó không tìm thấy bất kỳ sự khác biệt, và độ dài là như nhau, kết quả là 0. Nếu nó không tìm thấy bất kỳ sự khác biệt nhưng độ dài không giống nhau, chuỗi dài hơn được coi là "lớn hơn". Nếu nó không tìm sự khác biệt, nó có thể ngay lập tức làm việc ra được coi là "lớn hơn" dựa trên đó nhân vật là "lớn hơn" trong điều kiện thứ tự.

Đặt theo một cách khác: giống như thực hiện so sánh rõ ràng giữa hai giá trị char[].

So sánh văn hóa nhạy cảm phải thực hiện tất cả các loại kỳ công quanh co, tùy thuộc vào văn hóa chính xác bạn sử dụng. Để biết ví dụ về điều này, hãy xem this question. Nó khá rõ ràng rằng có các quy tắc phức tạp hơn để làm theo có thể làm cho điều này chậm hơn.

Answer 2

Nhanh nhất là chuỗi nội bộ có kiểm tra bình đẳng tham chiếu, nhưng bạn chỉ nhận được kiểm tra bình đẳng và chi phí quá cao của bộ nhớ - quá đắt đến mức gần như không bao giờ là khóa học được đề xuất.

Qua đó, một thử nghiệm thứ tự phân biệt chữ hoa chữ thường sẽ là nhanh nhất, và phương pháp này hoàn toàn được khuyến nghị cho các chuỗi không phải là văn hóa cụ thể. Phân biệt chữ hoa chữ thường nhanh hơn nếu nó hoạt động cho trường hợp sử dụng của bạn.

Khi bạn chỉ định StringComparison.Ordinal hoặc StringComparison.OrdinalIgnoreCase, so sánh chuỗi sẽ không phải ngôn ngữ. Đó là, các tính năng dành riêng cho ngôn ngữ tự nhiên bị bỏ qua khi đưa ra quyết định so sánh. Điều này có nghĩa là các quyết định dựa trên các so sánh byte đơn giản và bỏ qua các bảng vỏ hoặc các bảng tương đương được tham số hóa bởi văn hóa. Kết quả là, bằng cách đặt thông số rõ ràng thành StringComparison.Ordinal hoặc StringComparison.OrdinalIgnoreCase, mã của bạn thường tăng tốc độ, tăng độ chính xác và trở nên đáng tin cậy hơn.

Source

Answer 3

Tôi đã kiểm tra cả string.Compare và chuỗi.CompareOrdinal sử dụng stop watch

--Compare Ordinal case 1 
    Stopwatch sw = new Stopwatch(); 
    sw.Start(); 
    int x = string.CompareOrdinal("Jaswant Agarwal", "Jaswant Agarwal"); 
    sw.Stop(); 
    lblTimeGap.Text = sw.Elapsed.ToString(); 






    -- Only compare case 2 
    Stopwatch sw = new Stopwatch(); 
    sw.Start(); 
    int x = string.Compare("Jaswant Agarwal", "Jaswant Agarwal"); 
    sw.Stop(); 
    lblTimeGap.Text = sw.Elapsed.ToString(); 

Trong trường hợp 1 thời gian trôi qua trung bình là 00: 00: 00,0000030 Trong trường hợp 2 thời gian trôi qua trung bình là 00: 00: 00,0000086

tôi đã cố gắng với sự kết hợp bình đẳng và không bình đẳng khác nhau chuỗi và thấy rằng mỗi khi CompareOrdinal là nhanh hơn so với chỉ so sánh ..

đó là của riêng tôi observation..you cũng có thể thử chỉ cần đặt hai nút trên một hình thức sao chép và dán mã này trong chuyển loại sự kiện ..

Answer 4

Tôi đã thiết kế một thử nghiệm đơn vị để kiểm tra tốc độ so sánh chuỗi bằng cách sử dụng một số phương pháp được đề cập trong bài đăng này. Thử nghiệm này đã được chạy bằng cách sử dụng .NET 4

Tóm lại, không có nhiều sự khác biệt và tôi phải chuyển đến 100.000.000 lần lặp lại để thấy sự khác biệt đáng kể. Vì có vẻ như các nhân vật được so sánh lần lượt cho đến khi một sự khác biệt được tìm thấy, chắc chắn làm thế nào tương tự như các dây được đóng một phần.

Những kết quả này dường như gợi ý rằng việc sử dụng str1.Equals (str2) là cách nhanh nhất để so sánh chuỗi.

Đây là kết quả của thử nghiệm, với các lớp thử nghiệm bao gồm:

######## SET 1 compared strings are the same: 0 
#### Basic == compare: 413 
#### Equals compare: 355 
#### Equals(compare2, StringComparison.Ordinal) compare: 387 
#### String.Compare(compare1, compare2, StringComparison.Ordinal) compare: 426 
#### String.CompareOrdinal(compare1, compare2) compare: 412 

######## SET 2 compared strings are NOT the same: 0 
#### Basic == compare: 710 
#### Equals compare: 733 
#### Equals(compare2, StringComparison.Ordinal) compare: 840 
#### String.Compare(compare1, compare2, StringComparison.Ordinal) compare: 987 
#### String.CompareOrdinal(compare1, compare2) compare: 776 

using System; 
using System.Diagnostics; 
using NUnit.Framework; 

namespace Fwr.UnitTests 
{ 
    [TestFixture] 
    public class StringTests 
    { 
     [Test] 
     public void Test_fast_string_compare() 
     { 
      int iterations = 100000000; 
      bool result = false; 
      var stopWatch = new Stopwatch(); 

      Debug.WriteLine("######## SET 1 compared strings are the same: " + stopWatch.ElapsedMilliseconds); 

      string compare1 = "xxxxxxxxxxxxxxxxxx"; 
      string compare2 = "xxxxxxxxxxxxxxxxxx"; 

      // Test 1 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = compare1 == compare2; 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### Basic == compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 2 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = compare1.Equals(compare2); 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### Equals compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 3 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = compare1.Equals(compare2, StringComparison.Ordinal); 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### Equals(compare2, StringComparison.Ordinal) compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 4 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = String.Compare(compare1, compare2, StringComparison.Ordinal) != 0; 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### String.Compare(compare1, compare2, StringComparison.Ordinal) compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 5 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = String.CompareOrdinal(compare1, compare2) != 0; 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### String.CompareOrdinal(compare1, compare2) compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      Debug.WriteLine("######## SET 2 compared strings are NOT the same: " + stopWatch.ElapsedMilliseconds); 

      compare1 = "ueoqwwnsdlkskjsowy"; 
      compare2 = "sakjdjsjahsdhsjdak"; 

      // Test 1 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = compare1 == compare2; 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### Basic == compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 2 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = compare1.Equals(compare2); 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### Equals compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 3 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = compare1.Equals(compare2, StringComparison.Ordinal); 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### Equals(compare2, StringComparison.Ordinal) compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 4 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = String.Compare(compare1, compare2, StringComparison.Ordinal) != 0; 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### String.Compare(compare1, compare2, StringComparison.Ordinal) compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 

      // Test 5 

      stopWatch.Start(); 

      for (int i = 0; i < iterations; i++) 
      { 
       result = String.CompareOrdinal(compare1, compare2) != 0; 
      } 

      stopWatch.Stop(); 

      Debug.WriteLine("#### String.CompareOrdinal(compare1, compare2) compare: " + stopWatch.ElapsedMilliseconds); 

      stopWatch.Reset(); 
     } 
    } 
} 

Answer 5

Tôi chỉ nhận thấy một sự gia tăng hiệu suất 50% trong mã của riêng tôi bằng cách so sánh độ dài chuỗi đầu tiên và nếu bình đẳng sau đó sử dụng các chuỗi phương pháp .compare. Vì vậy, trong một vòng lặp Tôi có:

VB:

If strA.length = strB.length then 
    if string.compare(strA,strB,true) = 0 then 
     TheyAreEqual 
    End if 
End if 

C#:

if(strA.Length == strB.Length) 
{ 
    if(string.Compare(strA,strB,true) == 0) 
    { 
     //they are equal 
    } 
} 

Điều này có thể phụ thuộc vào chuỗi riêng của bạn, nhưng dường như nó đã làm việc tốt cho tôi .

Answer 6

Điều này có thể hữu ích đối với ai đó, nhưng việc thay đổi một dòng mã của tôi đã mang đơn vị thử nghiệm phương pháp của tôi xuống từ 140ms đến 1ms!

Original test

Đơn vị: 140ms

public bool StringsMatch(string string1, string string2) 
{ 
    if (string1 == null && string2 == null) return true; 
    return string1.Equals(string2, StringComparison.Ordinal); 
} 

New

Đơn vị kiểm tra: 1ms

public bool StringsMatch(string string1, string string2) 
{ 
    if (string1 == null && string2 == null) return true; 
    return string.CompareOrdinal(string1, string2) == 0 ? true : false; 
} 

Unit Kiểm tra (NUnit)

[Test] 
public void StringsMatch_OnlyString1NullOrEmpty_ReturnFalse() 
{ 
    Authentication auth = new Authentication(); 
    Assert.IsFalse(auth.StringsMatch(null, "foo")); 
    Assert.IsFalse(auth.StringsMatch("", "foo")); 
} 

Điều thú vị StringsMatch_OnlyString1NullOrEmpty_ReturnFalse() là bài kiểm tra đơn vị duy nhất mà mất 140ms đối với phương pháp StringsMatch. StringsMatch_AllParamsNullOrEmpty_ReturnTrue() luôn là 1ms và StringsMatch_OnlyString2NullOrEmpty_ReturnFalse() luôn luôn < 1ms.

Answer 7

Đây là một câu hỏi khá cũ, nhưng vì tôi cũng tìm thấy những câu hỏi khác.

Trong nghiên cứu chủ đề này xa hơn một chút, tôi đã xem một số interesting blog post so sánh tất cả các phương pháp so sánh chuỗi. Có lẽ không có khoa học cao nhưng vẫn là một housenumber tốt.

Nhờ bài viết này tôi bắt đầu sử dụng string.CompareOrdinal trong một kịch bản mà tôi đã phải tìm ra nếu một chuỗi nằm trong danh sách 170.000 chuỗi khác và thực hiện 1600 lần liên tiếp. string.CompareOrdinal làm cho nó gần như nhanh hơn 50% so với string.Equals