python - python 2 中的 `in range` 构建 --- 工作太慢

Question

我想检查给定的 x位于区间[0,a-1] .作为一个懒惰的编码员，我写了

x in range(a)

并且(因为那段代码在 4.5 嵌套循环中)很快就会遇到性能问题。我测试了它，结果确实是 n in range(n) 的运行时间在于 O(n)，给予或接受。我实际上认为我的代码会被优化为 x >= 0 and x < a但似乎并非如此。即使我修复了 range(a)提前时间不会变得恒定(尽管它会改善很多)- 请参阅旁注。

所以，我的问题是:

我应该使用 x >= 0 and x < a 吗？并且从不写x in range(a)以后再？有没有更好的写法？

---

旁注:

1. 我尝试在 SO 中搜索 range, python-2.7, performance标签放在一起，什么也没找到(与 python-2.x 相同)。

2. 如果我尝试以下操作:

   i = range(a)
   ...
   x in i
   

   因此范围是固定的，我只测量 x in i 的运行时间，我仍然在 O(x) 中获得运行时间(假设 a 足够大)。

3. n in xrange(n) 的运行时也在于 O(n)。
4. 我找到了 this post ，它为 python 3 提出了类似的问题。我决定在 python 3 上测试相同的东西，它通过测试就像什么都没有一样。我为 python 2 感到难过。

Answer 1

range 的问题在 Python 2 中，它创建了一个 list的值，所以 x in range(a)将创建一个列表并线性扫描该列表。 xrange 应该是一个生成器，但也快不了多少；可能仍然只是线性扫描值，而不是先创建整个列表。

In [2]: %timeit 5*10**5 in range(10**6 + 1)  # Python 2
10 loops, best of 3: 18.1 ms per loop

In [3]: %timeit 5*10**5 in xrange(10**6 + 1) # Python 2
100 loops, best of 3: 6.21 ms per loop

在Python 3 , range 更聪明，不仅不创建整个列表，而且还提供了 contains 的快速实现检查。

In [1]: %timeit 5*10**5 in range(10**6 + 1)  # Python 3
1000000 loops, best of 3: 324 ns per loop

更快，恕我直言，更具可读性:使用比较链:

In [2]: %timeit 0 <= 5*10**5 < 10**6 + 1     # Python 2 or 3
10000000 loops, best of 3: 46.6 ns per loop

---

Should I use x >= 0 and x < a and never write x in range(a) ever again? Is there an even better way of writing it?

“否”、“视情况而定”和"is"。你不应该使用 x >= 0 and x < a因为0 <= x < a更短且更容易解析(对于弱小的人)，并被解释为 (0 <= x) and (x < a) .你不应该使用 in range 在 Python 2 中，但在 Python 3 中，您可以根据需要使用它。

不过，我更喜欢比较链，因为 a <= x < b关于边界比 x in range(a, b) 更明确(如果 x == b 会怎么样？)，这可以防止许多差一错误或 +1填充范围。

另外，请注意 0 <= x < a与 x in range(0, a) 不完全相同, 作为 range将只包含整数值，即 1.5 in range(0, 5)是False ，而 0 <= 1.5 < 5是True ，这可能不是你想要的。此外，使用 range您可以使用 1 以外的步骤，例如5 in range(4, 10, 2)是False ，但也可以使用纯数学来实现，例如作为(4 <= x < 10) and (x - 4 % 2 == 0) .