我有一个
List<string>
有 1500 个字符串。我现在使用以下代码仅提取以字符串 prefixText 开头的字符串。
foreach(string a in <MYLIST>)
{
if(a.StartsWith(prefixText, true, null))
{
newlist.Add(a);
}
}
这非常快，但我正在快速寻找谷歌。现在我的问题是，如果我按字母顺序排列列表，然后逐个字符比较，我可以让它更快吗？或者有什么其他让这个更快的建议吗？
因此 1500 并不是一个非常大的数字，对排序列表进行二进制搜索可能就足够了。然而，最有效的前缀搜索算法是基于名为 Trie 或前缀树的数据结构。见：http ://en.wikipedia.org/wiki/Trie
下图非常简要地展示了这个想法：
对于 c# 实现，请参见例如.NET DATA STRUCTURES FOR PREFIX STRING SEARCH AND SUBSTRING (INFIX) Search 以实现自动完成和智能感知
如果您有按字母顺序排列的列表，则可以使用二进制搜索的变体使其更快。
作为起点，这将返回与前缀匹配的字符串之一的索引，因此您可以在列表中向前和向后查找以查找其余部分：
public static int BinarySearchStartsWith(List<string> 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
}
注意：如果您使用的前缀比所比较的任何字符串都长，它将中断，因此您可能需要弄清楚您想如何处理它。
您可以使用PLINQ（并行 LINQ）来加快执行速度：
var newList = list.AsParallel().Where(x => x.StartsWith(prefixText)).ToList()
分析了如此多的方法以实现最小的数据容量和高性能。第一个地方是：所有前缀都存储在字典中：key - 前缀，values - 适合前缀的项目。
这里简单实现这个算法：
public class Trie<TItem>
{
#region Constructors
public Trie(
IEnumerable<TItem> items,
Func<TItem, string> keySelector,
IComparer<TItem> 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<string, List<TItem>> Items { get; set; }
protected Func<TItem, string> KeySelector { get; set; }
protected IComparer<TItem> Comparer { get; set; }
#endregion
#region Methods
public List<TItem> Retrieve(string prefix)
{
return this.Items.ContainsKey(prefix)
? this.Items[prefix]
: new List<TItem>();
}
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<TItem> { 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
}
我认为真正最快的方法是从 1500 个字符串中生成一个包含所有可能前缀的字典，有效地为所有可能返回非空的搜索预先计算结果。然后，您的搜索将只是在 O(1) 时间内完成的字典查找。这是一个用内存（和初始化时间）换取速度的例子。
private IDictionary<string, string[]> prefixedStrings;
public void Construct(IEnumerable<string> 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];
}
您可以通过在调用 StartsWith 之前比较第一个字符来加快速度：
char first = prefixText[0];
foreach(string a in <MYLIST>)
{
if (a[0]==first)
{
if(a.StartsWith(prefixText, true, null))
{
newlist.Add(a);
}
}
}
1500 通常太少：
您可以通过对问题的简单分而治之来并行搜索它。在两个（或分成三个、四个、...、部分）不同的作业/线程中搜索列表的每一半。
或者将字符串存储在（不是二叉树）树中。将是 O(log n)。
按字母顺序排序，您可以进行二进制搜索（与前一个相同）
您是否尝试过实施字典并比较结果？或者，如果您确实按字母顺序排列条目，请尝试二进制搜索。
对我来说，问题是您是否需要这样做一次或多次。
如果您只找到一次 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(m-n)哪里 n 是第一个索引，m 是最后一个索引。
等一下，我们使用了错误的工具来完成这项工作。使用特里！如果您将所有字符串放入 Trie 而不是列表，您所要做的就是沿着带有您的前缀的 trie 并获取该节点下的所有单词。
我会使用 Linq：
var query = list.Where(w => w.StartsWith("prefixText")).Select(s => s).ToList();