Str 切片后操作的 Runtime 比切片后重新赋值的 Runtime 慢的多,为什么?
版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。
我测试了两个代码: 代码 1:
def check1(x):
y = str(x)[::-1]
return str(x)== y
运行结果:
11509/11509 cases passed (52 ms)
Your runtime beats 99.12 % of python3 submissions
Your memory usage beats 99.64 % of python3 submissions (12.7 MB)
代码 2:
def check2(x):
return str(x)==str(x)[::-1]
运行结果:
11509/11509 cases passed (92 ms)
Your runtime beats 30.82 % of python3 submissions
Your memory usage beats 99.64 % of python3 submissions (12.7 MB)
两个函数分别在 leetcode 上运行时间分别是 32ms 和 36ms。
我测了两个函数的调用时间分别时 0.00705718994140625、0.009938955307006836。
@Jason990420,帮我更正数据,两个函数本地调用时间相差不大,都是 0.006ms 左右
但是在 leetcode 上提交代码,测试案例为何 runtime 差距这么大呢 Your runtime beats 99.12 % of python3 submissions VS Your runtime beats 30.82 % of python3 submissions
理论分析 切片的原理官方文档 - 内置函数 slice: 对原 Itertable 进行 O (n) 时间复杂度的迭代转换成新(地址 id 不同)的一个 list。
切片操作的源码:https://hg.python.org/cpython/file/2.7/Obj...
查阅 python 中 list 的官方代码哦,我们知道 CPython 中切片一般按照三个模式:
前两种方式是按照 memoryviews to get zero-copy views of the original bytes data 使用类似字节的对象,用缓存去避免赋值。
完整切片,例如 mystr [:]:返回对完全相同的 str 的引用 (不仅仅是共享数据,相同的实际对象,mystr 是 mystr [:], 因为 str 是不可变的,所以这样做没有风险) 零长度切片和 (依赖于实现) 缓存长度为 1 个切片;单个字符串是空的字符串 (mystr [1:1] 是 mystr [2:2] 是”), 长度为 1 的低序数字符串也是缓存的单例 (在 CPython 3.5.0 上,它看起来像所有字符都可表示在 latin-1 中,即范围 (256) 中的 Unicode 序数,被缓存)
所有其他切片:切片的 str 在创建时复制,此后与原始 str 无关 但是我们使用的时 [::-1] 属于重新赋值,创建 id 不同的一个对象。
我们使用 python 的 dis 内置函数来分别看一些运行的过程:
import dis
dis.dis(check1)
# dis.dis(check2)
方法 check1 的运行结果 : True 20 0 LOAD_GLOBAL 0 (str) 2 LOAD_FAST 0 (x) 4 CALL_FUNCTION 1 6 LOAD_CONST 0 (None) 8 LOAD_CONST 0 (None) 10 LOAD_CONST 1 (-1) 12 BUILD_SLICE 3 14 BINARY_SUBSCR 16 STORE_FAST 1 (y)
21 18 LOAD_GLOBAL 0 (str) 20 LOAD_FAST 0 (x) 22 CALL_FUNCTION 1 24 LOAD_FAST 1 (y) 26 COMPARE_OP 2 (==) 28 RETURN_VALUE
方法 check2 的运行结果:
True 23 0 LOAD_GLOBAL 0 (str) 2 LOAD_FAST 0 (x) 4 CALL_FUNCTION 1 6 LOAD_GLOBAL 0 (str) 8 LOAD_FAST 0 (x) 10 CALL_FUNCTION 1 12 LOAD_CONST 0 (None) 14 LOAD_CONST 0 (None) 16 LOAD_CONST 1 (-1) 18 BUILD_SLICE 3 20 BINARY_SUBSCR 22 COMPARE_OP 2 (==) 24 RETURN_VALUE