列表视图中的高性能搜索

Question

我正在使用 Linq 在 WinRT 上的 ListView 中搜索和显示特定字符串 (Windows Phone 8.1)。这是我目前的方法：

string value = (string) sender.Text.ToLower();
if (value == "")
{
    AirportsList.ItemsSource = _airports.CountryList;
}
else
{
    List<Airport> queryList = _airports.AirportList
        .Where(airport => airport.IcaoId.ToLower().Contains(value) 
                      || airport.IcaoName.ToLower().Contains(value) 
                      || airport.City.ToLower().Contains(value) 
                      || airport.Country.ToLower().Contains(value)).ToList();
    AirportsList.ItemsSource = queryList.ToList();
}

这非常缓慢和滞后，因为它每次都必须创建项目源。有没有更高效的方法？

Answer 1

我想创建 queryList 不一定是最慢的部分。这只是一个 List<Airport>，一个 class 任何硬件都可以以最小的开销进行实例化。我想缓慢的部分是必须根据所有可能机场的四个不同属性检查您的价值，其中可能有很多。此外，对于每个属性，您正在搜索它是否 Contains 字符串，而不是仅在开头（通过 StartsWith）。这意味着每个属性都必须线性搜索您的结果。

幸运的是，搜索项目是一个非常常见的计算问题；因此，比我聪明的开发人员设计了许多解决方案来加快搜索速度，或者至少让它们 看起来 快速。我建议您选择下面列出的项目的组合（并搜索更多！）。如果不写一个非常长的答案（也许另一个 SO'er 会帮忙），我无法提供它们的实现，但希望它们能帮助您搜索！

Return 收集到 UI 结果 - 这个不需要 根本性的 改变对您的方法来说，它也不会使其更快，但即时 UI 反馈从心理上来说 非常重要，并且会引起用户的注意。
缩小查询范围 - 他们是在搜索 LHR、TPE 还是任何三个字母的短语？他们很可能正在搜索 ICAO id。首先通过 ICAO ID 执行搜索，然后尽快将它们回显到 UI。检查他们的 IP，他们是从位于英国的计算机上搜索的吗？如果是，您可以优先考虑英格兰等地的机场。在许多情况下，这将完成大多数人的搜索，而无需经过所有可能的排列。当然，在这些快捷方式之后进行全排列搜索，以防他们进行非标准搜索。

子集以前的查询答案 - 如果他们搜索 Lon 并且搜索检索到 London Heathrow、London Gatwick 和 Londrina，那么对 Londo 的后续搜索只会 return 这些响应的一个子集。这需要您保持先前请求（和响应）的状态，并且在实践中可能很复杂。

预排序和索引 _airports.AirportList 并使用不同的搜索算法 - 目前，您正在对机场进行线性搜索，复杂度为 O(n) .如果您最初使用 StartsWith 而不是 Contains 进行搜索，那么使用二进制搜索会将算法降低到 O(log n)，如果有 alot 的机场，最终会更快。按 IcaoId、IcaoName、City、Country 将你的 _airports.AirportList 预分类到单独的索引/列表中（如果你有空闲的内存）并针对这些进行二进制搜索.

如果这不起作用，开始喝酒（和微优化） - 你可以先发制人 ToLower 你的 _airports.AirportList 这样您不必在搜索时不断地降低它们的大写字母。您可以利用缓存优化并将 _airports.AirportList 扁平化为并行 List<IcaoId>、List<IcaoName> 等。您可以统计分析客户的搜索习惯并围绕他们优化搜索（例如，90% 是使用两个机场，始终将这些机场放在搜索堆的顶部）。您可以将搜索卸载到 3^rd 方服务，确实具有几乎瞬间完成的计算能力（I' D 认真考虑这个 ）。您可以对整个过程进行多线程处理。你可以用 C++ 重写它，当你 2 个月前写的 one class 内存泄漏到你的 phone 时，你会很生气。你可以找到证据表明你的老板卷入了性丑闻和勒索 him/her，完全避免这个问题，等等

列表视图中的高性能搜索

Performant search in listview

c#

linq

listview

windows-runtime