Kết hợp chuỗi tốc độ cao trong C#

Question

Tôi có danh sách khoảng 10.000 nhân viên trong một List<T> và tôi có một số ListBox chứa một tập con của những nhân viên đó, tùy thuộc vào cụm từ tìm kiếm trong hộp văn bản.

Nói một đối tượng Staff có các tính chất tiếp xúc công khai sau đây:

string FirstName 
string LastName 
string MiddleName 
    int StaffID 
    int CostCentre 

tôi có thể viết một hàm như thế này:

bool staffMatchesSearch(Staff stf) 
{ 
    if (tbSrch.Text.Trim() == string.Empty) 
    return true; // No search = match always. 

    string s = tbSrch.Text.Trim().ToLower(); 

    // Do the checks in the order most likely to return soonest: 
    if (stf.LastName.ToLower().Contains(s)) 
    return true; 
    if (stf.FirstName.ToLower().Contains(s)) 
    return true; 
    if (stf.MiddleName.ToLower().Contains(s)) 
    return true; 

    if (stf.CostCentre.ToString().Contains(s)) 
    return true; // Yes, we want partial matches on CostCentre 
    if (stf.StaffID.ToString().Contains(s)) 
    return true; // And also on StaffID 

    return false; 
} 

và sau đó làm điều gì đó như:

tbSrch_TextChanged(object sender, EventArgs e) 
{ 
    lbStaff.BeginUpdate(); 
    lbStaff.Items.Clear(); 

    foreach (Staff stf in staff) 
    if (staffMatchesSearch(stf)) 
     lbStaff.Items.Add(stf); 

    lbStaff.EndUpdate(); 
} 

Bộ lọc được đánh giá lại mỗi khi người dùng thay đổi nội dung của ô tbSrch.

Làm việc này và không phải là awfully chậm, nhưng tôi đã tự hỏi liệu mình có thể làm nhanh hơn không?

Tôi đã cố gắng viết lại toàn bộ nội dung là đa luồng, tuy nhiên chỉ có 10.000 nhân viên ở trên cao dường như lấy đi phần lớn lợi ích. Ngoài ra, có một loạt các lỗi khác như tìm kiếm "John", trước tiên người dùng nhấn "J" để cuộn lên các chuỗi, nhưng khi người dùng nhấn "o", một bộ khác sẽ được đặt lên trước khi lô đầu tiên có một cơ hội để trả lại kết quả của họ. Rất nhiều thời gian, kết quả được trả lại trong một trật tự lộn xộn và tất cả những điều khó chịu xảy ra.

Tôi có thể nghĩ đến một vài chỉnh sửa sẽ làm cho kịch bản tốt nhất tốt hơn đáng kể, nhưng chúng cũng sẽ khiến kịch bản xấu nhất tồi tệ hơn nhiều.

Bạn có ý tưởng nào về cách cải thiện điều này không?

---

gợi ý tuyệt vời tôi đã thực hiện đến nay, và kết quả của họ:

• Thêm một sự chậm trễ trên các sự kiện ValueChanged do đó nếu người dùng gõ một tên 5 ký tự một cách nhanh chóng trên bàn phím, nó chỉ thực hiện 1 tìm kiếm ở cuối thay vì 5 trong chuỗi.
• Đánh giá trước ToLower() và lưu trữ trong lớp Staff (dưới dạng thuộc tính [NonSerialized] để nó không chiếm nhiều không gian hơn trong tệp lưu).
• Thêm một tài sản get trong Staff trả về tất cả các tiêu chí tìm kiếm dưới dạng chuỗi đơn, dài, thấp hơn, được nối. Sau đó chạy một đơn Contains() trên đó. (String này được lưu trữ trong đối tượng Staff vì vậy nó chỉ được xây dựng một lần.)

Cho đến nay, những điều này đã làm giảm thời gian tìm kiếm từ khắp nơi trên 140ms xuống còn khoảng 60ms (mặc dù những con số này rất chủ quan tùy thuộc vào việc tìm kiếm thực tế thực hiện và số lượng kết quả được trả lại).

Answer 1

