c# - 如何提高该算法的性能？

Question

我有一个包含 100000 对的文本文件:单词和频率。

test.in 包含文字的文件:

• 1 行 - 所有词频对的总数
• 2 行到 ~100 001 - 词频对
• 100 002 行 - 用户输入单词的总数
• 从100003到最后-用户输入词

我解析这个文件，把里面的话放进去

Dictionary<string,double> dictionary;

我想在下面的代码中执行一些搜索+订单逻辑:

for(int i=0;i<15000;i++)
{
    tempInputWord = //take data from file(or other sources)

    var adviceWords = dictionary
                .Where(p => p.Key.StartsWith(searchWord, StringComparison.Ordinal))
                .OrderByDescending(ks => ks.Value)
                .ThenBy(ks => ks.Key,StringComparer.Ordinal)
                .Take(10)
                .ToList();

    //some output
}

问题:此代码必须在 10 秒内运行。

在我的电脑(核心 i5 2400、8gb RAM)上使用 Parallel.For() - 大约 91 秒。

你能给我一些提高性能的建议吗？

更新:

万岁!我们做到了! 感谢@CodesInChaos、@usr、@T_D 以及所有参与解决问题的人。

最终代码:

var kvList = dictionary.OrderBy(ks => ks.Key, StringComparer.Ordinal).ToList();

var strComparer = new MyStringComparer();
var intComparer = new MyIntComparer();
var kvListSize = kvList.Count;
var allUserWords = new List<string>();
for (int i = 0; i < userWordQuantity; i++)
{
    var searchWord = Console.ReadLine();
    allUserWords.Add(searchWord);
}
var result =  allUserWords
    .AsParallel()
    .AsOrdered()
    .Select(searchWord =>
    {
        int startIndex = kvList.BinarySearch(new KeyValuePair<string, int>(searchWord, 0), strComparer);
        if (startIndex < 0)
            startIndex = ~startIndex;

        var matches = new List<KeyValuePair<string, int>>();

        bool isNotEnd = true;
        for (int j = startIndex; j < kvListSize ; j++)
        {
            isNotEnd = kvList[j].Key.StartsWith(searchWord, StringComparison.Ordinal);
            if (isNotEnd) matches.Add(kvList[j]);
            else break;
        }
        matches.Sort(intComparer);

        var res = matches.Select(s => s.Key).Take(10).ToList();

        return res;
    });
foreach (var adviceWords in result)
{
   foreach (var adviceWord in adviceWords)
   {
       Console.WriteLine(adviceWord);
   }
   Console.WriteLine();
}

6 sec (9 sec without manual loop (with linq)))

Answer 1

您根本没有使用字典的任何算法强度。理想情况下，您将使用树结构以便执行前缀查找。另一方面，您与绩效目标的差距在 3.7 倍以内。我认为您可以通过优化算法中的常数因子来实现。

1. 不要在性能关键代码中使用 LINQ。手动遍历所有集合并将结果收集到 List<T> 中.事实证明，这在实践中大大加快了速度。
2. 根本不用字典。只需使用 KeyValuePair<T1, T2>[]并使用 foreach 运行它环形。这是遍历一组对的最快方法。

可能看起来像这样:

KeyValuePair<T1, T2>[] items;
List<KeyValuePair<T1, T2>> matches = new ...(); //Consider pre-sizing this.

//This could be a parallel loop as well.
//Make sure to not synchronize too much on matches.
//If there tend to be few matches a lock will be fine.
foreach (var item in items) {
 if (IsMatch(item)) {
  matches.Add(item);
 }
}

matches.Sort(...); //Sort in-place

return matches.Take(10); //Maybe matches.RemoveRange(10, matches.Count - 10) is better

这应该超过 3.7 倍的加速。

如果您需要更多，请尝试将项目填充到以 Key 的第一个字符为关键字的字典中.这样您就可以查找与 tempInputWord[0] 匹配的所有项目.这应该通过 tempInputWord 的第一个字符中的选择性来减少搜索时间。 .对于大约为 26 或 52 的英文文本。这是具有一级查找的前缀查找的原始形式。不漂亮，但也许就足够了。