Haskell:Data.Set `notMember` 比 `notElem` 慢？

Question

我预计 f1 为 O(i²)，f2 为 O(i · log i)。这是怎么回事？

import Data.Set

i = 20000

-- should be slow
f1 = [ x | x <- [1..i] , x `notElem` [2..i-1] ]
-- should be fast
f2 = [ x | x <- [1..i] , x `notMember` fromAscList [2..i-1] ]

ghci 输出:

*Main> f1
[1,20000]
(7.12 secs, 16,013,697,360 bytes)
*Main> f2
[1,20000]
(44.27 secs, 86,391,426,456 bytes)

Answer 1

这只是因为优化尚未发生。如果将以下内容放入文件 F.hs:

module F (f1,f2) where

import Data.Set

-- should be slow
f1 :: Int -> [Int]
f1 i = [ x | x <- [1..i] , x `notElem` [2..i-1] ]
-- should be fast
f2 :: Int -> [Int]
f2 i = [ x | x <- [1..i] , x `notMember` fromAscList [2..i-1] ]

首先进行优化编译，您将得到以下结果:

$ ghc -O2 F.hs       # compile with optimizations
[1 of 1[ Compiling F            ( F.hs, F.o )

$ ghci F.hs          # now load it up in GHCi
GHCi, version 8.0.1: http://www.haskell.org/ghc/  :? for help
Ok, modules loaded: F (F.o)
Prelude F> :set +s
Prelude F> f1 20000
[1,20000]
(2.16 secs, 2,030,440 bytes)
Prelude F> f2 20000
[1,20000]
(0.05 secs, 4,591,312 bytes)

我的猜测是，在您的情况下，您让 GHCi 多次重新计算 fromAscList [2..i-1] ，或类似的事情。