哪一个更快,为什么？

Question

(n >= 3 ) && (n <= 99)

要么

 n `elem` [3..99]

哪一个更快,为什么？

Answer 1

第一个更快

 (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++])

Answer 2

(n> = 3)&&(n <= 99)更快,因为它只涉及两个平凡的比较.如果编译器/解释器没有做任何真正的黑魔法优化,它必须构造列表([3..99]),因为懒惰的评估不能使用(通常"拉"下一个值,直到你完成,在这种情况下会有O(n/2)的复杂度.

Answer 3

这两个表达并不意味着相同的事情.一个微妙的区别是一个依赖于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

此外,尽管四个前奏Num实例(Int,Integer,Float和Double)都是的所有实例Ord和Enum,可以想像一个数值类型,它是一个实例Ord,但不是Enum.在这种情况下,第二次测试甚至不合法.

因此,一般情况下,编译器不能将第二个与第一个一样快,除非它知道给定类型,Ord并且该范围内的所有有序值也在创建的列表枚举中enumFromTo.对于Float并且Double这不是真的,因为Int并且Integer编译器无法导出它,编译器和库程序员必须手动编写它并确保它在所有情况下都保持.