1) như chỉ ra trong các ý kiến, có lẽ bạn không nên ToString các trường số - chỉ phù hợp với những con số

2) các cuộc gọi ToLower là một cống về hiệu suất.Thêm phiên bản thấp hơn của các thuộc tính này vào lớp Staff để ToLower chỉ phải được thực hiện sau khi

3) khi người dùng nhập một ký tự khác, bạn không cần đánh giá lại tất cả mục. việc nhập một ký tự sẽ chỉ giảm số lượng các kết quả phù hợp để chỉ đánh giá lại các trận đấu trước đó.

4) sử dụng bộ hẹn giờ để giới thiệu độ trễ giữa thời điểm người dùng nhập và khi bạn bắt đầu tìm kiếm. nếu họ đang nhập nhiều ký tự một cách nhanh chóng, bạn cũng có thể đợi cho đến khi chúng bị tạm dừng trong nửa giây

5) Kiểm tra phím đã được nhấn. Nếu NaN sau đó không kiểm tra các thuộc tính int.

Answer 2

Bạn có thể thêm thuộc tính riêng tư 'SearchTerm' vào đối tượng Staff là (FirstName + LastName + MiddleName + StaffID + CostCentre).ToLower() và thay vào đó hãy thực hiện kiểm tra Contains(). Điều này sẽ ngăn chặn bạn phải làm một ToLower() trên mỗi chuỗi mỗi lần và giảm số lượng các Contains() kiểm tra từ 5 đến 1.

Answer 3

Bạn có thể thử thực hiện một hay "tiền tố cây" trie:

http://en.wikipedia.org/wiki/Trie

Điều này sẽ cho phép bạn tìm kiếm văn bản bắt đầu với giá trị.

Tôi tin rằng bài viết được liên kết trên suffix-trees sẽ cho phép bạn thực hiện tìm kiếm văn bản đầy đủ, mặc dù nó có yêu cầu bộ nhớ cao hơn.

Đảm bảo rằng bạn ToLower tất cả dữ liệu của bạn khi chèn nó vào cấu trúc của bạn để bạn không phải thực hiện các so sánh không phân biệt chữ hoa chữ thường khi thực hiện tra cứu.

Answer 4

Khi nhìn thấy những gì bạn đã làm (chủ yếu là từ nhận xét về câu trả lời của @ mikel), có vẻ như bạn đang đến đó. Một gợi ý tôi chưa từng thấy có thể làm tăng tốc độ là so sánh sử dụng StringComparison.OrdinalIgnoreCase. Trong trường hợp của bạn, nó sẽ có nghĩa thay thế

if (stf.LastName.ToLower().Contains(s)) 
    return true; 

với

if (stf.LastName.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0) 
    return true; 

Dưới đây là một MSDN link, thảo luận so sánh chuỗi nhanh.

Answer 5

using System; 
using System.Text.RegularExpressions; 
namespace PatternMatching1 
{ 
    class Program 
    { 
     static void Main(string[] args) 
     { 
      try 
      { 
       Console.WriteLine("Please enter the first string."); 
       string str = Console.ReadLine(); ; 
       string replacestr = Regex.Replace(str, "[^a-zA-Z0-9_]+", " "); 



       Console.WriteLine("Please enter the second string."); 
       string str1 = Console.ReadLine(); ; 
       string replacestr1 = Regex.Replace(str1, "[^a-zA-Z0-9_]+", " "); 



       if (replacestr.Length == replacestr1.Length) 
       { 
        char[] cFirst = replacestr.ToLower().ToCharArray(); 
        char[] cSecond = replacestr1.ToLower().ToCharArray(); 

        Array.Sort<char>(cFirst); 
        Array.Sort<char>(cSecond); 

        if ((new string(cFirst)).Equals((new string(cSecond)))) 
         Console.WriteLine("Both String Same"); 
        else 
         Console.WriteLine("Both String Not Same"); 
       } 
       else 
        Console.WriteLine("oopsss, something going wrong !!!! try again"); 
      } 
      catch (Exception ex) 
      { 
       Console.WriteLine(ex.Message); 
      } 
      Console.Read(); 
     } 
    } 
} 

'