字典<字符串、字符串>值查找性能
本文关键字:字符串 查找 性能 字典 | 更新日期: 2024-10-30 19:32:32
我正在做一个小项目,但遇到了性能障碍。
我有Dictionary<string, string>()
我有一个string[]
.
假设我的Dictionary
有 50,000 个条目,我的string[]
有 30,000 个条目。
我想从我的Dictionary
中收集Keys
,其中value.ToCharArray().OrderBy(x => x)
等于我string[]
的value.ToCharArray().OrderBy(x => x)
。
我尝试通过将string[]
值的长度与Dictionary
中的值进行比较来减少必须查看的KeyValue
对的数量,但这并没有真正为我带来任何性能。
有没有人知道如何提高此查找的性能?
谢谢!
要扩展伪代码,请执行以下操作:
var stringToLookUp = GetSomeStrings(s.ToString()).Select(x => x).OrderBy(x => x).ToArray();
var aDictionaryOfStringString = GetDictionary(Resources.stringList);
var results = new List<string>();
foreach (var theString in stringToLookUp.Where(aString=> aString.Length > 0))
{
if (theString.Length > 0)
{
var theStringClosure = theString;
var filteredKeyValuePairs = aDictionaryOfStringString.Where(w => w.Value.Length == theStringClosure.Length && !results.Contains(w.Key)).ToArray();
var foundStrings = filteredKeyValuePairs.Where(kv => kv.Value.ToCharArray().OrderBy(c => c).ToArray().SequenceEqual(theStringClosure))
.Select(kv => kv.Key)
.ToArray();
if (foundStrings.Any()) results.AddRange(foundStrings);
}
}
我认为主要问题是你在每次迭代中迭代整个字典 - 这是 O(N^2)。最好根据修改后的键(来自字典或数组)构建哈希集,并迭代第二个。这是 O(N)。
// some values
var dictionary = new Dictionary<string, string>();
var fields = new string[]{};
string[] modifiedFields = new string[fields.Length];
for(var i =0; i < fields.Length; i++)
{
modifiedFields[i] = new string(fields[i].ToCharArray().OrderBy(x =>x).ToArray());
}
var set = new HashSet<string>(modifiedFields);
var results = new List<string>();
foreach(var pair in dictionary)
{
string key = new string(pair.Value.ToCharArray().OrderBy(x =>x).ToArray());
if (set.Contains(key))
{
results.Add(pair.Key);
}
}
你可以试试这个
var stringToLookUp = GetSomeStrings(s.ToString()).Select(x => x).OrderBy(x => x).ToArray();
var aDictionaryOfStringString = GetDictionary(Resources.stringList);
var results = aDictionaryOfStringString.Where(kvp => stringToLookUp.Select(s => s.OrderBy(x => x)).Contains(kvp.Value.OrderBy(x => x))).Select(kvp => kvp.Key).ToList();