Str 切片后操作的 Runtime 比切片后重新赋值的 Runtime 慢的多,为什么?

leetcode有一个判断str是否回文,测试代码

我测试了两个代码:

代码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)

具体内容看函数的文档:https://docs.python.org/zh-cn/3/library/di...

方法 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

感觉整体 check 的 io 操作更加繁琐啊,为什么会运行时间更少呢??🙃

文章!!首发于我的博客Stray_Camel(^U^)ノ~YO
Jason990420
最佳答案

这是我跑一千万次的时间, 好像和你的时间结果不一样. 测试环境会影响结果, 所以我把次数拉大, 结果应该会比较正确吧.

from datetime import datetime

def check1(x):
    y = str(x)[::-1]
    return str(x)== y

def check2(x):
        return str(x)==str(x)[::-1]

size = 10000000

def call(func):
    start_time = datetime.now()
    for i in range(size):
        result = func(123456789)
    print(datetime.now() - start_time,':',func.__name__)

call(check1)
call(check2)

Pyscripter 结果

0:00:07.303497 : check1
0:00:07.149908 : check2

DOS CMD 结果

0:00:06.854627 : check1
0:00:06.672187 : check2
4年前 评论
娃哈哈店长 (楼主) 4年前
娃哈哈店长 (楼主) 4年前
讨论数量: 2
Jason990420

这是我跑一千万次的时间, 好像和你的时间结果不一样. 测试环境会影响结果, 所以我把次数拉大, 结果应该会比较正确吧.

from datetime import datetime

def check1(x):
    y = str(x)[::-1]
    return str(x)== y

def check2(x):
        return str(x)==str(x)[::-1]

size = 10000000

def call(func):
    start_time = datetime.now()
    for i in range(size):
        result = func(123456789)
    print(datetime.now() - start_time,':',func.__name__)

call(check1)
call(check2)

Pyscripter 结果

0:00:07.303497 : check1
0:00:07.149908 : check2

DOS CMD 结果

0:00:06.854627 : check1
0:00:06.672187 : check2
4年前 评论
娃哈哈店长 (楼主) 4年前
娃哈哈店长 (楼主) 4年前

答案来自leetcode社区给我的回答:
再提交一次就会发现时间变了。python 的本身 overhead 比较大,出现波动很正常。第二个代码我又提交了一次是 40ms。👍

🙃不过有兴趣可以看一下这个文章:http://blog.kevmod.com/2016/07/why-is-pyth...

4年前 评论

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!