Linq表达式慢-如果可能的话需要优化

本文关键字：优化 表达式 如果 Linq | 更新日期: 2023-09-27 18:09:33

我有一个整数列表"numberRangeList"，其中按顺序包含31个从62到92的整数，我正在提取第二个整数列表"extractedList"，它将包含10个整数，其总和等于"total"。问题是计算大约需要30秒，有没有办法加快速度?

        var numberRangeList = new List<int>() { 62, 63, ...92 };
        var total = 772;
        var extractedList= (from n1 in numberRangeList
                      from n2 in numberRangeList
                      from n3 in numberRangeList
                      from n4 in numberRangeList
                      from n5 in numberRangeList
                      from n6 in numberRangeList
                      from n7 in numberRangeList
                      from n8 in numberRangeList
                      from n9 in numberRangeList
                      from n10 in numberRangeList
                      where n1 + n2 + n3 + n4 + n5 + n6 + n7 + n8 + n9 + n10 == total
                      select new List<int> { n1, n2, n3, n4, n5, n6, n7, n8, n9, n10 }).Take(1).First();

Linq表达式慢-如果可能的话需要优化

性能问题不在于LINQ，而在于问题本身。这个问题在CS文献中很有名，它被称为子集和http://en.wikipedia.org/wiki/Subset_sum_problem。这是一个已知的问题，属于时间复杂度的np完全类(http://en.wikipedia.org/wiki/NP-complete)。如果你不想探索(指数)问题的复杂性，你应该做一些次优解决方案的研究。

问题不在于LINQ查询-问题是你的算法复杂性是O(n^10) -大约有(92-62+1)^10个操作完成-这是很多工作，即使是现代cpu。您可以使用backpack动态规划算法来解决您的问题，然后使用BFS(宽度优先搜索)来查找包含十个数字的结果。

在我看来，您的查询计算了从公共数字池中获取的10个数字的所有可能组合。(或者，在数据库术语中，您正在计算一个非常大的叉乘。)有很多可能的组合需要处理。这也许并不奇怪，仅仅找到第一个匹配就需要30秒。

如果我没有完全搞错的话，你的计算类似于所谓的背包问题。如果是这样，也许你可以通过研究这个众所周知的问题找到一个优化方法。

更新:根据@Saverio Terracciano的评论，将您的问题视为背包问题的实例可能会引入比严格要求更多的复杂性。或许还可以看看子集问题

相关文章：