Haskell 中判断一个整数是否在某个闭区间内哪种方法更快,>= && <=,还是 elem ?

dyzdyz010
  • 1.2k

假设我有一个整数 x,我要判断该整数是否在 [1, limit] 这个区间内,在 Haskell 中我能想到两种方案:

  1. x >= 1 and x <= limit
  2. elem x [1..limit]

我使用了 GCI 的 Profiling,代码如下:

main = do
  print $ {-# SCC larger_than  #-} lth 10000
  print $ {-# scc in_range #-} inr 10000

lth :: Integer -> Bool
lth x = (x >= 1 && x <= 65535000000000)

inr :: Integer -> Bool
inr x = let m = 65535000000000::Integer in
  x `elem` [1..m]

显示的结果:

不知方法对不对,请问两种方案哪一种更快?

回复
阅读 1.9k
1 个回答
✓ 已被采纳

没想到SF有Haskell问题:)

其实你看Profiling的结果,in_rangeinherited %timeinherited %alloc都比larger_than大,占了整个程序执行的100%和93.3%。所以第一种方法快。

写个rewrite rule也许可以对elemenumFromTo进行优化。

试了写rewrite rule,发现enumFromTo有inline,导致rewrite rule没有生效,所以先自己实现一个myEnumFromTo看看效果:

module Main where

{-# RULES
   "elem/myEnumFromTo" forall (x::Integer) (n::Integer) (m::Integer) . elem x (myEnumFromTo n m) = x >= n && x <= m 
#-}

{-# NOINLINE myEnumFromTo #-}
myEnumFromTo n m
  | n == m = [n]
  | otherwise = [n] ++ myEnumFromTo (n + 1) m

main = do
  print $ {-# SCC larger_than  #-} lth 100000000
  print $ {-# scc in_range #-} inr     100000000

lth :: Integer -> Bool
lth x = (x >= 1 && x <= 65535000000000)

inr :: Integer -> Bool
inr x = let m = 65535000000000::Integer in
  x `elem` (myEnumFromTo 1 m)

Profile结果是这样的:

main        Main             app/Main.hs:(12,1)-(14,48)    0.0   15.8


                                                                                   individual      inherited
COST CENTRE    MODULE                SRC                        no.     entries  %time %alloc   %time %alloc

MAIN           MAIN                  <built-in>                 144          0    0.0   29.6     0.0  100.0
 CAF           GHC.Conc.Signal       <entire-module>            252          0    0.0    0.9     0.0    0.9
 CAF           GHC.IO.Encoding       <entire-module>            241          0    0.0    3.8     0.0    3.8
 CAF           GHC.IO.Encoding.Iconv <entire-module>            239          0    0.0    0.3     0.0    0.3
 CAF           GHC.IO.Handle.FD      <entire-module>            231          0    0.0   47.3     0.0   47.3
 CAF           GHC.IO.Handle.Text    <entire-module>            229          0    0.0    0.1     0.0    0.1
 CAF           GHC.Show              <entire-module>            214          0    0.0    0.4     0.0    0.4
 CAF           GHC.Event.Thread      <entire-module>            193          0    0.0    1.7     0.0    1.7
 CAF           GHC.Event.Poll        <entire-module>            160          0    0.0    0.1     0.0    0.1
 CAF:main1     Main                  <no location info>         286          0    0.0    0.0     0.0    0.0
  main         Main                  app/Main.hs:(12,1)-(14,48) 288          1    0.0    0.0     0.0    0.0
 CAF:main2     Main                  <no location info>         284          0    0.0    0.0     0.0    0.0
  main         Main                  app/Main.hs:(12,1)-(14,48) 293          0    0.0    0.0     0.0    0.0
   in_range    Main                  app/Main.hs:14:32-48       294          1    0.0    0.0     0.0    0.0
    inr        Main                  app/Main.hs:(20,1)-(21,29) 295          1    0.0    0.0     0.0    0.0
     inr.m     Main                  app/Main.hs:20:13-39       296          1    0.0    0.0     0.0    0.0
 CAF:main4     Main                  <no location info>         285          0    0.0    0.0     0.0    0.0
  main         Main                  app/Main.hs:(12,1)-(14,48) 290          0    0.0    0.0     0.0    0.0
   larger_than Main                  app/Main.hs:13:36-48       291          1    0.0    0.0     0.0    0.0
    lth        Main                  app/Main.hs:17:1-39        292          1    0.0    0.0     0.0    0.0
 main          Main                  app/Main.hs:(12,1)-(14,48) 289          0    0.0   15.8     0.0   15.8

还不知道怎让才能对enumFromTo生效:(

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