假设我有某个类的集合(无论是数组，通用List还是解决该问题的最快方法)，我们将其称为" 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);
}

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

此问题的应用程序域是一个自动完成程序，它可以获取查询并提供一系列建议。假设条件没有比这更复杂的了。还要假设会有很多搜索。

解决方案

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

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

不确定我是否理解...我们真正能做的就是优化规则，这是需要最快的部分。我们不能不给它增加更多硬件就加速循环。

如果我们有多个内核或者计算机，则可以并行化。

我现在还没有使用Java，但是我会考虑以下事项。

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

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

为了存储结果，根据我们收集结果的方式，结构可能会有所不同(但假设Java的通用结构很聪明，那么不会)。就像我说的那样，我还没有掌握Java，但是我假设通用链表将保留一个尾指针。在这种情况下，它并没有真正的改变。较了解底层数组与链接列表实现及其最终结果的人可能会告诉我们，使用尾指针添加到链接列表还是插入数组是否更快(我猜可能是数组) )。另一方面，如果要使用数组，则需要知道结果集的大小或者牺牲一些存储空间，并使它与要迭代的整个集合一样大。

通过找出最有可能是正确的比较来优化比较查询，并且首先进行比较也可能会有所帮助。即：如果通常集合的某个成员有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，但是接下来我们必须使索引保持最新。不能保证它更快，但是肯定会更复杂。

由于条件子句可以是"任何"的约束，因此我们只能扫描整个列表并应用条件。

如果条件子句有限制，那么我们可以查看如何组织数据以更有效地处理查询。

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

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

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

一旦有了查询类型的更具体子集，就可以对哪种结构最好做出更好的决策。另外，我们需要考虑数据量。如果我们有10个元素的列表，每个元素少于100个字节，那么扫描所有内容可能是最快的操作，因为数据量非常小。显然，这不能扩展到1M元素，但是即使是聪明的访问技术也要在设置，维护(如索引维护)和内存上付出成本。

编辑，基于注释

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

如果数据是动态的，则将其存储在平衡的树中并进行搜索。这实际上是一个二进制搜索，它使我们可以继续随机添加数据。

除此之外，还有一些关于这些概念的专业化知识。

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

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

实际上，如果集合可以增长到任意大小，并且我们不确定是否可以将其全部放入内存中，那么我将研究ORM，内存数据库或者其他嵌入式数据库。我想到了DevExpress的XPO for ORM或者SQLite.Net的内存数据库。

如果我们不想走那么远，请创建一个简单的索引，该索引由映射到类引用的" bar"成员引用组成。

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