如何提高这种算法的性能？

Question

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

test.in文件包含单词:

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

我解析这个文件并把文字放进去

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秒(9秒无手动循环(带linq)))

Answer 1

你完全没有使用字典的任何算法强度.理想情况下,您使用树结构,以便您可以执行前缀查找.另一方面,您的性能目标是3.7倍.我认为你可以通过优化算法中的常数因子来实现这一点.

1. 不要在执行关键代码中使用LINQ.手动循环遍历所有集合并将结果收集到一个List<T>.事实证明,这在实践中可以大大加快速度.
2. 根本不要使用字典.只需使用a 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].这应该通过第一个char中的选择性来减少搜索时间tempInputWord.对于大约26或52的英文文本.这是前缀查找的原始形式,具有一级查找.不漂亮,但也许就够了.

Answer 2

• 将字典替换为 a List<KeyValuePair<string, decimal>>，按键排序。

  对于搜索，我使用子字符串通过序数比较直接在其前缀之前排序。所以我可以使用二分搜索来找到第一个候选者。由于候选者是连续的，我可以替换Where为TakeWhile.

  int startIndex = dictionary.BinarySearch(searchWord, comparer);
  if(startIndex < 0)
      startIndex = ~startIndex;
  
  var adviceWords = dictionary
              .Skip(startIndex)
              .TakeWhile(p => p.Key.StartsWith(searchWord, StringComparison.Ordinal))
              .OrderByDescending(ks => ks.Value)
              .ThenBy(ks => ks.Key)
              .Select(s => s.Key)
              .Take(10).ToList();
  

• 确保对所有操作都使用序数比较，包括初始排序、二分查找和检查StartsWith。

• 我会Console.ReadLine在并行循环之外调用。可能使用AsParallel().Select(...)搜索词的集合而不是Parallel.For.