从集合中查找与字符串成员条件匹配的对象的最快方法

StackOverflow https://stackoverflow.com/questions/97329

题

假设我有一个集合（无论是数组、通用列表还是其他任何东西） 最快的 这个问题的解决方案）属于某个类，我们称之为 ClassFoo:

class ClassFoo
{
    public string word;
    public float score;
    //... etc ...
}

假设集合中有大约 50,000 个项目，全部都在内存中。现在我想尽快获取集合中遵守其 bar 成员条件的所有实例，例如如下所示：

List<ClassFoo> result = new List<ClassFoo>();
foreach (ClassFoo cf in collection)
{
    if (cf.word.StartsWith(query) || cf.word.EndsWith(query))
        result.Add(cf);
}

我怎样才能尽快得到结果？我应该考虑一些高级索引技术和数据结构吗？

此问题的应用程序域是自动完成器，它获取查询并给出建议集合作为结果。假设条件不会比这更复杂。还假设将会有大量搜索。

有帮助吗？

解决方案

由于条件子句可以是“任何内容”，因此您只能扫描整个列表并应用条件。

如果条件子句有限制，那么您可以考虑组织数据以更有效地处理查询。

例如，带有“byFirstLetter”字典的代码示例对于“endsWith”查询根本没有帮助。

因此，这实际上取决于您想要针对该数据执行哪些查询。

在数据库中，这个问题是“查询优化器”的负担。在典型的数据库中，如果您的数据库没有索引，显然每个查询都将是表扫描。当您向表添加索引时，优化器可以使用该数据制定更复杂的查询计划，以更好地获取数据。这本质上就是您所描述的问题。

一旦您有了更具体的查询类型子集，您就可以更好地决定哪种结构最好。此外，您还需要考虑数据量。如果您有一个包含 10 个元素的列表，每个元素都小于 100 字节，那么扫描所有内容很可能是您能做的最快的事情，因为您的数据量如此之少。显然，这不能扩展到 1M 元素，但即使是巧妙的访问技术也会在设置、维护（如索引维护）和内存方面产生成本。

编辑, ，根据评论

如果它是自动完成器，如果数据是静态的，则对其进行排序并使用二分搜索。你真的不会比这更快了。

如果数据是动态的，则将其存储在平衡树中，然后进行搜索。这实际上是一种二分搜索，它可以让您不断随机添加数据。

其他的都是这些概念的一些专业化。

其他提示

var Answers = myList.Where(item => item.bar.StartsWith(query) || item.bar.EndsWith(query));

我认为这是最简单的，应该执行得相当快。

不确定我是否理解...您真正能做的就是优化规则，这是需要最快的部分。如果不添加更多硬件，就无法加速循环。

如果您有多个核心或机器，您可以并行化。

我现在不擅长 Java，但我会考虑以下事情。

您如何创建列表？也许您可以以减少比较时间的方式创建已经订购的产品。

如果您只是对集合进行直接循环，那么将其存储为数组或链表之间不会有太大区别。

为了存储结果，根据收集结果的方式，结构可能会有所不同（但假设 Java 的通用结构很智能，则不会）。正如我所说，我不太懂 Java，但我假设通用链表会保留尾指针。在这种情况下，这实际上并没有什么区别。对底层数组与链表实现以及它最终如何在字节代码中查找有更多了解的人可能会告诉您是否使用尾指针附加到链表或插入数组更快（我的猜测是数组）。另一方面，如果您想使用数组，您需要知道结果集的大小，或者牺牲一些存储空间并使其与您正在迭代的整个集合一样大。

通过找出哪个比较最有可能是正确的来优化比较查询，并且首先执行此操作也可能会有所帮助。IE：如果通常有 10% 的时间集合成员以查询开始，30% 的时间成员以查询结束，则您需要首先进行结束比较。

对于您的特定示例，对集合进行排序将有所帮助，因为您可以对以查询开头的第一个项目进行二进制切入，并在到达下一个不以查询开头的项目时提前终止；您还可以生成一个指向集合项的指针表，该集合项按第二个子句的每个字符串的反向排序。

一般来说，如果你事先知道查询的结构，你可以对你的集合进行适当的排序（或者如果有多个子句，则为你的集合构建多个排序索引）；如果不这样做，你将无法比线性搜索做得更好。

如果您填充列表一次，然后进行多次查找（数千次或更多），那么您可以创建某种查找字典，将以值开头/结尾的值映射到其实际值。这将是一个快速查找，但会使用更多内存。如果您没有进行那么多查找，或者知道您将至少半频繁地重新填充列表，那么我会使用 CQ 建议的 LINQ 查询。

您可以创建某种索引，它可能会变得更快。

我们可以建立这样的索引：

Dictionary<char, List<ClassFoo>> indexByFirstLetter;
foreach (var cf in collection) {
  indexByFirstLetter[cf.bar[0]] = indexByFirstLetter[cf.bar[0]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[0]].Add(cf);
  indexByFirstLetter[cf.bar[cf.bar.length - 1]] = indexByFirstLetter[cf.bar[cf.bar.Length - 1]] ?? new List<ClassFoo>();
  indexByFirstLetter[cf.bar[cf.bar.Length - 1]].Add(cf);
}

然后像这样使用它：

foreach (ClasssFoo cf in indexByFirstLetter[query[0]]) {
  if (cf.bar.StartsWith(query) || cf.bar.EndsWith(query))
    result.Add(cf);
}

现在我们可能不必像您的示例中那样循环遍历尽可能多的 ClassFoo，但我们必须再次保持索引最新。不能保证它更快，但肯定更复杂。

依靠。您的所有对象总是会加载到内存中吗？可以加载的对象是否有限制？您的查询是否必须考虑尚未加载的对象？

如果集合变得很大，我肯定会使用索引。

事实上，如果集合可以增长到任意大小，并且您不确定是否能够将其全部放入内存中，我会考虑 ORM、内存数据库或其他嵌入式数据库。我想到了用于 ORM 的 DevExpress 的 XPO 或用于内存数据库的 SQLite.Net。

如果您不想走这么远，请创建一个简单的索引，其中包含映射到类引用的“bar”成员引用。

如果可能的条件集是固定的且很小，则可以为列表中的每个元素分配一个位掩码。位掩码的大小是标准集的大小。当您创建元素/将其添加到列表时，您检查它满足哪些条件，然后设置该元素的位掩码中的相应位。匹配列表中的元素就像将它们的位掩码与目标位掩码进行匹配一样简单。更通用的方法是布隆过滤器。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top