Hiệu suất LINQ cho Bộ sưu tập Lớn

Question

Tôi có một bộ sưu tập lớn các chuỗi (tối đa 1M) được sắp xếp theo thứ tự bảng chữ cái. Tôi đã thử nghiệm với các truy vấn LINQ đối với bộ sưu tập này bằng cách sử dụng HashSet, SortedDictionary và Dictionary. Tôi đang lưu trữ bộ nhớ cache tĩnh, kích thước lên tới 50MB và tôi luôn gọi truy vấn LINQ đối với bộ sưu tập được lưu trong bộ nhớ cache. Vấn đề của tôi là như sau:

Bất kể loại bộ sưu tập nào, hiệu suất kém hơn nhiều so với SQL (tối đa 200ms). Khi thực hiện một truy vấn tương tự với các bảng SQL nằm bên dưới, hiệu suất sẽ nhanh hơn nhiều (5-10ms). Tôi đã triển khai các truy vấn LINQ của mình như sau:

public static string ReturnSomething(string query, int limit) 
{ 
    StringBuilder sb = new StringBuilder(); 
    foreach (var stringitem in MyCollection.Where(
     x => x.StartsWith(query) && x.Length > q.Length).Take(limit)) 
    { 
     sb.Append(stringitem); 
    } 

    return sb.ToString(); 
} 

Tôi hiểu rằng HashSet, Dictionary, etc. thực hiện tra cứu bằng cách sử dụng tìm kiếm cây nhị phân thay vì liệt kê tiêu chuẩn. Các tùy chọn của tôi cho các truy vấn LINQ hiệu năng cao vào các loại bộ sưu tập nâng cao là gì?

Answer 1

Trong mã hiện tại của bạn, bạn không sử dụng bất kỳ trong những tính năng đặc biệt của Dictionary/SortedDictionary/HashSet bộ sưu tập, bạn đang sử dụng chúng cùng một cách mà bạn sẽ sử dụng một List. Đó là lý do tại sao bạn không thấy bất kỳ sự khác biệt nào về hiệu suất.

Nếu bạn sử dụng từ điển làm chỉ mục trong đó vài ký tự đầu tiên của chuỗi là khóa và danh sách chuỗi là giá trị, bạn có thể từ chuỗi tìm kiếm chọn một phần nhỏ của toàn bộ chuỗi các trận đấu có thể.

Tôi đã viết lớp bên dưới để kiểm tra điều này. Nếu tôi cư trú nó với một triệu chuỗi và tìm kiếm với một chuỗi tám ký tự nó sẽ lướt qua tất cả các kết quả phù hợp có thể trong khoảng 3 ms. Tìm kiếm bằng một chuỗi ký tự là trường hợp xấu nhất, nhưng nó tìm thấy 1000 kết quả đầu tiên trong khoảng 4 ms. Tìm tất cả các kết quả phù hợp cho một chuỗi ký tự mất khoảng 25 ms.

Lớp tạo chỉ mục cho các phím ký tự 1, 2, 4 và 8. Nếu bạn xem dữ liệu cụ thể của bạn và những gì bạn tìm kiếm, bạn sẽ có thể chọn các chỉ mục để tạo để tối ưu hóa nó cho các điều kiện của bạn.

public class IndexedList { 

    private class Index : Dictionary<string, List<string>> { 

     private int _indexLength; 

     public Index(int indexLength) { 
      _indexLength = indexLength; 
     } 

     public void Add(string value) { 
      if (value.Length >= _indexLength) { 
       string key = value.Substring(0, _indexLength); 
       List<string> list; 
       if (!this.TryGetValue(key, out list)) { 
        Add(key, list = new List<string>()); 
       } 
       list.Add(value); 
      } 
     } 

     public IEnumerable<string> Find(string query, int limit) { 
      return 
       this[query.Substring(0, _indexLength)] 
       .Where(s => s.Length > query.Length && s.StartsWith(query)) 
       .Take(limit); 
     } 

    } 

    private Index _index1; 
    private Index _index2; 
    private Index _index4; 
    private Index _index8; 

    public IndexedList(IEnumerable<string> values) { 
     _index1 = new Index(1); 
     _index2 = new Index(2); 
     _index4 = new Index(4); 
     _index8 = new Index(8); 
     foreach (string value in values) { 
      _index1.Add(value); 
      _index2.Add(value); 
      _index4.Add(value); 
      _index8.Add(value); 
     } 
    } 

    public IEnumerable<string> Find(string query, int limit) { 
     if (query.Length >= 8) return _index8.Find(query, limit); 
     if (query.Length >= 4) return _index4.Find(query,limit); 
     if (query.Length >= 2) return _index2.Find(query,limit); 
     return _index1.Find(query, limit); 
    } 

} 

Answer 2

Nếu bạn đang thực hiện "bắt đầu với", bạn chỉ quan tâm đến các so sánh thứ tự và bạn có thể sắp xếp bộ sưu tập (thứ tự theo thứ tự) sau đó tôi đề nghị bạn có các giá trị trong danh sách. Sau đó bạn có thể tìm kiếm nhị phân để tìm giá trị đầu tiên bắt đầu bằng tiền tố thích hợp, sau đó đi xuống danh sách kết quả tuyến tính cho đến khi giá trị đầu tiên mà không bắt đầu bằng tiền tố phù hợp.

