Map.Map vs函数

Question

为什么在这种情况下，使用数据构造函数和函数要比使用String和Map慢？

编辑:请注意我对Rotsor答案的第二个评论，它解释了为什么我接受了nulvinges的答案。

运行缓慢：

module Main where

import qualified Data.List as List

main :: IO ()
main = do
    print $ conspire fabFive fabFive

-- here i actually have 80 constructors
data Eris = Hera | Athene | Aphrodite | Paris | Helene
            deriving (Ord, Eq, Show, Read, Enum, Bounded)

fabFive = [minBound..maxBound] :: [Eris]

conspire :: [Eris] -> [Eris] -> [Eris]
conspire [Hera]   [Hera]   = [Hera, Athene]
...
conspire [Hera]   [Helene] = [Athene, Aphrodite, Paris]
...
conspire [Helene] [Helene] = [Hera]

conspire [a] (b:bs) =
    List.union (conspire [a] [b]) (conspire [a] bs)
conspire (a:as) ls =
    List.union (conspire [a] ls) (conspire as ls)

运行速度更快：

module Main where

import qualified Data.Map as Map
import qualified Data.Set as Set

main :: IO ()
main = do 
    print $ conspire (Set.fromList fabFive) (Set.fromList fabFive)

fabFive = [ Hera, Athene, Aphrodite, Paris, Helene ]

conspire :: Set.Set String -> Set.Set String -> Set.Set String
conspire set1 set2 = Set.fold Set.union Set.empty $ Set.map
    (\x -> Set.fold Set.union Set.empty $ Set.map
        (\y -> conspiracy Map.! (Set.singleton x, Set.singleton y))
        set2
    )
    set1

conspiracy = Map.fromList
    [ ( (Set.singleton "Hera" , Set.singleton "Hera" )
      , Set.fromList [ "Hera", "Athene" ]
      )
    ...
    , ( (Set.singleton "Hera" , Set.singleton "Helene" )
      , Set.fromList [ "Athene", "Aphrodite", "Paris" ]
      )
    ...
    , ( (Set.singleton "Helene" , Set.singleton "Helene" )
      , Set.fromList [ "Hera" ]
      )
    ]

Answer 1

Map创建了一个哈希图，其值为O(1)，但是使用一个函数，您必须检查每个条件。

编辑:这实际上是错误的。Map是一个大小平衡的二叉树，但这应该会给conspire带来O(logn)的复杂度，而函数必须检查每个组合，因此具有O(n)复杂度。

记住模式匹配是如何工作的：

f 0 = 0
f i = 1+f (i-1)

是语法糖，适用于：

f i = if i == 0
      then 0
      else 1+f (i-1)

您正在进行O(n)比较，以找出您想要执行的函数。

使用Map，它在二叉树中进行搜索，并且只需执行O(logn)比较。

Answer 2

你的第一个版本运行很慢，因为List.nub函数，效率非常低。它在N为列表大小的情况下以O(N^2)时间工作。其他一切都将由大型N的nub主导。