Haskell 中判斷一個(gè)整數(shù)是否在某個(gè)閉區(qū)間內(nèi)哪種方法更快，>= && <=，還是 elem ？

假設(shè)我有一個(gè)整數(shù) x，我要判斷該整數(shù)是否在 [1, limit] 這個(gè)區(qū)間內(nèi)，在 Haskell 中我能想到兩種方案：

x >= 1 and x <= limit
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]

顯示的結(jié)果：

不知方法對(duì)不對(duì)，請(qǐng)問(wèn)兩種方案哪一種更快？

回答

編輯回答

瘋浪

沒(méi)想到SF有Haskell問(wèn)題：）

其實(shí)你看Profiling的結(jié)果，in_range的inherited %time和inherited %alloc都比larger_than大，占了整個(gè)程序執(zhí)行的100%和93.3%。所以第一種方法快。

寫個(gè)rewrite rule也許可以對(duì)elem和enumFromTo進(jìn)行優(yōu)化。

試了寫rewrite rule，發(fā)現(xiàn)enumFromTo有inline，導(dǎo)致rewrite rule沒(méi)有生效，所以先自己實(shí)現(xiàn)一個(gè)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結(jié)果是這樣的:

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

還不知道怎讓才能對(duì)enumFromTo生效:(

2017年5月30日 01:59