LeetCode第5题中C++比Python快50倍的原因探究

I'm practicing LeetCode Problem 5 (Longest Palindromic Substring) and confused by the huge runtime difference between C++ (~20ms) and Python (~1000ms). I know Python, as an interpreted language, generally has lower performance than C++, but this time C++ is 50x faster than Python, which exceeds my expectations. Since both programs use exactly the same algorithm, the difference doesn't come from the algorithm itself. Could this huge performance gap be caused by the different string implementation mechanisms of C++ and Python?

C++ Code #

class Solution {
public:
    string longestPalindrome(string s) {
        if(s.size() == 0) return "";
        int length = 1, index = 0, subOddLength = 1, subEvenLength = 1, subLength = 1;
        for(int i = 1; i < s.size(); ++i){
            subOddLength = palindromeLength(s, i, i);
            subEvenLength = palindromeLength(s, i - 1, i);
            subLength = max(subOddLength, subEvenLength);
            if(subLength > length){
                length = subLength;
                index = i - subLength / 2;
            }
        }
        return s.substr(index, length);
    }
private:
    int palindromeLength(const string &s, int l, int r){
        int n = s.size();
        while(l >= 0 && r < n){
            if(s[l] != s[r]) break;
            l--;
            r++;
        }
        l++;
        r--;
        return r - l + 1;
    }
};

Python Code #

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def palindrome_length(l, r):
            while l >= 0 and r < len(s):
                if s[l] != s[r]:
                    break;
                l -= 1;
                r += 1
            l += 1;
            r -= 1
            return r - l + 1
        length, index = 1, 0
        for i in range(1, len(s)):
            odd_len = palindrome_length(i, i)
            even_len = palindrome_length(i - 1, i)
            sub_len = max(odd_len, even_len)
            if sub_len > length:
                length, index = sub_len, i - sub_len // 2
        return s[index : index + length]

Great question! That 50x performance gap you're observing is absolutely rooted in fundamental differences between how C++ and Python handle strings, execution, and low-level operations—let's break down the key factors:

1. String Representation & Access Overhead #

• C++ std::string: At its core, it's a contiguous array of char bytes stored directly in memory. Accessing s[l] or s[r] is a raw memory lookup with near-zero overhead. In release mode, the compiler often optimizes away bounds checking, making these operations even faster.
• Python str: Python strings are immutable Unicode objects. Each character is a Unicode code point, and accessing s[l] involves multiple steps:
  • Validating that l is within the string's bounds (Python doesn't skip this check)
  • Dereferencing the string object to access its underlying Unicode data
  • Wrapping the raw data into a Python str object for comparison
    These extra steps add up quickly, especially in tight loops like your palindrome_length function where you're accessing characters hundreds of times.

2. Compiled vs. Interpreted Execution #

• C++: Your code is compiled to native machine code before running. The compiler performs aggressive optimizations:
  • It can inline the palindromeLength function, eliminating the overhead of function calls entirely
  • Optimize loop conditions and memory access patterns to align with CPU capabilities
  • Remove redundant operations (like the final l++/r-- if it can calculate the length directly)
• Python: Python is an interpreted language—every line of code is parsed and executed at runtime. Function calls in Python have significant overhead compared to C++, and loop iterations are handled by the interpreter rather than raw CPU instructions. This overhead is amplified in functions like palindrome_length that get called repeatedly.

3. Loop Efficiency #

Tight loops are where Python's performance really lags behind compiled languages. For each iteration of your while loop in palindrome_length:

• Python has to evaluate the loop condition (l >=0 and r < len(s)), which includes calling len(s) (even though it's optimized, it still has overhead)
• The comparison s[l] != s[r] isn't a simple byte comparison—it's a Unicode code point comparison with all the associated object overhead
• Incrementing/decrementing l and r involves modifying Python integer objects (which are immutable, so each change creates a new object)

In C++, all these operations are reduced to single machine instructions that run in nanoseconds.

Why 50x? #

All these factors compound: string access overhead, interpreted loop overhead, and function call overhead add up to create that massive gap. LeetCode's timing might have slight variance, but a 50x difference here is completely normal given the fundamental differences between the two languages.

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