這個問題涉及任意數量的骰子，每個骰子有任意數量的面。然后我們找到可以放在順子中的最大骰子數，請參閱Google 的 Code Jam 解釋。我一直在嘗試解決 Haskell 中的問題，我認為以下解決方案在演算法上有效。但是，在問題上獲得滿分還不夠快，所以可以優化嗎？
import Data.List (sort)
getMaxStraight :: [Int] -> Int
getMaxStraight sides =
foldl
(\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight)
0
(sort sides)
除此之外，我還撰寫了一個可以及時運行的 Python 解決方案。到底是怎么回事？
def solve(sides)
sides = sorted(sides)
max_straight = 0
for side in sides:
if side > max_straight:
max_straight = 1
return max_straight
編輯：這篇文章已“還原”為舊版本。可以在此處找到更新版本的帖子
uj5u.com熱心網友回復：
您在這里所做的是構建一個大型運算式樹，它將查找以下串列[1, 2, 3, 4, 5, 6]：
f (f (f (f (f (f 0 1) 2) 3) 4) 5) 6
使用flambda 運算式\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight。因此，您將首先創建一個可能會占用大量記憶體的大型運算式，然后對其進行評估。
正如檔案foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b所說：
如果您想要一個有效的嚴格左折疊，您可能想要使用
foldl'而不是foldl. 這樣做的原因是后者在將內部結果z `f` x1應用于運算子（例如 to ）之前不會強制內部結果（例如在上面的示例中(`f` x2)）。這會導致 thunk 鏈??(n) 個元素長，然后必須從外向內對其進行評估。
通過使用foldl' :: Foldable t => (b -> a -> b) -> b -> t a -> b, 對于每一步，結果將被評估為弱頭范式 (WHNF) [haskell-wiki]，因此您可以防止創建大的 thunk。您可以像這樣實作：
import Data.Foldable(foldl')
getMaxStraight :: [Int] -> Int
getMaxStraight sides =
foldl'
(\maxStraight side -> if side > maxStraight then succ maxStraight else maxStraight)
0
(sort sides)轉載請註明出處，本文鏈接：https://www.uj5u.com/qianduan/462840.html
上一篇：Haskell庫中是否有類似陣列的資料結構，插入O(logn)并檢索O(logn)？我可以用拉鏈推匯出一個嗎？
下一篇：如何從源代碼構建llvm-hs