计算排列占用太多时间

Question

我正在尝试生成20个！排列并对其进行一些逻辑运算。我切换到多处理，当我增加进程的数量（相对于核心的数量）时，性能会提高。 我已经控制了25秒10秒！32核系统的计算。 我最后的任务是做20个！在不到2小时，我正在考虑GPU编程。对我应该遵循的方法提出建议

Answer 1

10! = 3628800  
20! = 2432902008176640000  
20!/10! = 670442572800  

如果需要25秒才能生成10！排列，需要大约670442572800乘以25秒。它将花费531490年。请复习你的问题。在

Answer 2

每当我做任何涉及大量置换的事情时，我都会考虑如何避免在生成置换时重新计算已经计算过的值。其中一种方法是使用递归。通过使用递归，您通常可以计算前n个可能性一次，然后将计算出的值转发给所有其他函数调用，而无需重新计算n！时代。然后下一个函数调用处理n-1个可能性，依此类推。这种方法的问题是递归本身会给所有函数调用增加相当大的开销，并阻止编译器内联+应用进一步的优化。在

给你说你有n！排列，我假设你可能在重新排列n个项目。如果这些排列需要一段时间才能生成每一个排列（不仅仅是简单的加法/乘法或其他），那么您可以考虑做的一件事是（如果可能的话），生成所有可能的k项排列，这就是k！*（20选择k），仍然比20小很多！对于小k，则将其存储在哈希表或排序数组中，然后查找其他所有值（20-k）！*（20选择k）排列。如果您正在搜索某个最佳值，请尝试从每个查询中将其“减去”到查找表中（如果可能的话，也可以这样做），如果有条目，则为最佳值。在

如果没有关于这个问题的更多细节，恐怕我没有更多的建议了。在