我不太熟悉Haskell/GHC可以优化代码的程度.下面我有一个非常"蛮力"(在声明意义上)实施n皇后问题.我知道它可以更有效地编写,但那不是我的问题.这让我想到了GHC优化功能和限制.
我已经在我认为非常简单的陈述性意义中表达了这一点.过滤满足谓词的[1..n]的排列For all indices i,j s.t j<i, abs(vi - vj) != j-i 我希望这是可以优化的东西,但它也有点像要求很多编译器.
validQueens x = and [abs (x!!i - x!!j) /= j-i | i<-[0..length x - 2], j<-[i+1..length x - 1]]
queens n = filter validQueens (permutations [1..n])
oneThru x = [1..x]
pointlessQueens = filter validQueens . permutations . oneThru
main = do
n <- getLine
print $ pointlessQueens $ (read :: String -> Int) n
这种运行速度相当慢并且增长很快. n=10需要大约一秒钟,n=12需要永远.如果没有优化,我可以判断增长是因子(排列数)乘以二次方(要检查的谓词中的差异数).有没有什么办法可以通过智能编译更好地执行此代码？我尝试了ghc这样的基本选项-O2并没有注意到显着的差异,但我不知道更精细的点(只是添加了标志)
我的印象是我调用的函数queens无法优化,必须在过滤之前生成所有排列.无点版本有更好的机会吗？一方面,我觉得过滤器和谓词之间的智能功能理解可能能够在它们甚至完全生成之前敲掉一些明显不受欢迎的元素,但另一方面,它有点像是要感觉很多. …
我想从列表中生成所有可能的对,限制为(a,b)==(b,a)和((a,b),(c,d))==(( c,d),(a,b))所有a,b,c,d.另外,我可以假设我作为参数提供的列表中的所有元素都是不同的.
我做的第一件事就是写下这个列表理解:
pairsOfPairs :: [a] -> [((a,a),(a,a))]
pairsOfPairs xs = [((w,x),(y,z)) | w <- xs, x <- xs, y <- xs, z <- xs,
w < x, y < z, w < y, w /= z, x /= y, x /= z]
这具有惯用的优点,但速度非常慢(剖析显示接近90%的运行时间花费在此功能上,而另一个类似的功能).
缓慢的原因是,对于n个元素的列表,它生成n ^ 4个候选对对,但是这些限制最终将其缩减为n!/(8*(n-4)!),这意味着我们正在做至少8次工作太多了.
有没有办法重写pairsOfPairs能够提高速度的功能？显然它仍然是O(n ^ 4),但我希望降低常数.
编辑:事实上,我几乎总是用长度为5的列表调用此函数,这意味着结果中有5个!/ 8 = 15个元素,但该函数生成一个5 ^ 4 = 625个元素的列表作为中间步骤.如果我能消除所有这些中间元素,我就会获得大约40倍的加速!