1

假设我有一个特定类的集合（可以是数组、通用列表或任何最快解决此问题的方法），我们称之为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);
}

如何尽快获得结果？我应该考虑一些高级索引技术和数据结构吗？

此问题的应用程序域是一个自动完成器，它获取查询并作为结果提供一组建议。假设条件没有比这更复杂。还假设会有很多搜索。

4

9 回答 9

2

由于条件子句可以是“任何东西”的约束，您只能扫描整个列表并应用条件。

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

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

因此，这实际上归结为您要对这些数据进行哪些查询。

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

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

编辑，根据评论

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

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

其他任何东西都是对这些概念的一些专业化。

于 2008-09-18T22:13:14.887 回答
1

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

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

于 2008-09-18T21:48:11.920 回答
0

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

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

于 2008-09-18T21:49:03.057 回答
0

我现在不熟悉我的 Java，但我会考虑以下事情。

你是如何创建你的列表的？也许您可以通过一种减少比较时间的方式创建它已经排序。

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

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

通过找出最有可能是真的比较来优化您的比较查询并首先进行比较也可能会有所帮助。即：如果集合的成员通常有 10% 的时间以您的查询开始，而成员有 30% 的时间以查询结束，那么您可能希望先进行结束比较。

于 2008-09-18T21:56:30.353 回答
0

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

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

于 2008-09-18T21:56:43.443 回答
0

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

于 2008-09-18T21:59:35.603 回答
0

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

我们可以像这样构建一个索引：

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，但是我们必须再次保持索引是最新的。不能保证它更快，但它肯定更复杂。

于 2008-09-18T22:01:36.490 回答
0

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

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

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

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

于 2008-09-18T22:21:16.473 回答
0

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

于 2008-09-19T22:06:41.157 回答