Làm thế nào có thể C# 's string.IndexOf thực hiện quá nhanh, 10 lần nhanh hơn bình thường cho vòng tìm?

Question

Tôi có một chuỗi rất dài (60MB về kích thước), trong đó tôi cần tìm xem có bao nhiêu cặp '<' và '>' nằm trong đó.

---

Tôi đã cố gắng đầu tiên theo cách riêng của tôi:

 char pre = '!'; 
     int match1 = 0; 
     for (int j = 0; j < html.Length; j++) 
     { 
      char c = html[j]; 
      if (pre == '<' && c == '>') //find a match 
      { 
       pre = '!'; 
       match1++; 
      } 
      else if (pre == '!' && c == '<') 
       pre = '<'; 
     } 

Đoạn mã trên chạy trên chuỗi của tôi cho khoảng 1000 ms.

---

Sau đó, tôi cố gắng sử dụng string.IndexOf

 int match2 = 0; 
     int index = -1; 
     do 
     { 
      index = html.IndexOf('<', index + 1); 
      if (index != -1) // find a match 
      { 
       index = html.IndexOf('>', index + 1); 
       if (index != -1) 
        match2++; 
      } 
     } while (index != -1); 

Đoạn mã trên chạy chỉ khoảng 150 ms.

---

tôi tự hỏi sự kỳ diệu mà làm cho string.IndexOf chạy quá nhanh là gì?

Mọi người đều có thể truyền cảm hứng cho tôi?

---

Sửa

Ok, theo câu trả lời @ BrokenGlass của. Tôi sửa đổi mã của tôi theo cách mà họ không kiểm tra các cặp, thay vào đó, họ kiểm tra có bao nhiêu '<' trong chuỗi.

---

 for (int j = 0; j < html.Length; j++) 
     { 
      char c = html[j]; 
      if (c == '>') 
      { 
       match1++; 
      } 
     } 

mã trên chạy với giá khoảng 760 ms .

---

Sử dụng IndexOf

 int index = -1; 
     do 
     { 
      index = html.IndexOf('<', index + 1); 
      if (index != -1) 
      { 
       match2++; 
      } 
     } while (index != -1); 

Đoạn mã trên chạy trong khoảng 132 ms. vẫn rất nhanh.

---

Chỉnh sửa 2

Sau khi đọc @Jeffrey Sax bình luận, tôi nhận ra rằng tôi đã chạy trong VS với chế độ Debug.

Sau đó, tôi đã tạo và chạy ở chế độ phát hành, ok, IndexOf vẫn nhanh hơn nhưng không nhanh hơn nữa.

Dưới đây là kết quả:

Đối với số lượng cặp đôi: 207ms 144ms VS

Đối với đếm một char bình thường: 141ms 111ms VS.

Hiệu suất của mã của riêng tôi đã thực sự được cải thiện.

---

Bài học kinh nghiệm: khi bạn làm công cụ chuẩn, hãy thực hiện ở chế độ phát hành!

Answer 1

Bạn có đang chạy thời gian của mình từ trong Visual Studio không? Nếu vậy, mã của bạn sẽ chạy chậm hơn đáng kể vì lý do đó.

Ngoài ra, bạn ở một mức độ nào đó, so sánh táo và cam. Hai thuật toán hoạt động theo một cách khác.

Các IndexOf khuyết phiên bản giữa tìm kiếm một dấu ngoặc mở chỉ và một khung bế mạc chỉ. Mã của bạn đi qua toàn bộ chuỗi và giữ một cờ trạng thái cho biết nó đang tìm kiếm một dấu mở hay một khung đóng. Điều này đòi hỏi nhiều công việc hơn và dự kiến ​​sẽ chậm hơn.

Dưới đây là một số mã thực hiện so sánh giống như phương pháp IndexOf của bạn.

int match3 = 0; 
for (int j = 0; j < html.Length; j++) { 
    if (html[j] == '<') { 
     for (; j < html.Length; j++) 
      if (html[j] == '>') 
       match3++; 
    } 
} 

Trong các thử nghiệm của tôi đây thực sự là khoảng 3 lần nhanh hơn so với phương pháp IndexOf. Nguyên nhân? Các chuỗi thực sự không đơn giản như các chuỗi ký tự riêng lẻ. Có các điểm đánh dấu, dấu trọng âm, v.v. String.IndexOf xử lý tất cả sự phức tạp thêm một cách đúng đắn, nhưng nó có chi phí.

Answer 2

Tôi mong chờ string.IndexOf so với mẫu mã đầu tiên của bạn chạy ít nhất hai lần càng nhanh (bên cạnh bất kỳ tối ưu hóa khác mà có thể được thực hiện có) kể từ khi bạn kiểm tra cả bắt đầu và kết thúc nhân vật trong mỗi lần lặp của bạn. Thực hiện của bạn với string.IndexOf mặt khác sẽ chỉ kiểm tra ký tự kết thúc sau khi nó đã tìm thấy thành công một ký tự bắt đầu. Điều này cắt giảm số lượng hoạt động trên mỗi lần lặp xuống đáng kể (một ít so sánh).

Answer 3

Điều duy nhất mà nói đến cái tâm của tôi là thực hiện thực tế của IndexOf lớp chuỗi iniside, đó gọi

callvirt System.String.IndexOf 

đó, nếu chúng ta sử dụng một sức mạnh của phản xạ (càng nhiều càng tốt cho nó có thể) kết thúc vào

CompareInfo.IndexOf(..) 

cuộc gọi, mà thay vào đó sử dụng cửa sổ siêu nhanh chức năng có nguồn gốc FindNLSString:

Answer 4

Đó là một chút sai lầm để so sánh trực tiếp việc triển khai được quản lý của bạn và phương pháp String.IndexOf. Việc triển khai IndexOf phần lớn là mã gốc và do đó có một bộ đặc điểm hiệu suất khác với triển khai được quản lý của bạn. Trong mã riêng biệt, tránh kiểm tra an toàn loại và chi phí tương ứng của chúng, được CLR tiêm vào thuật toán được quản lý.

Một ví dụ là việc sử dụng các chỉ số mảng

char c = html[j]; 

Trong mã quản lý tuyên bố này sẽ xác minh rằng cả hai j là một chỉ số có giá trị vào mảng html và sau đó trả về giá trị. Mã nguồn gốc tương đương chỉ đơn giản là trả về một bộ nhớ bù đắp mà không cần kiểm tra bổ sung. Việc thiếu kiểm tra này cung cấp mã nguồn gốc một lợi thế vốn có ở đây vì nó có thể tránh được một lệnh chi nhánh bổ sung trên mỗi lần lặp của vòng lặp.

Lưu ý rằng lợi thế này không tuyệt đối. JIT rất có thể kiểm tra vòng lặp này và quyết định rằng j không bao giờ có thể là một chỉ mục không hợp lệ và bỏ qua các kiểm tra trong mã nguồn gốc được tạo ra (và nó thực hiện điều này trong một số trường hợp IIRC).

Answer 5

Sử dụng câu lệnh chuyển đổi thay vì kiểm tra nếu tốc độ thử nghiệm tăng lên một chút. Mã này đôi khi đánh bại mã chỉ mục trên máy tính của tôi.

 int count = 0; 
     bool open = false; 
     for (int j = 0; j < testStr.Length; j++) 
     { 
      switch (testStr[j]) 
      { 
       case '<': 
        open = true; 
        break; 
       case '>': 
        if (open) 
         count++; 

        open = false; 
        break;   
      } 
     }