在 C# 中搜索名称列表的最快方法

from s in stringList
where s.ToLower().Contains(searchWord.ToLower())
select s

查找子字符串(不是完全匹配(非常困难。没有任何内置功能可以帮助您解决此问题。我建议您研究可用于有效查找子字符串的后缀树数据结构。

你可以searchWord.ToLower()拉出到局部变量中，以节省大量的字符串操作，顺便说一句。您还可以预先计算字符串列表的小写版本。如果无法预先计算，至少使用 s.IndexOf(searchWord, StringComparison.InvariantCultureIgnoreCase) != -1 .这样可以节省昂贵的 ToLower 呼叫。

你也可以打一个.作为查询的并行。

另一种选择，虽然它需要相当多的内存，但还是预先计算后缀数组之类的东西(字符串中的位置列表，按它们指向的字符串排序(。

http://en.wikipedia.org/wiki/Suffix_array

如果要搜索的字符串列表相对静态，这将是最可行的。整个字符串索引列表可以存储在单个元组数组(indexOfString，positionInString(中，您可以使用String.Compare(keyword, 0, target, targetPos, keyword.Length)执行二叉搜索。

因此，如果您有 100,000 个平均长度为 20 的字符串，则需要 100,000 * 20 * 2*sizeof(int( 的内存用于结构。您可以通过将 indexOfString 和 positionInString 打包到一个 32 位 int 中来将其减半，例如，在最低的 12 位中使用 positionInString，在其余的高位中使用 indexOfString。你只需要做一点摆弄就可以把这两个值弄回来。请务必注意，该结构本身不包含字符串或子字符串。要搜索的字符串仅存在一次。

这基本上会给你一个完整的索引，并允许非常快速地找到任何子字符串(对后缀数组表示的索引进行二叉搜索(，而实际的字符串比较最少。

如果内存很重要，那么对原始蛮力算法的简单优化是预先计算唯一字符的字典，并分配序号来表示每个字符。然后为每个字符串预先计算一个位数组，并为字符串中包含的每个唯一字符设置位。由于您的字符串相对较短，因此恢复的 BitArray 应该有相当多的可变性(如果您的字符串很长，它不会很好地工作(。然后，您只需计算 BitArray 或搜索关键字，并且仅在keywordBits & targetBits == keywordBits 的字符串中搜索关键字。如果您的字符串预转换为小写，并且只是英文字母，则 BitArray 可能适合单个整数。因此，这将需要最少的额外内存，易于实现，并允许您快速过滤掉您肯定找不到关键字的字符串。这可能是一个有用的优化，因为字符串搜索速度很快，但是使用暴力搜索可以执行很多操作。

编辑 对于那些感兴趣的人，这是我提出的初始解决方案的基本实现。我使用 OP 描述的 100,000 个随机生成的长度字符串运行了测试。虽然构建和排序索引大约需要 30 秒，但一旦完成，搜索关键字 3000 次的速度是暴力破解的 49,805 毫秒，使用索引搜索的速度为 18 毫秒，因此快了几千倍。如果您很少构建列表，那么我最初构建后缀数组的简单但相对缓慢的方法应该就足够了。有更聪明的方法来构建它，速度更快，但需要比下面我的基本实现更多的编码。

// little test console app
static void Main(string[] args) {
    var list = new SearchStringList(true);
    list.Add("Now is the time");
    list.Add("for all good men");
    list.Add("Time now for something");
    list.Add("something completely different");
    while (true) {
        string keyword = Console.ReadLine();
        if (keyword.Length == 0) break;
        foreach (var pos in list.FindAll(keyword)) {
            Console.WriteLine(pos.ToString() + " =>" + list[pos.ListIndex]);
        }
    }
}
~~~~~~~~~~~~~~~~~~
// file for the class that implements a simple suffix array
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Collections;
namespace ConsoleApplication1 {
    public class SearchStringList {
        private List<string> strings = new List<string>();
        private List<StringPosition> positions = new List<StringPosition>();
        private bool dirty = false;
        private readonly bool ignoreCase = true;
        public SearchStringList(bool ignoreCase) {
            this.ignoreCase = ignoreCase;
        }
        public void Add(string s) {
            if (s.Length > 255) throw new ArgumentOutOfRangeException("string too big.");
            this.strings.Add(s);
            this.dirty = true;
            for (byte i = 0; i < s.Length; i++) this.positions.Add(new StringPosition(strings.Count-1, i));
        }
        public string this[int index] { get { return this.strings[index]; } }
        public void EnsureSorted() {
            if (dirty) {
                this.positions.Sort(Compare);
                this.dirty = false;
            }
        }
        public IEnumerable<StringPosition> FindAll(string keyword) {
            var idx = IndexOf(keyword);
            while ((idx >= 0) && (idx < this.positions.Count)
                && (Compare(keyword, this.positions[idx]) == 0)) {
                yield return this.positions[idx];
                idx++;
            }
        }
        private int IndexOf(string keyword) {
            EnsureSorted();
            // binary search
            // When the keyword appears multiple times, this should
            // point to the first match in positions. The following
            // positions could be examined for additional matches
            int minP = 0;
            int maxP = this.positions.Count - 1;
            while (maxP > minP) {
                int midP = minP + ((maxP - minP) / 2);
                if (Compare(keyword, this.positions[midP]) > 0) {
                    minP = midP + 1;
                } else {
                    maxP = midP;
                }
            }
            if ((maxP == minP) && (Compare(keyword, this.positions[minP]) == 0)) {
                return minP;
            } else {
                return -1;
            }
        }
        private int Compare(StringPosition pos1, StringPosition pos2) {
            int len = Math.Max(this.strings[pos1.ListIndex].Length - pos1.StringIndex, this.strings[pos2.ListIndex].Length - pos2.StringIndex);
            return String.Compare(strings[pos1.ListIndex], pos1.StringIndex, this.strings[pos2.ListIndex], pos2.StringIndex, len, ignoreCase);
        }
        private int Compare(string keyword, StringPosition pos2) {
            return String.Compare(keyword, 0, this.strings[pos2.ListIndex], pos2.StringIndex, keyword.Length, this.ignoreCase);
        }
        // Packs index of string, and position within string into a single int. This is
        // set up for strings no greater than 255 bytes. If longer strings are desired,
        // the code for the constructor, and extracting  ListIndex and StringIndex would
        // need to be modified accordingly, taking bits from ListIndex and using them
        // for StringIndex.
        public struct StringPosition {
            public static StringPosition NotFound = new StringPosition(-1, 0);
            private readonly int position;
            public StringPosition(int listIndex, byte stringIndex) {
                this.position = (listIndex < 0) ? -1 : this.position = (listIndex << 8) | stringIndex;
            }
            public int ListIndex { get { return (this.position >= 0) ? (this.position >> 8) : -1; } }
            public byte StringIndex { get { return (byte) (this.position & 0xFF); } }
            public override string ToString() {
                return ListIndex.ToString() + ":" + StringIndex;
            }
        }
    }
}

有一种方法会快得多。 但这意味着寻找确切的单词匹配，而不是使用Contains功能。

基本上，如果你有它的记忆，你可以创建一个单词字典，它也为找到单词的字符串引用某种ID(或ID(。

所以字典可能是类型 <string, List<int>> . 当然，这里的好处是您可以将许多单词合并到一个较小的集合中。 而且，字典的查找速度非常快，因为它建立在哈希表上。

现在，如果这不是您要查找的内容，则可以搜索内存中全文搜索库。 SQL Server 支持使用索引进行全文搜索，以加快传统通配符搜索以外的过程。 但是纯内存解决方案肯定会更快。 但是，这仍然可能无法为您提供通配符搜索的确切功能。

在这种情况下，

您需要的是一个反向索引。

如果您热衷于支付大量费用，则可以使用特定于数据库的全文搜索索引，并调整索引以索引每个单词子集。

或者，您可以使用一个非常成功的开源项目来实现同样的事情。

您需要使用分词器对字符串进行预索引，并生成反向索引文件。我们在 Java 中也有类似的用例，我们必须在大量数据中实现非常快速的自动完成。

你可以看看 Lucene.NET 这是Apache Lucene(Java(的一个端口。

如果你愿意放弃LINQ，你可以使用NHibernate搜索。(眨眼(。

另一种选择是在内存中实现预索引，不需要预处理和绕过扫描，看看 Knuth-Morris-Pratt 算法。