Dictionary<string, string> 值查找性能

Question

我正在做一个小项目，但运行遇到了性能障碍。

我有一个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);
    }
}

Answer 1

我认为主要问题是您在每次迭代中都遍历整个字典 - 这是 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);
  }
}

Answer 2

你可以试试这个

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();

Dictionary<string, string> 值查找性能

Dictionary<string, string> Value lookup performance

c#

performance

dictionary

lookup

pseudocode