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)

我的猜测是,在你的情况下,你有fromAscList [2..i-1]多次GHCi重新计算,或类似的东西.