Python实现LeetCode无重复子串性能远低于C++，该如何优化？

题目说明 #

给定一个字符串s，找出其中不含有重复字符的最长子串的长度。
题目链接：最长无重复字符子串

测试背景 #

为了验证C++和Python之间的性能差距，使用相同逻辑分别编写了两个语言版本的题解代码，实测性能对比如下：

原有C++实现代码 #

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int max_count=0;
        int k=1;
        int i=0;
        int j=0;
        bool visited[256];
        memset(visited,false,256);
        int n=s.size();
        
        while(k<=n && i<n && j<n){
            /*for(int l=i;l<=j;l++) cout << s[l];
            cout << endl;*/
            
            if(visited[int(s[j])]){
                memset(visited,false,256);
                k=1;
                i++;
                j=i+k-1;
            }else{
                if (max_count<k) max_count=k;
                visited[int(s[j])]=true;
                k++;
                j++;
            }
        }
        return max_count;
    }
};

原有Python实现代码 #

class Solution:
    def lengthOfLongestSubstring(self, a: str) -> int:
        
        #apply sliding window for k=0,1,2,..,n until repetition is found for a substring
        k=1 #wndow length
        i=0 #starting indx of substring
        j=0 #ending indx of substring
        init_visited=[False]*256
        visited=init_visited[:]
        max_count=0
        n=len(a)
        
        while k<=n and j<n and i<n:       
            #print(k,i,j)
            #print(a[i:j+1])
            if visited[ord(a[j])]:
                visited = init_visited[:]
                i+=1
                k=1
                j=i+k-1
            else:
                visited[ord(a[j])]=True
                max_count=max(max_count,k)
                
                k+=1
                j+=1
        
        return max_count

Python代码优化点 #

• 优化核心逻辑，避免全量数组拷贝：原有逻辑每次遇到重复字符就全量重置/拷贝256位的标记数组，Python中列表拷贝的开销远高于C++的memset操作。可以改用标准滑动窗口思路，用数组记录每个字符最后出现的位置，遇到重复时直接移动左指针到重复字符上一次出现位置的下一位，不需要重置整个标记数组，既把时间复杂度从最坏O(n²)降到了O(n)，也彻底避免了高频数组拷贝开销。
• 移除冗余变量：原有代码单独维护的窗口长度变量k可以直接用右指针-左指针+1计算，不需要额外做变量更新，减少操作开销。
• 用轻量结构替代普通列表：如果要保留原有标记数组的逻辑，可以用bytearray替代bool列表，bytearray的读写和重置效率都远高于普通列表，重置时直接执行visited[:] = b'\x00'*256即可，比切片拷贝快很多。
• 减少函数调用开销：可以把当前字符的ord计算结果先存到局部变量，避免重复调用ord函数，Python中函数调用的开销远高于原生变量读写。
• 优先使用局部变量：Python访问局部变量的速度远快于访问全局变量/对象属性，可以把len(a)、ord这类值和函数提前绑定到局部变量，进一步提升执行速度。

优化后代码示例 #

class Solution:
    def lengthOfLongestSubstring(self, a: str) -> int:
        # 记录每个ASCII字符最后出现的位置，初始值设为-1
        last_pos = [-1] * 256
        max_len = 0
        left = 0
        n = len(a)
        ord_func = ord
        for right in range(n):
            cur_ord = ord_func(a[right])
            # 当前字符在窗口内存在重复，移动左指针到重复位置的下一位
            if last_pos[cur_ord] >= left:
                left = last_pos[cur_ord] + 1
            last_pos[cur_ord] = right
            cur_len = right - left + 1
            if cur_len > max_len:
                max_len = cur_len
        return max_len

内容的提问来源于stack exchange，提问作者VerilogCoder