性能模式的GHC

匹配我正在寫我創建了一個數據類型的「追加」功能（這基本上是與「流」交易）。但是，這種數據類型有12種不同的構造函數，處理不同類型的「流」，例如，無限，空，固定長度，可變長度，已附加等。性能模式的GHC

輸入類型和輸出類型之間的邏輯是有點複雜但並不令人難以置信的如此。（也許在一個簡單的代理類型包裝），然後匹配匹配內部或對144箱子

只是模式匹配（12

對陣大類*：

我認爲兩種方法12）。我可以用通配符將特定組合減少到100，但這就是它。

我知道第二種方法更難以維護，但忽視這一點，GHC會發現第二種方法更容易優化嗎？如果它可以通過一個簡單的跳轉表（或者兩個跳轉表）來完成第二種方法，那麼我懷疑它會更快。但是如果它正在進行線性檢查，則速度會更慢。

是否GHC優化模式匹配（甚至是非常大的）轉換成固定的時間跳錶？

來源

2017-01-19 Clinton

相關：[*的Haskell GHC：什麼是一個模式匹配的具有N構造的時間複雜度*]（http://stackoverflow.com/q/9027384/2751851） – duplode

是的，GHC優化了這種模式匹配。前七個（我認爲）構造函數通過指針標記得到了優化，特別好。我相信其餘的將由跳轉表處理。但是144個案例聽起來很難維護，而且您必須注意代碼大小。你真的需要所有這些情況嗎？

來源

2017-01-19 08:29:54 dfeuer

這不是太難寫一個小哈斯克爾腳本寫入一個巨大的情況下塊和一個小基準它。例如：

module Main (main) where 

mapping = zip ['!'..'z'] (reverse ['!'..'z']) 

test_code = 
    [ 
    "module Main where", 
    "", 
    "tester :: String -> String", 
    "tester cs = do", 
    " c <- cs", 
    " case transform c of", 
    " Just c' -> [c']", 
    " Nothing -> [c ]", 
    "", 
    "input = concat [ [' '..'z'] | x <- [1..10000] ]", 
    "", 
    "main = print $ length $ tester $ input", 
    "" 
    ] 

code1 = 
    test_code ++ 
    [ 
    "transform :: Char -> Maybe Char", 
    "transform c = lookup c " ++ show mapping 
    ] 

code2 = 
    test_code ++ 
    [ 
    "transform :: Char -> Maybe Char", 
    "transform c =", 
    " case c of" 
    ] ++ 
    map (\(k, v) -> " " ++ show k ++ " -> Just " ++ show v) mapping ++ 
    [ 
    " _ -> Nothing" 
    ] 

main = do 
    writeFile "Test1.hs" (unlines code1) 
    writeFile "Test2.hs" (unlines code2)

如果你運行這段代碼，它生成的兩個小哈斯克爾源文件：Test1.hs和Test2.hs。前者使用Prelude.lookup將字符映射到字符。後者使用巨大的箱子。這兩個文件都包含將映射應用於大量數據列表並打印出結果大小的代碼。（這樣可以避免I/O，否則這將是主導因素。）在我的系統上，Test1需要幾秒鐘的時間才能運行，而Test2幾乎是瞬間的。

的過興趣的讀者可能想嘗試擴展這個使用Data.Map.lookup和比較的速度。

這證明了模式匹配遠比鍵/值映射列表...這是不是你問的一個O（n）的遍歷更快。但隨時醞釀你自己的基準。您可以嘗試自動生成一個嵌套的案例，並對結果進行計時。我的猜想是你不會看到太多的差異，但隨時嘗試它。

來源

2017-01-19 11:35:19 MathematicalOrchid

性能模式的GHC

回答

相關問題