Cách nhanh nhất để lặp qua các ký tự riêng lẻ trong một chuỗi trong C# là gì?

Question

Tiêu đề là câu hỏi. Dưới đây là nỗ lực của tôi để trả lời nó thông qua nghiên cứu. Nhưng tôi không tin tưởng vào nghiên cứu không được định dạng của mình nên tôi vẫn đặt ra câu hỏi (Cách nhanh nhất để lặp qua các ký tự riêng lẻ trong một chuỗi trong C# là gì?).

Thỉnh thoảng, tôi muốn quay vòng qua các ký tự của một chuỗi một, chẳng hạn như khi phân tích cú pháp cho các mã thông báo lồng nhau - một cái gì đó mà cannot be done with regular expressions. Tôi tự hỏi cách nhanh nhất là lặp qua các ký tự riêng lẻ trong một chuỗi, đặc biệt là các chuỗi rất lớn.

Tôi đã tự kiểm tra và kết quả của tôi dưới đây. Tuy nhiên có rất nhiều độc giả với kiến ​​thức sâu hơn về trình biên dịch .NET CLR và C# vì vậy tôi không biết nếu tôi thiếu một cái gì đó hiển nhiên, hoặc nếu tôi đã mắc lỗi trong mã thử nghiệm của mình. Vì vậy, tôi thu hút phản ứng tập thể của bạn. Nếu bất cứ ai có cái nhìn sâu sắc vào cách trình chỉ mục chuỗi thực sự hoạt động sẽ rất hữu ích. (Có phải đó là một tính năng ngôn ngữ C# được biên dịch thành một cái gì đó khác đằng sau hậu trường không? Hoặc một cái gì đó được xây dựng trong CLR?).

Phương pháp đầu tiên sử dụng một dòng suối được lấy trực tiếp từ các câu trả lời chấp nhận từ các chủ đề: how to generate a stream from a string?

thử nghiệm

longString là một chuỗi 99.100.000 nhân vật bao gồm 89 bản sao của phiên bản plain-text của đặc tả ngôn ngữ C#. Kết quả được hiển thị cho 20 lần lặp lại. Trường hợp có thời gian 'khởi động' (ví dụ như lần lặp đầu tiên của mảng được tạo ngầm trong phương thứC# 3), tôi đã thử nghiệm riêng biệt, chẳng hạn như bằng cách ngắt khỏi vòng lặp sau lần lặp đầu tiên.

Kết quả

Từ thử nghiệm của tôi, bộ nhớ đệm chuỗi trong một mảng char sử dụng phương pháp ToCharArray() được nhanh nhất cho iterating trên toàn bộ chuỗi. Phương thức ToCharArray() là một chi phí trả trước và quyền truy cập sau đó vào các ký tự riêng lẻ nhanh hơn một chút so với trình truy cập chỉ mục được tích hợp sẵn.

          milliseconds 
           --------------------------------- 
Method       Startup Iteration Total StdDev 
------------------------------ ------- --------- ----- ------ 
1 index accessor      0  602 602  3 
2 explicit convert ToCharArray  165  410 582  3 
3 foreach (c in string.ToCharArray)168  455 623  3 
4 StringReader      0  1150 1150  25 
5 StreamWriter => Stream   405  1940 2345  20 
6 GetBytes() => StreamReader  385  2065 2450  35 
7 GetBytes() => BinaryReader  385  5465 5850  80 
8 foreach (c in string)    0  960 960  4 

Cập nhật: mỗi @ bình luận của Eric, đây là kết quả cho 100 lặp trên một bình thường hơn 1,1 M chuỗi char (một bản sao của C# spec). Indexer và mảng char vẫn còn nhanh nhất, tiếp theo là foreach (char trong chuỗi), tiếp theo là các phương thức stream.

          milliseconds 
           --------------------------------- 
Method       Startup Iteration Total StdDev 
------------------------------ ------- --------- ----- ------ 
1 index accessor      0  6.6 6.6 0.11 
2 explicit convert ToCharArray  2.4  5.0 7.4 0.30 
3 for(c in string.ToCharArray)  2.4  4.7 7.1 0.33 
4 StringReader      0  14.0 14.0 1.21 
5 StreamWriter => Stream   5.3  21.8 27.1 0.46 
6 GetBytes() => StreamReader  4.4  23.6 28.0 0.65 
7 GetBytes() => BinaryReader  5.0  61.8 66.8 0.79 
8 foreach (c in string)    0  10.3 10.3 0.11  

Mã sử ​​dụng (thử nghiệm riêng rẽ; hiển thị cùng cho ngắn gọn)

//1 index accessor 
int strLength = longString.Length; 
for (int i = 0; i < strLength; i++) { c = longString[i]; } 

//2 explicit convert ToCharArray 
int strLength = longString.Length; 
char[] charArray = longString.ToCharArray(); 
for (int i = 0; i < strLength; i++) { c = charArray[i]; } 

//3 for(c in string.ToCharArray) 
foreach (char c in longString.ToCharArray()) { } 

//4 use StringReader 
int strLength = longString.Length; 
StringReader sr = new StringReader(longString); 
for (int i = 0; i < strLength; i++) { c = Convert.ToChar(sr.Read()); } 

//5 StreamWriter => StreamReader 
int strLength = longString.Length; 
MemoryStream stream = new MemoryStream(); 
StreamWriter writer = new StreamWriter(stream); 
writer.Write(longString); 
writer.Flush(); 
stream.Position = 0; 
StreamReader str = new StreamReader(stream); 
while (stream.Position < strLength) { c = Convert.ToChar(str.Read()); } 

//6 GetBytes() => StreamReader 
int strLength = longString.Length; 
MemoryStream stream = new MemoryStream(Encoding.Unicode.GetBytes(longString)); 
StreamReader str = new StreamReader(stream); 
while (stream.Position < strLength) { c = Convert.ToChar(str.Read()); } 

//7 GetBytes() => BinaryReader 
int strLength = longString.Length; 
MemoryStream stream = new MemoryStream(Encoding.Unicode.GetBytes(longString)); 
BinaryReader br = new BinaryReader(stream, Encoding.Unicode); 
while (stream.Position < strLength) { c = br.ReadChar(); } 

//8 foreach (c in string) 
foreach (char c in longString) { } 

câu trả lời chấp nhận:

Tôi giải thích @CodeInChaos và ghi chú Ben như sau:

fixed (char* pString = longString) { 
    char* pChar = pString; 
    for (int i = 0; i < strLength; i++) { 
     c = *pChar ; 
     pChar++; 
    } 
} 

Thực hiện 100 lần lặp lại trong ngắn hạn chuỗi là 4,4 ms, với < 0,1 ms st dev.

Answer 1

Câu trả lời nhanh nhất là sử dụng C++/CLI: How to: Access Characters in a System::String

Cách tiếp cận này lặp thông qua các nhân vật tại chỗ trong chuỗi sử dụng con trỏ số học . Không có bản sao, không có kiểm tra phạm vi ngầm, và không có cuộc gọi chức năng cho mỗi phần tử.

Có khả năng có thể nhận được (gần, C++/CLI không yêu cầu ghim) hiệu suất tương tự từ C# bằng cách viết phiên bản C# không an toàn của PtrToStringChars.

Cái gì như:

unsafe char* PtrToStringContent(string s, out GCHandle pin) 
{ 
    pin = GCHandle.Alloc(s, GCHandleType.Pinned); 
    return (char*)pin.AddrOfPinnedObject().Add(System.Runtime.CompilerServices.RuntimeHelpers.OffsetToStringData).ToPointer(); 
} 

Đừng nhớ để gọi GCHandle.Free sau đó.

bình luận CodeInChaos của chỉ ra rằng C# cung cấp một đường cú pháp cho việc này:

fixed(char* pch = s) { ... } 

Answer 2

Bất kỳ lý do nào không bao gồm foreach?

foreach (char c in text) 
{ 
    ... 
} 

Đây có phải là thực sự sẽ cổ chai hiệu suất của bạn, bằng cách này? Tỷ lệ phần trăm tổng thời gian chạy của bạn là gì?

Answer 3

Nếu tốc độ thực sự quan trọng for nhanh hơn foreach

for (int i = 0; i < text.Length; i++) { 
    char ch = text[i]; 
    ... 
} 

Answer 4

Những loại xét nghiệm nhân tạo là khá nguy hiểm. Đáng chú ý là các phiên bản // 2 và // 3 của bạn không bao giờ thực sự lập chỉ mục chuỗi. Trình tối ưu hóa jitter chỉ ném mã ra vì biến c không được sử dụng chút nào. Bạn chỉ cần đo vòng lặp for() mất bao lâu. Bạn thực sự không thể thấy điều này trừ khi bạn nhìn vào mã máy được tạo ra.

Thay đổi thành c += longString[i]; để buộc trình chỉ mục mảng được sử dụng.

Điều vô nghĩa là tất nhiên. Chỉ hồ sơ thực mã.

Answer 5

Nếu tối ưu hóa vi mô rất quan trọng đối với bạn, hãy thử điều này. (Tôi giả định chiều dài chuỗi đầu vào để là bội số của 8 vì đơn giản)

unsafe void LoopString() 
{ 
    fixed (char* p = longString) 
    { 
     char c1,c2,c3,c4; 
     Int64 len = longString.Length; 
     Int64* lptr = (Int64*)p; 
     Int64 l; 
     for (int i = 0; i < len; i+=8) 
     { 
      l = *lptr; 
      c1 = (char)(l & 0xffff); 
      c2 = (char)(l >> 16); 
      c3 = (char)(l >> 32); 
      c4 = (char)(l >> 48); 
      lptr++; 
     } 
    } 
} 

Just kidding, không bao giờ sử dụng mã này :)

Answer 6

TL; DR: một đơn giản foreach là cách nhanh nhất để lặp một chuỗi .

Đối với những người quay lại điều này: lần thay đổi!

Với JIT .NET 64 bit mới nhất, phiên bản không an toàn thực sự là chậm nhất.

Dưới đây là triển khai điểm chuẩn cho BenchmarkDotNet. Từ những điều này, tôi nhận được các kết quả sau:

  Method |  Mean |  Error | StdDev | 
---------------- |----------:|----------:|----------:| 
     Indexing | 5.9712 us | 0.8738 us | 0.3116 us | 
IndexingOnArray | 8.2907 us | 0.8208 us | 0.2927 us | 
    ForEachOnArray | 8.1919 us | 0.6505 us | 0.1690 us | 
     ForEach | 5.6946 us | 0.0648 us | 0.0231 us | 
      Unsafe | 7.2952 us | 1.1050 us | 0.3941 us | 

Những điều thú vị là bản sao không hoạt động trên bản sao mảng.Điều này cho thấy việc lập chỉ mục và foreach có hiệu suất rất giống nhau, với chênh lệch 5%, foreach là nhanh hơn. Sử dụng unsafe thực sự chậm hơn 28% so với sử dụng foreach.

Trong quá khứ unsafe có thể là tùy chọn nhanh nhất, nhưng JIT sẽ nhanh hơn và thông minh hơn mọi lúc.

Như một tham chiếu, các mã chuẩn:

using System; 
using System.Collections.Generic; 
using System.Linq; 
using System.Text; 
using System.Threading.Tasks; 
using BenchmarkDotNet.Attributes; 
using BenchmarkDotNet.Configs; 
using BenchmarkDotNet.Horology; 
using BenchmarkDotNet.Jobs; 
using BenchmarkDotNet.Running; 

namespace StringIterationBenchmark 
{ 
    public class StringIteration 
    { 
     public static void Main(string[] args) 
     { 
      var config = new ManualConfig(); 

      config.Add(DefaultConfig.Instance); 

      config.Add(Job.Default 
       .WithLaunchCount(1) 
       .WithIterationTime(TimeInterval.FromMilliseconds(500)) 
       .WithWarmupCount(3) 
       .WithTargetCount(6) 
      ); 

      BenchmarkRunner.Run<StringIteration>(config); 
     } 

     private readonly string _longString = BuildLongString(); 

     private static string BuildLongString() 
     { 
      var sb = new StringBuilder(); 
      var random = new Random(); 

      while (sb.Length < 10000) 
      { 
       char c = (char)random.Next(char.MaxValue); 
       if (!Char.IsControl(c)) 
        sb.Append(c); 
      } 

      return sb.ToString(); 
     } 

     [Benchmark] 
     public char Indexing() 
     { 
      char c = '\0'; 
      var longString = _longString; 
      int strLength = longString.Length; 

      for (int i = 0; i < strLength; i++) 
      { 
       c |= longString[i]; 
      } 

      return c; 
     } 

     [Benchmark] 
     public char IndexingOnArray() 
     { 
      char c = '\0'; 
      var longString = _longString; 
      int strLength = longString.Length; 
      char[] charArray = longString.ToCharArray(); 

      for (int i = 0; i < strLength; i++) 
      { 
       c |= charArray[i]; 
      } 

      return c; 
     } 

     [Benchmark] 
     public char ForEachOnArray() 
     { 
      char c = '\0'; 
      var longString = _longString; 

      foreach (char item in longString.ToCharArray()) 
      { 
       c |= item; 
      } 

      return c; 
     } 

     [Benchmark] 
     public char ForEach() 
     { 
      char c = '\0'; 
      var longString = _longString; 

      foreach (char item in longString) 
      { 
       c |= item; 
      } 

      return c; 
     } 

     [Benchmark] 
     public unsafe char Unsafe() 
     { 
      char c = '\0'; 
      var longString = _longString; 
      int strLength = longString.Length; 

      fixed (char* p = longString) 
      { 
       var p1 = p; 

       for (int i = 0; i < strLength; i++) 
       { 
        c |= *p1; 
        p1++; 
       } 
      } 

      return c; 
     } 
    } 
} 

Mã này có một vài thay đổi nhỏ từ mã được cung cấp. Các ký tự được lấy từ chuỗi gốc là | -ed với biến được trả về và chúng tôi trả về giá trị. Lý do cho điều này là chúng ta thực sự cần phải làm điều gì đó với kết quả. Nếu không, nếu chúng tôi chỉ lặp qua chuỗi như sau:

//8 foreach (c in string) 
foreach (char c in longString) { } 

JIT là miễn phí để loại bỏ điều này vì nó có thể suy ra rằng bạn không thực sự quan sát kết quả của lần lặp lại. Bằng cách | -ing các ký tự trong mảng và trả về điều này, BenchmarkDotNet sẽ đảm bảo rằng JIT không thể thực hiện tối ưu hóa này.