Why is this list comprehension slower than initializing conditionally using a for loop in Python?-CodePudding

Why is initializing the diagonal in a 2d matrix using an external loop much faster than doing it in a list comprehension? I was using the list comprehension and I was getting time limit exceeded in Leetcode in a problem involving dynamic programming ( https://leetcode.com/problems/longest-palindromic-substring/ ). I thought my algorithm was wrong. Switching to an external loop solved it in half the time and my solution got accepted. Here is sample of my code with timing. The first one is 6 times slower than the second approach on my machine.

#super slow
from time import perf_counter
s=perf_counter()
dpArray=[[  True if i==j else False for j in range(1000)] for i in range(1000) ]
print(f"Initialized in {perf_counter() - s:0.4f} seconds")

#super fast
s=perf_counter()
dpArray=[[False]*1000 for i in range(1000) ]
for i in range(1000):
    dpArray[i][i]=True
print(f"Initialized diagonal in {perf_counter() - s:0.4f} seconds")

Execution:
Initialized in 0.0645 seconds
Initialized diagonal in 0.0095 seconds

Incase anyone is interested in the solution, here is the slow version, which barely passes. I had to make a few tweaks to avoid a TLE error:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[  True if i==j else False for j in range(len(s))] for i in range(len(s)) ]
        ans=s[0]
        for j in range(len(s)):
            for i in (range(j)):
                if s[i]==s[j] and (dp[i 1][j-1] or j==i 1):
                    dp[i][j]=True
                    if j-i 1>len(ans):
                        ans=s[i:j 1]
        return ans

Fast version:

class Solution:
    def longestPalindrome(self, s: str) -> str:
        dp = [[False]*len(s) for _ in range(len(s)) ]
        for i in range(len(s)):
            dp[i][i]=True
        ans=s[0]
        for j in range(len(s)):
            for i in range(j):
                if s[i]==s[j] and (dp[i 1][j-1] or j==i 1):
                    dp[i][j]=True
                    if j-i 1>len(ans):
                        ans=s[i:j 1]
        return ans

CodePudding user response：

The two methods are not equivalent. In the list comprehension you perform 1,000,000 comparisons (if i==j) while in the second one you don't have any comparisons at all.

Also [False]*1000 is a built-in shortcut and probably executes faster than a for loop.

Note that the time complexity for both methods is O(n^2), but that doesn't mean that one cannot be faster than the other.