哪一个更快，为什么？

Question

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

或者

 n `elem` [3..99]

哪个更快，为什么？

- Pratik Deoghare

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

- Dead account

---

你期望看到什么“黑魔法”？即使编译器在幕后识别 [3..99] 是一个范围并执行了范围检查，它仍将只是 (n >= 3) && (n <= 99) 的相同结果。 - Dead account

我猜你可以通过使用重写规则，像这样 "elem/enumFromTo" forall x lo hi. elem x (enumFromTo lo hi) = (x >= lo && x <= hi)，让 GHC 优化这个特定的情况。不过我从来没有用过重写规则（太像黑魔法了;-)，所以请谨慎对待这个建议！ - yatima2975

所以我得出结论，没有黑魔法！ ;)) +1A 我喜欢带有代码的答案。 - Pratik Deoghare

我认为elem首先会执行(n >= start) && (n <= end)的检查，然后使用step、start、end即[start，start+step，start+2*step...end]来判断n是否在范围内。 - Pratik Deoghare

elem 没有办法知道它所使用的列表是什么：特别地，它来自像 [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

Answer 2

(n >= 3) && (n <= 99)更快，因为它仅涉及两个琐碎的比较。如果编译器/解释器没有进行任何真正的黑魔法优化，它必须构建列表([3..99])，因为不能使用惰性求值(通常是“拉”下一个值，直到完成，在这种情况下的复杂度为O(n/2))。

- Florian Thiel

---

+1 所以并没有黑魔法，虽然我本来期望有一些 :) 同时欢迎来到 SO！ - Pratik Deoghare

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

此外，尽管四个 Prelude Num 实例 (Int、Integer、Float 和 Double) 都是 Ord 和 Enum 的实例，但仍然可以想象一种数字类型，它是 Ord 的实例，但不是 Enum 的实例。在这种情况下，第二个测试甚至都不合法。

因此，通常情况下，编译器无法像第一个测试那样进行优化，除非它知道对于给定的类型，它是 Ord 的，并且范围内的所有有序值也都在由 enumFromTo 创建的枚举列表中。对于 Float 和 Double 来说，这并不成立，而对于 Int 和 Integer，编译器没有办法推导出来，必须由编译器和库程序员手动编写代码，并确保在所有情况下都成立。

- MtnViewMark

Answer 4

这取决于机器和编译器（或解释器）。

- Thomas Eding