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问题），即需要从两个字符串中删除的最少字符数，使得它们变成相同的字符串。

- user6412203

---

注意：如果未命中缓存的次数远大于命中缓存的次数，即大部分时间都在向字典中存储数据而非读取数据，则记忆化可能会导致性能变差而不是改善。 - Moses Koledoye

不要使用 is 来比较字符串。 - Daniel

是的，你做错了。aux_dict不能是一个局部变量。 - Robᵩ

这个函数被正确地进行了记忆化吗？你的函数调用每次都会创建一个新的空字典...我有什么遗漏吗？ - juanpa.arrivillaga

@Nelsão 因为这个。 - yinnonsanders

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倍。

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

- Daniel

---

没错。我已经在我的代码中修复了它，但第二个版本仍然较慢。我会在问题中进行修复。 - user6412203

在进行修改后，性能稍有提升但是仍然比常规递归慢了大约两倍（每个版本都使用了100000次循环）。 - user6412203