Thực tế, bạn có thể thực hiện tìm kiếm nhị phân khác cho giá trị đầu tiên không bắt đầu bằng tiền tố, vì vậy bạn có điểm bắt đầu và điểm kết thúc. Sau đó, bạn chỉ cần áp dụng tiêu chí độ dài cho phần phù hợp đó. (Tôi hy vọng rằng nếu đó là dữ liệu hợp lý, kết hợp tiền tố sẽ loại bỏ hầu hết các giá trị ứng cử viên.) Cách để tìm giá trị đầu tiên không bắt đầu bằng tiền tố là tìm kiếm giá trị đầu tiên theo từ điển không - ví dụ với tiền tố "ABC", tìm kiếm "ABD".

Không điều nào trong số này sử dụng LINQ và tất cả đều rất cụ thể đối với trường hợp cụ thể của bạn, nhưng nó sẽ hoạt động. Hãy cho tôi biết nếu bất kỳ điều này không có ý nghĩa.

Answer 3

Chỉ cần nhìn vào mã của bạn, tôi sẽ nói rằng bạn nên sắp xếp lại việc so sánh để tận dụng lợi thế của đoản mạch khi sử dụng các toán tử logic:

foreach (var stringitem in MyCollection.Where(
    x => x.Length > q.Length && x.StartsWith(query)).Take(limit)) 

Việc so sánh chiều dài luôn luôn sẽ là một O (1) hoạt động (như chiều dài đang được lưu trữ như là một phần của chuỗi, nó không tính mỗi nhân vật mỗi lần), trong khi cuộc gọi đến StartsWith sẽ là một hoạt động O (N), trong đó N là độ dài của truy vấn (hoặc chiều dài của chuỗi, tùy theo cái nào nhỏ hơn).

Bằng cách đặt so sánh độ dài trước khi cuộc gọi đến StartsWith, nếu so sánh đó thất bại, bạn tiết kiệm cho mình một số chu kỳ bổ sung có thể tăng lên khi xử lý số lượng lớn các mục.

Tôi không nghĩ rằng bảng tra cứu sẽ giúp bạn ở đây, vì bảng tra cứu rất tốt khi bạn so sánh toàn bộ khóa chứ không phải các phần của khóa, như bạn đang thực hiện với lệnh gọi StartsWith.

Thay vào đó, bạn có thể nên sử dụng cấu trúc cây được chia nhỏ dựa trên các chữ cái trong các từ trong danh sách.

Tuy nhiên, tại thời điểm đó, bạn đang thực sự chỉ tái tạo những gì SQL Server đang làm (trong trường hợp chỉ mục) và đó sẽ chỉ là một bản sao của nỗ lực từ phía bạn.

Answer 4

Tôi đặt cược bạn có chỉ mục trên cột để máy chủ SQL có thể thực hiện so sánh trong các hoạt động O (log (n)) thay vì O (n).Để bắt chước hành vi của máy chủ SQL, hãy sử dụng một bộ sưu tập được sắp xếp và tìm tất cả các chuỗi sao cho s> = truy vấn và sau đó xem xét các giá trị cho đến khi bạn tìm thấy một giá trị không bắt đầu bằng s và sau đó thực hiện một bộ lọc bổ sung trên các giá trị. Đây được gọi là quét phạm vi (Oracle) hoặc tìm kiếm chỉ mục (máy chủ SQL).

Đây là một số mã ví dụ rất có khả năng đi vào vòng lặp vô hạn hoặc có lỗi một lần vì tôi đã không kiểm tra nó, nhưng bạn nên có ý tưởng.

// Note, list must be sorted before being passed to this function 
IEnumerable<string> FindStringsThatStartWith(List<string> list, string query) { 
    int low = 0, high = list.Count - 1; 
    while (high > low) { 
     int mid = (low + high)/2; 
     if (list[mid] < query) 
      low = mid + 1; 
     else 
      high = mid - 1; 
    } 

    while (low < list.Count && list[low].StartsWith(query) && list[low].Length > query.Length) 
     yield return list[low]; 
     low++; 
    } 
} 

Answer 5

Nếu bạn đang cố gắng để tối ưu hóa tìm kiếm một danh sách các chuỗi với một tiền tố cho bạn có thể muốn xem xét việc thực hiện một Trie (không bị nhầm lẫn với một tree thường xuyên) cấu trúc dữ liệu trong C#.

Các thử nghiệm cung cấp tra cứu tiền tố rất nhanh và có chi phí bộ nhớ rất nhỏ so với các cấu trúc dữ liệu khác cho loại thao tác này.

Giới thiệu LINQ to Objects nói chung. Nó không phải là bất thường để có một giảm tốc độ so với SQL. Mạng là littered with articles phân tích hiệu suất của nó.

Answer 6

Tôi nghĩ rằng vấn đề là Linq không có cách nào để sử dụng thực tế là trình tự của bạn đã được sắp xếp. Đặc biệt là nó không thể biết, rằng việc áp dụng các chức năng StartsWith giữ lại thứ tự.

Tôi khuyên bạn nên sử dụng phương pháp List.BinarySearch cùng với IComparer<string> mà chỉ so sánh các ký tự truy vấn đầu tiên (điều này có thể khó, vì không rõ ràng, nếu chuỗi truy vấn sẽ luôn là tham số đầu tiên hoặc thứ hai ()).

Bạn thậm chí có thể sử dụng so sánh chuỗi chuẩn, vì BinarySearch trả về số âm mà bạn có thể bổ sung (sử dụng ~) để lấy chỉ mục của phần tử đầu tiên lớn hơn truy vấn của bạn.

Sau đó, bạn phải bắt đầu từ chỉ mục trả về (theo cả hai hướng!) Để tìm tất cả các phần tử phù hợp với chuỗi truy vấn của bạn.