Why my Python recursive solution (with memorization) is much faster than non-recursive one?


  • 1
    D

    Below is my recursive solution with running time ~160 ms

    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            def _dp(x, y):
                if distance[x][y] is None:
                    if x == 0:
                        # boundary condition
                        distance[x][y] = y
                    elif y == 0:
                        # boundary condition
                        distance[x][y] = x
                    elif word1[x-1] == word2[y-1]:
                        distance[x][y] = _dp(x-1, y-1)
                    else:
                        distance[x][y] = min(_dp(x-1, y), _dp(x, y-1), _dp(x-1, y-1)) + 1
    
                return distance[x][y]
    
            len1, len2 = len(word1), len(word2)
            distance = [[None] * (len2+1) for _ in range(len1+1)]
            return _dp(len1, len2)
    

    And this is the standard DP version, with running time 268 ms. Why the recursive solution is much faster than the non-recursive one?

    class Solution(object):
        def minDistance(self, word1, word2):
            """
            :type word1: str
            :type word2: str
            :rtype: int
            """
            len1, len2 = len(word1) + 1, len(word2) + 1
            distance = [[0] * len2 for _ in range(len1)]
            '''
            Define D(i, j) as the edit distance between W1[0 : i] and W2 [0 : j],
            i.e., the first i/j characters of W1 and W2, respectively
            The edit distance between W1 and W2 is thus D(n, m)        
            Base conditions:
                D(i, 0) = i; D(0, j) = j
            DP formula:
                               / delete:  D(i-1, j) + 1
                D(i, j) = min -- insert:  D(i, j-1) + 1
                               \ replace: D(i-1, j-1) + 0, if W1[i] == W2[j]
                                                        1, if W1[i] != W2[j]
            '''
            for x in xrange(1, len1):
                distance[x][0] = x
            for y in xrange(1, len2):
                distance[0][y] = y
            for x in xrange(1, len1):
                for y in xrange(1, len2):
                    if word1[x-1] == word2[y-1]:
                        distance[x][y] = distance[x-1][y-1]
                    else:
                        distance[x][y] = min(distance[x-1][y], distance[x][y-1], distance[x-1][y-1]) + 1
            return distance[-1][-1]

  • 1
    A

    Initially I was surprised because function calls are expensive. However, the recursive algorithm does not need to visit the entire array to arrive at a solution, it only visits the paths that are relevant to it depending on whether letters being compared are equal to each other or not. I assume this is what makes it much faster.

    As an example, I ran your code with the following input:

    "abcd"
    "dd"
    

    I printed out the final state of the edit distance array and it's the following:

    [[0, 1, None], [1, 1, None], [2, 2, None], [3, 3, None], [None, None, 3]]
    

    As you can see many entries are None, indicating that the algorithm didn't visit them. With longer sequences the benefits would be even greater.

    In the DP case, you always loop through the entire distance array.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.