在创建Intellisense/Autocomplete列表时，过滤字符串列表的最快方法是什么？

Question

我正在编写一个Intellisense/Autocomplete，就像你在Visual Studio中找到的一样。在列表可能包含2000+项之前，一切都很好。

我使用一个简单的LINQ语句进行过滤：

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

然后，我将这个集合赋值给一个WPF列表框的ItemSource，这就是它的结尾，一切正常。

注意，列表框也是虚拟化的，所以在内存和可视化树中最多只能有7-8个可视化元素。

然而，现在需要注意的是，当用户在richtextbox中输入的速度非常快，并且在每次按键时，我执行过滤+绑定，就会出现这种半竞争条件，或者说不同步过滤，就像第一次击键的过滤可能仍然在做过滤或绑定工作，而第四次击键也在做同样的工作。

我知道我可以在应用过滤器之前进行延迟，但我正在尝试实现与Visual Studio中的过滤器非常类似的无缝过滤。

我不确定我的问题到底出在哪里，所以我也将其归因于IndexOf的字符串操作，或者我的字符串列表可以在某种索引中进行优化，这可以加快搜索速度。

任何关于代码样本的建议都非常受欢迎。

谢谢。

Answer 1

我建议尝试将结果集限制在一定数量的项上，看看问题是否消失了。也就是说，您可能有5000个可供选择，但尽量返回不超过100，即使更多匹配。可以这样说：

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

如果您的问题消失了，速度减慢可能是由于为列表框返回的项太多所致。我不确定这个问题会不会消失，因为ListBox是虚拟化的，但值得一试。您也可以尝试相同的操作，但在排序(即，orderby)之前，将过滤结果限制为100个项目，看看这是否有帮助。不管怎样，按下面的顺序做会更有效率：

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

底线是确定问题是返回并分配给filterColection的项目数的函数，还是初始项目数的函数，或者两者兼而有之。

Answer 2

如果你有一个2000个项目的结果集，延迟不是你的问题。我在这里做了一些大的假设，但你实际上只需要返回500个项目-你的用户将不断输入以缩小结果集，直到它达到可以浏览的大小。

你应该优化常见的情况(我假设它最终会有大约50个项目)-如果你的用户正在滚动一个2000个项目的小列表，那么一定是其他地方出了问题，界面需要更多的工作。

Answer 3

我认为问题是您的过滤器执行O(n) (其中n是要自动完成的项目的总数)，也就是说，它必须检查每一项以找出哪些匹配。你拥有的项目越多，过滤器的性能就越差。

尝试使用trie，而不是使用列表。尝试执行O(m)，其中m是字符串中的字符数。这意味着数据集的大小不会影响查找的性能。

在Promptu (我编写的一个应用程序启动程序)中，我在智能感知/自动完成中使用了尝试。如果您想要查看实际尝试的示例，可以下载并试用。