什麼是影響列表理解內容的因素（處理時間）？

Question

從learn-you-a-haskell學到一個例子，其中所有邊和等於或小於10的整數的直角三角形的邊長爲24？「

rightTrianglesOriginal = [（a，b，c）| [0127]- [1..10]，b < - [1..10]，a < - [1..10]，a^2 + b^2 == c^2，a + b + c == 24]

我改變了原來的例子的部分，並希望瞭解下面的過程（在極端條件下）。

• 謂詞的順序是否會影響性能？

• 添加謂詞（否則由其他謂詞暗示）會影響性能嗎？ （例如a> b，c> a，c> b？）？基於謂詞（1）a> b和（2）c> a製作一個元組列表，然後進一步應用^ 2 + b^2 = c^2會不會增強整體性能？

• 如果我們改變參數位置，例如，是否會影響性能？ （a，b，c）或（c，b，a）？

• 如果需要如此繁重的排列和組合，我們是否應該在下次使用時存儲預先計算的答案（儘可能）以提高性能或其他？

rightTriangles = [（A，B，C）| Ç< - [1..10]，B < - [1..10]，一個< - [1..10]，A^2 + B^2 == C^2]

給出幾乎沒有時間。

rightTriangles10 = [（a，b，c）| [- [1..10]，a < - [1..10]，a^2 + b^2 == c^2，a> b，c> a ]

給幾乎沒有時間的結果。

rightTriangles100 = [（a，b，c）| c < - [1..100]，b < - [1..100]，a < - [1..100]，a^2 + b^2 == c^2，a> b，c> a ]

在幾秒鐘內給出結果。

rightTriangles1000 = [（a，b，c）| c < - [1..1000]，b < - [1..1000]，a < - [1..1000]，a^2 + b^2 == c^2，a> b，c> a ]

30分鐘後我停止了處理。結果尚未完成。

請注意，作爲初學者，我缺乏相關知識來檢查單個函數處理的確切時間。

Answer 1

rightTrianglesOriginal = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a+b+c == 24] 

• 謂詞的順序會影響性能？

這取決於。在這種情況下，改變謂詞的順序並不會改變任何實質性的東西，所以差異 - 如果有的話 - 將會非常小。由於a^2 + b^2 == c^2是有點更昂貴的檢查比a + b + c == 24，並且這兩個測試篩選出許多價值，我期望一個小加速通過交換兩個測試

rightTrianglesSwapped = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a+b+c == 24, a^2 + b^2 == c^2] 

但整個計算是如此之小，它會很難可靠地進行測量。一般來說，您可以通過重新排序測試和生成器來獲得很大的差異，特別是將測試和生成器交叉插入到快捷方式的死角可能會產生巨大的影響。在這裏，您可以在b和a發電機之間添加一個b < c測試到快捷方式。當然，將發生器更改爲b <- [1 .. c-1]仍然更有效。

• 是否添加謂詞（否則由其他謂詞暗示）會影響性能？ （例如a > b, c > a, c > b？）？

是的，但通常很少，除非謂詞的評估非常昂貴。在上面，如果謂詞成立，你將會對隱含的第三謂詞進行不必要的評估。這裏謂詞對於標準數字類型來說計算起來很便宜，並且它不經常被評估（大多數候選三元組更早失效），所以影響幾乎不可測量。但是要做的是額外的工作 - 編譯器不夠聰明，無法消除它 - 所以它需要額外的時間。

• 製作元組的列表謂詞（1）a > b和（2）c > a，然後進一步應用^ 2 + B^2 = C^2將提高整體性能或不的基礎上？

這取決於。如果你把一個謂詞放在可以快捷的地方，那會提高性能。有了這些謂詞需要對發生器進行重新排序（在b之前獲得a，因此您可以在c > a上進行快捷操作）。與a^2 + b^2 == c^2相比，計算比較便宜一些，所以即使測試總數增加（後一種情況會比前者多三倍），它仍然可以提高性能，以便首先執行更便宜的測試（但是最多首先鑑別測試也可以是更好的策略，即使它們更昂貴，也取決於成本和功率之間的關係）。

• 如果我們改變參數位置，例如，可以影響性能嗎？ (a,b,c)或(c, b, a)？

基本上，這不能有任何可衡量的影響。

• 什麼是在現實生活中應用的最好的策略，如果需要這樣的重排列組合 - 我們應該（儘可能），以備下次使用存儲預先計算的答案，以提高性能或任何其它？

這取決於。如果計算複雜並且結果很小，最好將結果存儲起來以便重複使用。如果計算結果很便宜並且結果很大，最好重新計算。在這種情況下，畢達哥拉斯三元組的數量很小，計算不是非常便宜，因此存儲以供重用可能是有益的。

rightTriangles10 = [ (a,b,c) | c <- [1..10], b <- [1..10], a <- [1..10], a^2 + b^2 == c^2, a > b , c > a] 

給幾乎沒有時間的結果。

rightTriangles100 = [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a] 

在幾分鐘內給出結果。

rightTriangles1000 = [ (a,b,c) | c <- [1..1000], b <- [1..1000], a <- [1..1000], a^2 + b^2 == c^2, a > b , c > a] 

那麼，三元組檢查的數量是立方在極限，通過10倍，從而增加限制增大三元組由1000倍檢查的數量，對於運行時間因子大致相同，由於內存要求較大，可能會稍大一些。所以甚至沒有編譯，更不用說優化的代碼，

ghci> [ (a,b,c) | c <- [1..100], b <- [1..100], a <- [1..100], a^2 + b^2 == c^2, a > b , c > a] 
[(4,3,5),(8,6,10),(12,5,13),(12,9,15),(15,8,17),(16,12,20),(24,7,25),(20,15,25),(24,10,26) 
,(21,20,29),(24,18,30),(30,16,34),(28,21,35),(35,12,37),(36,15,39),(32,24,40),(40,9,41) 
,(36,27,45),(48,14,50),(40,30,50),(45,24,51),(48,20,52),(45,28,53),(44,33,55),(42,40,58) 
,(48,36,60),(60,11,61),(63,16,65),(60,25,65),(56,33,65),(52,39,65),(60,32,68),(56,42,70) 
,(55,48,73),(70,24,74),(72,21,75),(60,45,75),(72,30,78),(64,48,80),(80,18,82),(84,13,85) 
,(77,36,85),(75,40,85),(68,51,85),(63,60,87),(80,39,89),(72,54,90),(84,35,91),(76,57,95) 
,(72,65,97),(96,28,100),(80,60,100)] 
(2.64 secs, 2012018624 bytes) 

限制1000的預期時間約爲45分鐘。對數據使用一些限制，我們可以做得更快：

ghci> length [(a,b,c) | c <- [2 .. 1000], b <- [1 .. c-1], a <- [c-b+1 .. b], a*a + b*b == c*c] 
881 
(87.28 secs, 26144152480 bytes)