Linq 表达式缓慢 - 如果可能，需要优化

Question

我有一个整数列表“numberRangeList”，其中按顺序包含从 62 到 92 的 31 个整数，我正在提取第二个整数列表“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();

Answer 1

性能问题不在于LINQ，而在于问题本身。这个问题在计算机科学文献中众所周知，称为子集和http://en.wikipedia.org/wiki/Subset_sum_problem。这是一个已知问题，属于时间复杂度的 NP 完全类 ( http://en.wikipedia.org/wiki/NP-complete )。如果您不想探索（指数级）问题的复杂性，则应该对次优解决方案进行一些研究。