In python-3.x /questions/tagged/python-3.x a range(..)
是一个对象,它不构造列表。如果您执行成员检查int
作为项目,那么它可以非常快地做到这一点。该算法有点复杂,因为有正向步骤和反向步骤。你可以查一下[GitHub] https://github.com/python/cpython/blob/3.7/Objects/rangeobject.c#L338。具有正步数的简单算法(c > 0
) for x in range(a, b, c)
是这样的:
x ≥ a &楔形; x .
对于负步数 (c < 0
) 非常相似:
x≤a&楔形; x > b &楔形; mod(x-a, c) = 0.
如果我们考虑进行比较O(1)并计算模数,它是O(1)算法。实际上,对于巨大的数字,它会按数字的位数进行缩放,因此它是O(log n)算法。
然而这仅适用于int
s。事实上,如果你使用float
s, complex
、其他数值或非数值类型,则不执行上述计算。然后它将回退到迭代range(..)
目的。这当然会花费相当长的时间。如果您有一百万个元素的范围,它将迭代所有这些元素并最终到达范围的末尾,并返回False
,或找到匹配项,然后返回True
。将来,也许可以为某些数字类型实现一些额外的功能,但通常不能这样做,因为您可以使用不同工作方式的相等运算来定义自己的数字类型。
In python-2.x /questions/tagged/python-2.x, range(..)
是一个返回列表的函数。的确:
>>> range(15)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]
>>> type(range(15))
<type 'list'>
为了检查某个元素是否是列表的成员,它将迭代列表,并检查所有项目的相等性,直到找到相等的元素,或者列表已耗尽。如果我们考虑检查两项是否等于常数时间,那么这需要线性时间O(n)。实际上,对于巨大的数字,检查两个数字是否相等,与“位数”成线性比例,因此O(log m) with m该数字的值。
python-2.x /questions/tagged/python-2.x has an xrange(..)
也反对,但这不会使用上述演示的技巧检查成员资格。