Python之range

我的图片 · 在线免费的图片处理工具

前言

简单记录一下 Python 中 range 相关内容,记录于此,方便自己查阅。重点是它为什么不占内存,以及成员判断为什么那么快。

正文

先把上面那句翻过来:range(10**12) 既不一次生成整数,也不占巨大内存。它压根不存整数,只存一条公式:start / stop / step。

基本格式

range(stop) 或 range(start, stop[, step]),前包后不包,step 可以是负数:

print(list(range(5)))
print(list(range(2, 6)))
print(list(range(0, 10, 2)))
print(list(range(5, 0, -1)))

输出:

[0, 1, 2, 3, 4]
[2, 3, 4, 5]
[0, 2, 4, 6, 8]
[5, 4, 3, 2, 1]

list(...) 只是把结果摊开看,平时 for i in range(n) 直接用,别手滑先转成列表。

不占内存:只存三个数

import sys

for n in [10, 10**6, 10**12, 10**20]:
    print(f"range({n}) 占内存:{sys.getsizeof(range(n))} 字节")

print("len :", len(range(10**12)))
print("末端:", range(10**12)[-1])

输出:

range(10) 占内存:48 字节
range(1000000) 占内存:48 字节
range(1000000000000) 占内存:48 字节
range(100000000000000000000) 占内存:48 字节
len : 1000000000000
末端: 999999999999

一律 48 字节(版本不同数字会变,恒定不变才是重点)。len() 是套公式算出来的,不用数;r[-1] 也是一套就出。真正撑内存的是展开:

import sys

print("list(range(10**6)) 占:", sys.getsizeof(list(range(10**6))), "字节")

try:
    print(len(range(10**20)))
except OverflowError as e:
    print("len 超大范围:", type(e).__name__, ":", e)

输出:

list(range(10**6)) 占: 8000056 字节
len 超大范围: OverflowError : Python int too large to convert to C ssize_t

10**12 个真 list() 出来内存直接爆,但那是 list 干的。最后那个 OverflowError 更说明它没在数数:对象照样造得出来、照样能取值,只是长度超出 C 整型的表示范围。

接回前面「列表是连续数组存引用」那节:list 至少还有一排引用要搬,range 连这排都没有,只有三个整数。

惰性,但不是生成器

r = range(10**12)

print("切片    :", r[5:10])
print("带步长  :", r[::2])
print("遍历两次:", list(r[:3]), list(r[:3]))

输出:

切片    : range(5, 10)
带步长  : range(0, 1000000000000, 2)
遍历两次: [0, 1, 2] [0, 1, 2]

切片完还是 range,能 len、能索引、能重复遍历——因为它随时按公式重算,不需要把值存下来。生成器则走一个丢一个:

g = (i for i in range(3))
r = range(3)

print("生成器两次:", list(g), list(g))
print("range 两次:", list(r), list(r))

输出:

生成器两次: [0, 1, 2] []
range 两次: [0, 1, 2] [0, 1, 2]
 rangelist生成器 / map
占内存恒定随长度涨恒定
len / 索引 / 切片✅✅❌
能重复遍历✅✅❌(走完就空)

一句话:range 是惰性序列,不是迭代器;前面笔记里 map / filter 返回的才是迭代器。

成员判断为什么 O(1)

接回上面那题。x in range(...) 对整数是直接套公式(判范围 + 整除步长),不是遍历也不是哈希:

r = range(10**12)

print("整数在不在 :", 999999999999 in r)
print("超出范围   :", 10**12 in r)
print("带步长 3   :", 3 in range(0, 10, 2))
print("浮点在不在 :", 9999.0 in range(10**5))
print("浮点不在   :", -1.0 in range(10**5))

输出:

整数在不在 : True
超出范围   : False
带步长 3   : False
浮点在不在 : True
浮点不在   : False

结果都对,但快慢差得离谱:实测 999999999 in range(10**9) 约 0.0004 秒(2000 次),而 -1.0 in range(10**5) 范围小一万倍却要 4.7 秒——换成非整数就退回逐个比。所以上轮说的「range 靠算术 O(1)」只对整数成立。

写法怎么判复杂度
整数 in range套公式O(1)
浮点 in range退回逐个比O(n)
in set / in dict哈希定位平均 O(1),最坏 O(n)
in list / tuple / dict.values()从头扫O(n)

小结

  • range 只存 start / stop / step,恒定几十字节,不生成任何整数
  • 占内存的是 list(range(n)) 或真的把循环走完
  • 能 len、索引、切片、重复遍历 → 惰性序列,不是生成器
  • 整数 in 靠公式 O(1),浮点退回线性;len 超大范围会 OverflowError
  • 前包后不包,step 可负

一句话版:range 不是「一筐数」,是「一条算数的公式」;要值现算,不算就不占地方。

参考文章

  1. AI
  2. Python 文档

暂无评论

none
暂无评论...