Cách nhanh nhất để lọc danh sách các chuỗi khi tạo danh sách Intellisense/Autocomplete là gì?

Question

Tôi đang viết Intellisense/Tự động hoàn thành giống như bạn tìm thấy trong Visual Studio. Tất cả đều ổn cho đến khi danh sách có thể chứa hơn 2000 mục.

Tôi đang sử dụng một tuyên bố LINQ đơn giản để thực hiện việc lọc:

var filterCollection = from s in listCollection 
         where s.FilterValue.IndexOf(currentWord,  
         StringComparison.OrdinalIgnoreCase) >= 0 
         orderby s.FilterValue 
         select s; 

sau đó tôi gán bộ sưu tập này để ItemSource một WPF Listbox, và đó là kết thúc của nó, hoạt động tốt.

Lưu ý rằng, Listbox cũng được ảo hóa, vì vậy sẽ chỉ có tối đa 7-8 yếu tố trực quan trong bộ nhớ và trong cây thị giác. Tuy nhiên, trước khi báo trước là khi người dùng gõ cực nhanh trong richtextbox, và trên mọi khóa, tôi thực thi lọc + ràng buộc, có điều kiện bán chạy này, hoặc lọc đồng bộ, chẳng hạn như lần đầu tiên bộ lọc chính của đột quỵ vẫn có thể thực hiện công việc lọc hoặc ràng buộc của nó, trong khi đột quỵ quan trọng thứ tư cũng làm như vậy.

Tôi biết tôi có thể trì hoãn trước khi áp dụng bộ lọc, nhưng tôi đang cố gắng đạt được một bộ lọc liền mạch giống như bộ lọc trong Visual Studio. Tôi không chắc chắn vấn đề của mình nằm ở đâu, vì vậy tôi cũng gán nó vào hoạt động chuỗi của IndexOf, hoặc có lẽ danh sách chuỗi của tôi có thể được tối ưu hóa trong một số loại chỉ mục, có thể tăng tốc độ tìm kiếm.

Bất kỳ đề xuất nào về mẫu mã đều được hoan nghênh nhiều.

Cảm ơn.

Answer 1

Tôi khuyên bạn nên cố gắng giới hạn kết quả được đặt ở một số mục và xem sự cố có bị mất hay không. Đó là, bạn có thể có 5000 để lựa chọn, nhưng cố gắng trả lại không quá 100, ngay cả khi có nhiều trận đấu hơn. Nói:

var filterCollection = (from s in listCollection 
    where s.FilterValue.IndexOf(currentWord,StringComparison.OrdinalIgnoreCase)>=0 
    orderby s.FilterValue 
    select s).Take(100); 

Nếu sự cố của bạn biến mất, sự chậm lại có thể do quá nhiều mục được trả lại cho hộp danh sách. Tôi không chắc chắn rằng vấn đề sẽ biến mất, kể từ khi ListBox được ảo hóa, nhưng nó có giá trị một shot. Bạn cũng có thể thử điều tương tự nhưng giới hạn kết quả của việc lọc thành 100 mục, trước khi sắp xếp (ví dụ: orderby) và xem điều đó có giúp ích gì không. Đó là hiệu quả hơn để làm điều đó theo thứ tự này, anyways:

var filterCollection = (from s in listCollection 
    where s.FilterValue.IndexOf(currentWord,StringComparison.OrdinalIgnoreCase)>=0 
    select s).Take(100) 
      .OrderBy(s => s.FilterValue); 

Điểm mấu chốt là xác định nếu vấn đề là một chức năng của số lượng các mặt hàng trở lại và giao cho filterColection hoặc chứng nhận số ban đầu của mặt hàng, hoặc cả hai .

Answer 2

Độ trễ không phải là vấn đề của bạn nếu bạn có tập hợp 2000 mục. Tôi đang thực hiện một số giả định lớn ở đây, nhưng bạn chỉ thực sự cần trả lại tối đa 500 mục - người dùng của bạn sẽ tiếp tục nhập để thu hẹp bộ kết quả cho đến khi nó là kích thước có thể chấp nhận được để duyệt qua.

Bạn nên tối ưu hóa trường hợp thông thường (giả sử nó sẽ kết thúc bằng nói ~ 50 mục) - nếu người dùng của bạn cuộn qua danh sách 2000 mục nhỏ, điều gì đó sai và giao diện cần nhiều công việc hơn .

Answer 3

Một tối ưu hóa thực sự đơn giản là

if(currentWord.StartsWith(lastWord)) 

bạn có thể lọc trên danh sách các mục lọc được trả về bởi truy vấn cuối cùng.Tức là, trừ khi bạn giảm số lượng các mục được trả về bởi truy vấn LINQ của bạn như được gợi ý bởi một số câu trả lời khác. Bạn luôn có thể lưu trữ những gì trong truy vấn trong một biến và sau đó làm Take (100) sau đó mặc dù bạn sẽ cần phải đảm bảo thực hiện lười biếng LINQ không cắn bạn trong trường hợp đó.

Trên mặt gắn kết, thay vì thay thế toàn bộ bộ sưu tập, bạn có thể sử dụng ObservableCollection và chỉ thêm/xóa các mục khỏi nó. Sẽ tốt hơn nếu bạn đảo ngược bộ lọc của mình trả về nếu bạn định làm điều đó nhưng bạn sẽ thấy phản hồi nhanh hơn nhiều và sẽ không thấy hiệu suất lớn như vậy nếu người dùng nhập nhanh.

Answer 4

Tôi nghĩ vấn đề là bộ lọc của bạn thực hiện O(n) (nơi n là tổng số các mặt hàng để tự động hoàn thành từ), có nghĩa là, nó phải trải qua mỗi mục để tìm ra những trận đấu. Bạn càng có nhiều mục, bộ lọc sẽ càng tệ hơn.

Thay vì sử dụng danh sách, hãy thử sử dụng trie. Số lần thực hiện thực hiện O(m), trong đó m là số ký tự trong chuỗi. Điều này có nghĩa là kích thước của tập dữ liệu không ảnh hưởng đến hiệu suất của tra cứu.

Trong Promptu (trình chạy ứng dụng tôi đã viết), tôi sử dụng các lần thử trong phần intellisense/autocomplete. Nếu bạn muốn xem ví dụ về các hành động cố gắng, bạn có thể tải xuống và dùng thử.

Answer 5

Đây là "điều kiện chủng tộc" của bạn.

orderby s.FilterValue 

Xem xét chuỗi chữ d, o, g.

• "d" bắt đầu chạy và khớp với 30% của tập hợp. 6000 mặt hàng phải được đặt hàng.
• "do" bắt đầu chạy và sẽ khớp với tỷ lệ 6% của tập hợp. 1200 mặt hàng phải được đặt hàng.
• "chú chó" bắt đầu chạy và sẽ khớp với 0,5% của tập hợp. 100 mặt hàng phải được đặt hàng.

Khi xem xét khối lượng công việc khác nhau của từng sự kiện, không có gì ngạc nhiên khi sự kiện cuối cùng kết thúc trước sự kiện đầu tiên và thứ hai.

Hành vi chính xác nhất mà tôi có thể tưởng tượng là ngăn chặn sự ràng buộc cho bất kỳ sự kiện hoạt động nào trước đó khi sự kiện bắt đầu. Nếu bạn có thể ngăn chặn sự ràng buộc bằng cách tạm dừng thực hiện trên những sự kiện đó, thì càng nhiều càng tốt. Nhớ lại những quả tên lửa đó, chúng không còn mục tiêu nữa.