在python 2中的`范围'构造---工作太慢

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. 我试着搜索范围,python-2.7,性能标签放在一起,什么都没找到(与python-2.x相同).

2. 如果我尝试以下:

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

   所以范围是固定的,我只测量运行时间x in i,我仍然在O(x)中得到运行时(假设a足够大).

3. n in xrange(n)O(n)中的运行时间也是如此.
4. 我找到了这篇文章,它问python 3的类似问题.我决定在python 3上测试相同的东西,它通过测试就像没什么.我为python 2感到难过.

Answer 1

rangePython 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

我应该x >= 0 and x < a再次使用并且永远不会在范围(a)中写入x吗？有没有更好的写作方式？

"不","它取决于","是".你不应该使用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)is False,而0 <= 1.5 < 5is True,可能不是你想要的.此外,使用range您可以使用比其他的步骤1,例如5 in range(4, 10, 2)是False,但同样也可以用纯数学来实现,例如作为(4 <= x < 10) and (x - 4 % 2 == 0).