python 中字典的效率：

Question

在下面的递归函数中，我在 python 中应用了一些记忆技术，将以前的计算值保存在字典中，理论上应该具有 O(1) 的存储和检索。但是，使用记忆化时的执行时间大约是简单递归的三倍。

在下面的两段代码中，第二段代码执行时间如此长的可能原因是什么？我是不是用错了词典？

简单的递归函数：

import time

def deletion_distance(str1, str2):
  if str1 is "":
    return len(str2)
  elif str2 is "":
    return len(str1)
  else:
    if str1[len(str1) - 1] == str2[len(str2) - 1]:
      return deletion_distance(str1[:-1],str2[:-1])
    else:
      return 1 + min(deletion_distance(str1, str2[:-1]),deletion_distance(str1[:-1],str2))

str1 = "dragonified"
str2 = "infinitezimal"

start = time.time()
for i in range(0,2):
    deletion_distance(str1,str2)
end = time.time()

print((end - start) / 2)

使用字典进行记忆的动态编程：

import time

def deletion_distance(str1, str2):
  global aux_dict

  if str1 is "":
    return len(str2)
  elif str2 is "":
    return len(str1)
  else:
    if str1[len(str1) - 1] == str2[len(str2) - 1]:
      if "1"+str1[:-1]+"2"+str2[:-1] in aux_dict:
        return aux_dict["1"+str1[:-1]+"2"+str2[:-1]]
      else:
        aux_dict["1"+str1[:-1]+"2"+str2[:-1]] = deletion_distance(str1[:-1],str2[:-1])
        return aux_dict["1"+str1[:-1]+"2"+str2[:-1]]
    else:

      return 1 + min(
        aux_dict["1"+str1+"2"+str2[:-1]] if "1"+str1+"2"+str2[:-1] in aux_dict else deletion_distance(str1, str2[:-1]),
        aux_dict["1"+str1[:-1]+"2"+str2] if "1"+str1[:-1]+"2"+str2 in aux_dict else deletion_distance(str1[:-1],str2))

aux_dict = {}      
str1 = "dragonified"
str2 = "infinitezimal"

start = time.time()
for i in range(0,2):
    deletion_distance(str1,str2)
end = time.time()

print((end - start) / 2)

两个函数都计算两个字符串的删除距离（PRAMP.COM问题），这只是两个字符串的最少字符数，从两个字符串中删除，使它们变得相同。

Answer 1

您根本不使用字典，因为您为每个函数调用使用一个新的空字典。

aux_dict = {}

def deletion_distance(str1, str2):
    if (str1, str2) in aux_dict:
        return aux_dict[str1, str2]
    if not str1:
        return len(str2)
    elif not str2:
        return len(str1)
    elif str1[-1] == str2[-1]:
        result = deletion_distance(str1[:-1],str2[:-1])
    else:
        result = 1 + min(
            deletion_distance(str1, str2[:-1]),
            deletion_distance(str1[:-1], str2),
        )
    aux_dict[str1, str2] = result
    return result

这将两个示例字符串的调用量从 1685178 减少到 268，因此缓存版本快了 3000 倍。

编辑：在你更新的问题中，你仍然没有正确使用字典。只有在两个字符串的最后一个字符相等的情况下，才会使用字典。

python 中字典的效率：

Efficiency of dictionaries in python:

python

recursion

dictionary

memoization

dynamic-programming