(n >= 3 ) && (n <= 99)
或者
n `elem` [3..99]
哪个更快,为什么?
(n >= 3) && (n <= 99)
它正在执行3个操作
n >= 3
n <= 99
and
而elem函数是在数组中查找元素,因此最多执行(99 - 3) * 2次操作。
index = 0
isFound = false
array[] = { 3, 4, 5, 6, ... 98, 99 }
while isFound == false
isFound = (n == array[index++])
(n >= 3) && (n <= 99)更快,因为它仅涉及两个琐碎的比较。如果编译器/解释器没有进行任何真正的黑魔法优化,它必须构建列表([3..99]),因为不能使用惰性求值(通常是“拉”下一个值,直到完成,在这种情况下的复杂度为O(n/2))。
这两个表达式的意思并不相同。微妙的区别在于一个依赖于 Ord
,而另一个依赖于 Enum
:
> :t \n -> (n >= 3) && (n <= 99)
\n -> (n >= 3) && (n <= 99) :: (Num a, Ord a) => a -> Bool
> :t \n -> n `elem` [3..99]
\n -> n `elem` [3..99] :: (Num a, Enum a) => a -> Bool
例如,如果 n 是 3.14159,那么第一个测试将通过,但第二个测试将失败:
> (pi >= 3) && (pi <= 99)
True
> pi `elem` [3..99]
False
此外,尽管四个 Prelude Num
实例 (Int
、Integer
、Float
和 Double
) 都是 Ord
和 Enum
的实例,但仍然可以想象一种数字类型,它是 Ord
的实例,但不是 Enum
的实例。在这种情况下,第二个测试甚至都不合法。
因此,通常情况下,编译器无法像第一个测试那样进行优化,除非它知道对于给定的类型,它是 Ord
的,并且范围内的所有有序值也都在由 enumFromTo
创建的枚举列表中。对于 Float
和 Double
来说,这并不成立,而对于 Int
和 Integer
,编译器没有办法推导出来,必须由编译器和库程序员手动编写代码,并确保在所有情况下都成立。
这取决于机器和编译器(或解释器)。
"elem/enumFromTo" forall x lo hi. elem x (enumFromTo lo hi) = (x >= lo && x <= hi)
,让 GHC 优化这个特定的情况。不过我从来没有用过重写规则(太像黑魔法了;-),所以请谨慎对待这个建议! - yatima2975elem
首先会执行(n >= start) && (n <= end)
的检查,然后使用step
、start
、end
即[start,start+step,start+2*step...end]
来判断n
是否在范围内。 - Pratik Deoghareelem
没有办法知道它所使用的列表是什么:特别地,它来自像[3..99]
这样的表达式的信息在运行时丢失了。想一想如何计算elem n (3 : 4 : 50000 : [6..99]
,你会发现elem
必须遍历所有元素。至于你第一个评论中的问题:请参阅 Data.List 的源代码:http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/GHC-List.html#elem 获取定义(它不涉及数组)。 - yatima2975