Python怎么可能花更多的时间进行一个循环而不是多个循环呢？

Question

我有两个代码可以完成类似的任务：

class Solution1:
    def f(self, s: str) -> bool:
        def calculate(s, i, digit, length, maxi):
            count = 1
            while i < length:
                if s[i] == digit: count += 1
                else: break
                i += 1
            
            return max(maxi, count), i

        
        maxi1 = 0
        maxi0 = 0
        length = len(s)
        i = 0
        while i<length:
            if s[i] == '0': maxi0, i = calculate(s,i,'0', length, maxi0)
            else: maxi1, i = calculate(s,i,'1', length, maxi1)
        
        return maxi1 > maxi0


class Solution3:
    def f(self, s: str) -> bool:
        s1 = s.split('0')
        s0 = s.split('1')
        r1 = max([len(i) for i in s1])
        r0 = max([len(i) for i in s0])
        return r1>r0

使用%timeit运行以下代码，

x = '1100011111100111010111'*10

sol1 = Solution1().f
sol3 = Solution3().f

% timeit -r 30 -n 3000 sol1(x,)
% timeit -r 30 -n 3000 sol3(x,)

它给了我

3000 loops, best of 30: 77.5 µs per loop
3000 loops, best of 30: 29.6 µs per loop

第二个代码花费了几乎一半时间的，这是很奇怪的。

split()在循环上迭代一次，并使用了两次，然后len对每个子部分使用O(N)时间，并对每个子字符串调用，这意味着总共有O(N)时间，在此基础上，max对这两个子字符串的工作原理完全相同。有人能解释一下这是怎么回事吗？是cpython在引擎盖下为内置函数做了什么吗？

令我惊讶的是：

class Solution4:
    def f(self, s: str) -> bool:
        return len(max(s.split('0'))) > len(max(s.split('1')))

如果在+ split() twice上使用max，则会占用strings 7x较少的时间。

Answer 1

kindall的注释中已经给出了一个代码比另一个代码慢的问题的答案。再一次，为了完整起见：

内置函数(如max() )是用C编写的，比等效的Python代码快得多。然后，您的解决方案示例并不严格地执行其他两个字符串的操作(它检查最大的字符串，而不是最大长度的字符串)。在这种情况下，它们在功能上是等价的(因为一个由五个零组成的字符串“大于”一个由三个字符串组成的字符串)，但是比较两个字符串比两个函数调用和它们的结果比较要快(如您所知)。-金德尔

有两种方法可以让事情做得更快：

• 优化了使用的方法
• 的代码，选择了完全不同的方法

因此，与其怀疑使用其他函数/方法/模块来做相同的事情会显著缩短执行时间，不如让我们惊讶地发现，选择另一种方法/方法来解决同样的问题也能做到这一点。下面是这样的另一种方法的代码，并解释了解决方案背后的思想核心：

对于寻找解决方案，通常最明显的事情是不去想的。在这里讨论同样的任务时，Counting longest occurrence of repeated sequence in Python竟然没有提到下面提供的方法。

“解决方案5”调用的方法则相反，即在生成的字符串所有子字符串列表中搜索最大子字符串长度。

它搜索迭代递增子字符串长度的子字符串的第一次出现。使用高度优化的子字符串搜索和只查找它的第一次出现会导致与解决方案4相比，在字符串较长的情况下花费更少的时间，对于非常长的字符串(对于非常短的字符串，f4()似乎更快)。

因此，让我们将最快的解决方案f4()与解决相同问题的另一种方法f5()进行比较。

class Solution4:
    def f4(self, s: str) -> bool:
        return len(max(s.split('0'))) > len(max(s.split('1')))

def f4(s: str) -> bool: # cut out time for class overhead
    return len(max(s.split('0'))) > len(max(s.split('1')))

def f5(s):
    foundMax0=False; foundMax1=False
    for l in range(1,len(s)+1):
        if not foundMax0: 
            # print(f'{l=}, {s.find("0"*l)=}') 
            if s.find("0"*l) is -1: 
                max0=l-1; foundMax0=True
        if not foundMax1: 
            # print(f'{l=}, {s.find("1"*l)=}') 
            if s.find("1"*l) is -1: 
                max1=l-1; foundMax1=True
        if foundMax0 and foundMax1:
            break
    return max1 > max0

from time import perf_counter as T
s = '1100011111100111010111'*10 # *1000
sT=T(); sol4 =Solution4().f4(s); eT=T(); print(f'{eT-sT:11.8f}')
sT=T(); sol4f=            f4(s); eT=T(); print(f'{eT-sT:11.8f}')
sT=T(); sol5 =            f5(s); eT=T(); print(f'{eT-sT:11.8f}')
print( f5(s) )
# Times vary, but the last solution is more than ten times faster than the up to now fastest one on a large string and still 1.5 times faster on a small one:  
# s*10   : 0.00002643
# s*10   : 0.00001687
# s*10   : 0.00000914
# s*1000 : 0.00116592
# s*1000 : 0.00104705
# s*1000 : 0.00007862

上面的代码有很大的优化空间，例如，从长度2开始，再按2步进行，但是这里的消息是另一条：

在考虑循环的时间安排时，考虑到更改这些循环所使用的数据也会对最终运行时产生重大影响。