如何改進Haskell組合算法？

下面介紹的解決方案如何改進以下問題？它能在時間和空間上更有效率嗎？是否有空間泄漏？如何改進Haskell組合算法？

問題：鑑於Astronauts輸入列表中，產生對Astronauts這樣的，該對不具有來自相同國家二級Astronauts的列表。假設輸入具有Astronauts的列表以及唯一的identifiers。

data Astronaut = Astronaut { identifier :: Int, country :: String } deriving (Eq) 

astronautPairs :: [Astronaut] -> [(Astronaut, Astronaut)] 
astronautPairs xs = foldl accumulatePairs [] [(a, b) | a <- xs, b <- xs, country a /= country b] 
    where 
     accumulatePairs pairs pair = if hasPair pair pairs then pairs else pair:pairs 
     hasPair [email protected](a,b) ((c,d):xs) = a == d && b == c || hasPair pair xs 
     hasPair _ [] = False

來源

2015-10-09 hamsterdam

您認爲應該佔用多少空間？一旦你決定，只需在一個大輸入上運行你的代碼，看看你的內存使用情況是否匹配（在這裏'-stderr'運行時選項可以派上用場）。然後你告訴我們*是否有空間泄漏。 – crockeea

您可能喜歡[我之前的答案]（http://stackoverflow.com/a/6473153/791604）中的'pairs'函數。 –

你想同時生產'（a，b）'和'（b，a）'，還是你打算代表兩人團隊？ – dfeuer

而是消除了對翻轉爲什麼不能避免在首位生成它們的。它是我們產生它們，是嗎？

import Data.List (tails) 

astronautPairs :: [Astronaut] -> [(Astronaut, Astronaut)] 
astronautPairs xs = [ (y,z) | (y:ys) <- tails xs, z <- .... , country y /= country .... ]

這假定宇航員的輸入列表沒有重複。

因此，我們避免了三角一代的重複。

（我離開的代碼的一部分了，你來完成）。

來源

2015-10-10 05:56:48

是的，那對我來說很合適。這是什麼空間複雜性？當然， – hamsterdam

時間是二次的。空間將取決於最終名單的長度。除了輸入列表的O（n）大小以外，任何編譯器都不能製作一個在O（1）空間中工作的代碼，而該代碼必須完全存在於內存中 - 也就是說，這不是一個在線算法，即使最後一個元素被訪問，GC也不能收回列表的頭元素。 –

有道理。謝謝！ – hamsterdam

讓我們從實現細節退一步，想想你要完成的任務：

產生對Astronaut s的列表，使得對不具備從兩個Astronaut小號相同的國家

你似乎被允許假設每個宇航員在列表中只出現一次。

解決此問題的一種有效方法是先按照國家劃分列表開始。一個自然的方法是建立一個HashMap String [Int]，它包含了來自每個國家的所有宇航員的列表。現在

import qualified Data.HashMap.Strict as HMS import Data.HashMap.Strict (HashMap) divideAstronauts :: [Astronaut] -> HashMap String [Int] divideAstronauts = foldl' go mempty where go hm (Astronaut ident cntry) = HMS.insertWith (++) cntry [ident] hm

可以瓜分程序的其餘部分分爲兩個步驟：

選擇所有對國家的。

對於每一對國家，選擇所有的宇航員對，每對來自這些國家之一。

來源

2015-10-10 04:39:45 dfeuer

如何改進Has​​kell組合算法？

回答

相關問題

如何改進Haskell組合算法？