你当前的代码没有充分利用 Dictionary
/ SortedDictionary
/ HashSet
这些特殊集合的功能,你使用它们的方式与使用 List
的方式相同。所以你看不到任何性能上的差异。
如果你将字典作为索引,其中字符串的前几个字符是键,字符串列表是值,那么从搜索字符串中可以挑选出可能匹配的一小部分整个字符串集合。
我编写了下面的类来测试这个想法。如果我用一百万个字符串填充它,并用一个八个字符的字符串进行搜索,则可以在大约3毫秒内快速找到所有可能的匹配项。用一个字符的字符串进行搜索是最坏的情况,但它可以在大约4毫秒内找到前1000个匹配项。查找一个字符字符串的所有匹配项需要大约25毫秒。
该类创建1、2、4和8字符键的索引。如果你查看你的具体数据和搜索内容,你应该能够选择要创建哪些索引来优化你的条件。
public class IndexedList {
private class Index : Dictionary<string, List<string>> {
private int _indexLength;
public Index(int indexLength) {
_indexLength = indexLength;
}
public void Add(string value) {
if (value.Length >= _indexLength) {
string key = value.Substring(0, _indexLength);
List<string> list;
if (!this.TryGetValue(key, out list)) {
Add(key, list = new List<string>());
}
list.Add(value);
}
}
public IEnumerable<string> Find(string query, int limit) {
return
this[query.Substring(0, _indexLength)]
.Where(s => s.Length > query.Length && s.StartsWith(query))
.Take(limit);
}
}
private Index _index1;
private Index _index2;
private Index _index4;
private Index _index8;
public IndexedList(IEnumerable<string> values) {
_index1 = new Index(1);
_index2 = new Index(2);
_index4 = new Index(4);
_index8 = new Index(8);
foreach (string value in values) {
_index1.Add(value);
_index2.Add(value);
_index4.Add(value);
_index8.Add(value);
}
}
public IEnumerable<string> Find(string query, int limit) {
if (query.Length >= 8) return _index8.Find(query, limit);
if (query.Length >= 4) return _index4.Find(query,limit);
if (query.Length >= 2) return _index2.Find(query,limit);
return _index1.Find(query, limit);
}
}
TryGetValue
或进行ContainsKey
检查来避免这种情况。 - Anand Sowmithiran