Kiểm tra xem một chuỗi có chứa một phần tử từ một danh sách (các chuỗi)

Question

Đối với khối mã sau đây:

For I = 0 To listOfStrings.Count - 1 
    If myString.Contains(lstOfStrings.Item(I)) Then 
     Return True 
    End If 
Next 
Return False 

Đầu ra là:

Trường hợp 1:

myString: C:\Files\myfile.doc 
listOfString: C:\Files\, C:\Files2\ 
Result: True 

Trường hợp 2:

myString: C:\Files3\myfile.doc 
listOfString: C:\Files\, C:\Files2\ 
Result: False 

Danh sách (listOfStrings) có thể chứa nhiều mục (tối thiểu 20) và nó phải được kiểm tra với hàng nghìn chuỗi (như myString).

Có cách nào tốt hơn (hiệu quả hơn) để viết mã này không?

Answer 1

Với LINQ, và sử dụng C# (Tôi không biết VB nhiều những ngày này):

bool b = listOfStrings.Any(s=>myString.Contains(s)); 

hoặc (ngắn hơn và hiệu quả hơn, nhưng cho là chưa rõ ràng):

bool b = listOfStrings.Any(myString.Contains); 

Nếu bạn đã thử nghiệm bình đẳng, nó sẽ có giá trị nhìn vào HashSet vv, nhưng điều này sẽ không giúp đỡ với một phần trận đấu trừ khi bạn chia thành các mảnh và thêm một trật tự phức tạp.

---

cập nhật: nếu bạn thực sự có nghĩa là "StartsWith", thì bạn có thể sắp xếp danh sách và đặt nó vào một mảng; sau đó sử dụng Array.BinarySearch để tìm từng mục - kiểm tra bằng cách tra cứu để xem đó có phải là một kết hợp toàn bộ hoặc một phần hay không.

Answer 2

Tôi không chắc liệu nó có hiệu quả hơn hay không, nhưng bạn có thể nghĩ đến việc sử dụng tại Lambda Expressions.

Answer 3

Có một số đề xuất từ ​​một câu hỏi tương tự trước đó "Best way to test for existing string against a large list of comparables".

Regex có thể đủ cho yêu cầu của bạn. Biểu thức sẽ là một kết nối của tất cả các phần tử ứng cử viên, với toán tử OR "|" giữa chúng. Tất nhiên, bạn sẽ phải theo dõi các ký tự không thoát khi xây dựng biểu thức hoặc không thể biên dịch nó do các giới hạn về kích thước hoặc độ phức tạp.

Một cách khác để thực hiện điều này là xây dựng một trie data structure để biểu diễn tất cả các phần tử ứng cử viên (điều này có thể trùng lặp với những gì mà trình phù hợp regex đang làm). Khi bạn bước qua từng ký tự trong chuỗi thử nghiệm, bạn sẽ tạo một con trỏ mới vào thư mục gốc của trie, và chuyển các con trỏ hiện có tới con thích hợp (nếu có). Bạn nhận được một trận đấu khi bất kỳ con trỏ nào đến một chiếc lá.

Answer 4

Dựa trên các mẫu của bạn, một cải tiến sẽ thay đổi để sử dụng StartsWith thay vì Chứa. StartsWith chỉ cần lặp qua từng chuỗi cho đến khi nó tìm thấy sự không phù hợp đầu tiên thay vì phải khởi động lại tìm kiếm ở mọi vị trí ký tự khi tìm thấy nó.

Ngoài ra, dựa trên mẫu của bạn, có vẻ như bạn có thể trích xuất phần đầu tiên của đường dẫn cho myString, sau đó đảo ngược so sánh - tìm đường dẫn khởi tạo của myString trong danh sách chuỗi thay vì cách khác xung quanh.

string[] pathComponents = myString.Split(Path.DirectorySeparatorChar); 
string startPath = pathComponents[0] + Path.DirectorySeparatorChar; 

return listOfStrings.Contains(startPath); 

EDIT: Đây sẽ là thậm chí nhanh hơn bằng cách sử dụng ý tưởng HashSet @Marc Gravell đề cập kể từ khi bạn có thể thay đổi Contains-ContainsKey và tra cứu sẽ là O (1) thay vì O (N). Bạn sẽ phải đảm bảo rằng các đường dẫn khớp chính xác. Lưu ý rằng đây không phải là một giải pháp chung như là @Marc Gravell nhưng được thiết kế riêng cho các ví dụ của bạn.

Xin lỗi ví dụ C#. Tôi không có đủ cà phê để dịch sang VB.

Answer 5

Nếu tốc độ rất quan trọng, bạn có thể muốn tìm kiếm Aho-Corasick algorithm cho các bộ mẫu.

Đó là trie có liên kết lỗi, nghĩa là độ phức tạp là O (n + m + k), trong đó n là độ dài của văn bản đầu vào, m độ dài tích lũy của mẫu và k số kết quả phù hợp. Bạn chỉ cần sửa đổi thuật toán để chấm dứt sau khi kết quả khớp đầu tiên được tìm thấy.

Answer 6

Bạn đã kiểm tra tốc độ chưa?

tức là bạn đã tạo một nhóm dữ liệu mẫu và đã định cấu hình chưa? Nó có thể không tệ như bạn nghĩ.

Điều này cũng có thể là thứ bạn có thể sinh ra thành một sợi riêng biệt và mang đến ảo tưởng về tốc độ!

Answer 7

myList.Any(myString.Contains); 

Answer 8

Tôi thích câu trả lời của Marc, nhưng cần có Chứa phù hợp để là CaSe InSenSiTiVe.

Đây là giải pháp:

bool b = listOfStrings.Any(s => myString.IndexOf(s, StringComparison.OrdinalIgnoreCase) >= 0)) 

Answer 9

khi bạn xây dựng của bạn Strings nó phải như thế này

bool inact = new string[] { "SUSPENDARE", "DIZOLVARE" }.Any(s=>stare.Contains(s));