搜索列表表示字符串.StartsWith（）
我有一个
List 有1500个字符串。 我现在使用以下代码只提取以字符串prefixText开头的字符串。
foreach(string a in ) { if(a.StartsWith(prefixText, true, null)) { newlist.Add(a); } }
这很快，但我正在寻找谷歌快速。 现在我的问题是，如果我按字母顺序排列List，那么比较char by char我可以加快速度吗？ 或者其他任何有关加快速度的建议？
1500通常太少：
-
你可以通过一个简单的划分并征服问题来并行搜索它。 将列表的每一半搜索为两个（或分成三个，四个，……，部分）不同的作业/线程。
-
或者将字符串存储在（非二进制）树中。 将是O（log n）。
-
按字母顺序排序，您可以进行二分查找（与前一个相同）
因此，1500实际上并不是一个庞大的二进制搜索排序列表就足够了。 然而，用于前缀搜索的最有效算法基于名为Trie或Prefix Tree的数据结构。 请参阅： http ： //en.wikipedia.org/wiki/Trie
下图简要介绍了这个想法： 
对于c＃实现，请参阅例如用于前缀字符串搜索的.NET数据结构和子站点（INFIX）搜索实现自动完成和INTELLI-SENSE
如果您按照alpabetical顺序列出了列表，则可以使用二进制搜索的变体来使其快得多。
作为一个起点，这将返回与前缀匹配的其中一个字符串的索引，因此您可以在列表中向前和向后查找其余内容：
public static int BinarySearchStartsWith(List words, string prefix, int min, int max) { while (max >= min) { int mid = (min + max) / 2; int comp = String.Compare(words[mid].Substring(0, prefix.Length), prefix); if (comp < 0) { min = mid + 1; } else if (comp > 0) { max = mid - 1; } else { return mid; } } return -1; } int index = BinarySearchStartsWith(theList, "pre", 0, theList.Count - 1); if (index == -1) { // not found } else{ // found }
注意：如果使用比任何比较的字符串都长的前缀，它将会中断，因此您可能需要弄清楚如何处理它。
分析了许多方法，以实现最低数据容量和高性能。 首先是：所有前缀都存储在字典中：键 – 前缀，值 – 适用于前缀的项。
这里简单实现了这个算法：
public class Trie { #region Constructors public Trie( IEnumerable items, Func keySelector, IComparer comparer) { this.KeySelector = keySelector; this.Comparer = comparer; this.Items = (from item in items from i in Enumerable.Range(1, this.KeySelector(item).Length) let key = this.KeySelector(item).Substring(0, i) group item by key) .ToDictionary( group => group.Key, group => group.ToList()); } #endregion #region Properties protected Dictionary> Items { get; set; } protected Func KeySelector { get; set; } protected IComparer Comparer { get; set; } #endregion #region Methods public List Retrieve(string prefix) { return this.Items.ContainsKey(prefix) ? this.Items[prefix] : new List (); } public void Add(TItem item) { var keys = (from i in Enumerable.Range(1, this.KeySelector(item).Length) let key = this.KeySelector(item).Substring(0, i) select key).ToList(); keys.ForEach(key => { if (!this.Items.ContainsKey(key)) { this.Items.Add(key, new List { item }); } else if (this.Items[key].All(x => this.Comparer.Compare(x, item) != 0)) { this.Items[key].Add(item); } }); } public void Remove(TItem item) { this.Items.Keys.ToList().ForEach(key => { if (this.Items[key].Any(x => this.Comparer.Compare(x, item) == 0)) { this.Items[key].RemoveAll(x => this.Comparer.Compare(x, item) == 0); if (this.Items[key].Count == 0) { this.Items.Remove(key); } } }); } #endregion }
您可以使用PLINQ（并行LINQ）来加快执行速度：
var newList = list.AsParallel().Where(x => x.StartsWith(prefixText)).ToList()
您可以通过在调用StartsWith之前比较第一个字符来加速一点：
char first = prefixText[0]; foreach(string a in ) { if (a[0]==first) { if(a.StartsWith(prefixText, true, null)) { newlist.Add(a); } } }
我假设真正最快的方法是生成一个包含1500个字符串中所有可能前缀的字典，有效地预先计算将返回非空的所有可能搜索的结果。 然后，您的搜索将只是在O（1）时间内完成的字典查找。 这是交易记忆（和初始化时间）的速度的情况。
private IDictionary prefixedStrings; public void Construct(IEnumerable strings) { this.prefixedStrings = ( from s in strings from i in Enumerable.Range(1, s.Length) let p = s.Substring(0, i) group s by p ).ToDictionary( g => g.Key, g => g.ToArray()); } public string[] Search(string prefix) { string[] result; if (this.prefixedStrings.TryGetValue(prefix, out result)) return result; return new string[0]; }
您是否尝试过实施字典并比较结果？ 或者，如果您按字母顺序排列条目，请尝试二进制搜索。
对我而言，问题是你是否需要这样做一次或多次。
如果您只找到一次StartsWithPrefix列表，则不能更快，然后保留原始列表并执行myList.Where(s => s.StartsWith(prefix)) 。 这一次查看每个字符串，所以它是O(n)
如果您需要多次查找StartsWithPrefix列表，或者您可能想要在原始列表中添加或删除字符串并更新StartsWithPrefix列表，那么您应该对原始列表进行排序并使用二进制搜索。 但这将是sort time + search time = O(n log n) + 2 * O(log n)
如果您使用二进制搜索方法，您将找到第一次出现前缀的索引以及最后一次出现的索引。 然后执行mySortedList.Skip(n).Take(mn)其中n是第一个索引，m是最后一个索引。
编辑：
等一下，我们正在使用错误的工具来完成工作。 使用特里 ！ 如果您将所有字符串放入Trie而不是列表中，那么您所要做的就是使用前缀向前走，然后抓住该节点下面的所有单词。
我会选择使用Linq：
var query = list.Where(w => w.StartsWith("prefixText")).Select(s => s).ToList();