什么是过滤字符串作出智能感知/自动完成列表时，列表中的最快方法是什么？ [英] What is the fastest way to filter a list of strings when making an Intellisense/Autocomplete list?

问题描述

我在写一个智能感知/自动完成像一个你会发现在Visual Studio。这是所有罚款，直到在列表中包含大概2000+的项目。

I'm writing an Intellisense/Autocomplete like the one you find in Visual Studio. It's all fine up until when the list contains probably 2000+ items.

我使用一个简单的LINQ语句做筛选：

I'm using a simple LINQ statement for doing the filtering:

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

我然后分配这个集合到一个WPF ListBox的ItemSource，这就是它的结束，工作正常。

I then assign this collection to a WPF Listbox's ItemSource, and that's the end of it, works fine.

注意到，列表框也被虚拟化一样，所以只会有在内存中，并在可视化树最多7-8的视觉元素。

Noting that, the Listbox is also virtualised as well, so there will only be at most 7-8 visual elements in memory and in the visual tree.

然而，需要注意的现在的问题是，当用户输入速度极快，在RichTextBox中，并在每一个关键的了，我执行过滤+结合，有这个半竞争状态，或不同步的过滤，像第一个键中风的过滤仍然可以做它的过滤或结合工作，而第四个按键行程也这样做。

However the caveat right now is that, when the user types extremely fast in the richtextbox, and on every key up I execute the filtering + binding, there's this semi-race condition, or out of sync filtering, like the first key stroke's filtering could still be doing it's filtering or binding work, while the fourth key stroke is also doing the same.

我知道应用滤镜之前，我可以把一个延迟，但我想实现无缝过滤很像一个在Visual Studio中。

I know I could put in a delay before applying the filter, but I'm trying to achieve a seamless filtering much like the one in Visual Studio.

我不知道在哪里我的问题正是在于，所以我也这归因于的IndexOf的字符串操作，或者是我的字符串的可能在某种指标进行优化的名单，这可能会加速搜索。

I'm not sure where my problem exactly lies, so I'm also attributing it to IndexOf's string operation, or perhaps my list of string's could be optimised in some kind of index, that could speed up searching.

code样品的任何建议都值得欢迎。

Any suggestions of code samples are much welcomed.

感谢。

推荐答案

我觉得问题是，你的过滤器执行 O（N）（其中 N 是自动完成的项目总数），也就是说，它要经过的每次的项目，以找出哪些比赛。在更多的项目你有，坏的过滤器将执行。

I think the problem is that your filter performs O(n) (where n is the total number of items to autocomplete from), that is, it has to go through every item to figure out which ones match. The more items you have, the worse the the filter will perform.

，请尝试使用线索。尝试执行 O（M），其中 M 是字符串中的字符数。这意味着数据集的大小不影响查找的性能

Instead of using a list, try using a trie. Tries perform O(m), where m is the number of characters in the string. This means the size of the dataset does not affect the performance of the lookup.

在 Promptu （一个应用程序启动我写了），我使用的尝试智能感知/自动完成。如果你想尝试看看在行动的一个例子，你可以下载它，并尝试一下。

In Promptu (an app launcher I wrote), I use tries in the intellisense/autocomplete. If you want to see an example of tries in action, you can download it and try it out.

这篇关于什么是过滤字符串作出智能感知/自动完成列表时，列表中的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！