为什么 Collatz 链的无碰撞子链的记忆比没有记忆慢？

Question

我编写了一个程序来对两种查找 “小于某个界限的整数的最长 Collatz 链”的方法进行基准测试。

第一种方法是使用“回溯记忆”，它跟踪当前链从开始到哈希 table 冲突（在堆栈中），然后将所有值弹出到哈希 table （增加链长度值）。

第二种方法是使用更简单的记忆，只记忆链的起始值。

令我惊讶和困惑的是，在第一次碰撞之前记忆整个子链的算法始终比只记忆起始值的算法慢。

我想知道这是否是由于以下因素之一造成的：

Python 使用堆栈真的很慢吗？足以抵消性能收获
我的code/algorithm不好吗？
从统计学上讲，随着整数变大，重新访问以前的非记忆元素所花费的时间计算出的 Collatz chains/sub-chains 是渐近最小的，以由于从堆栈中弹出元素而导致的任何开销根本不值得获得收益？

简而言之，我想知道这个意想不到的结果是由于语言、代码还是数学（即 Collatz 的统计）造成的。

import time

def results(backtrackMemoization, start, maxChainValue, collatzDict):
  print()
  print(("with " if backtrackMemoization else "without ") + "backtracking memoization")
  print("length of " + str(collatzDict[maxChainValue[0]]) + " found for n = " + str(maxChainValue[0]))
  print("computed in " + str(round(time.time() - start, 3)) + " seconds")

def collatz(backtrackMemoization, start, maxChainValue, collatzDict):
  for target in range(1, maxNum):
    n = target
    if (backtrackMemoization):
      stack = []
    else:
      length = 0

    while (n not in collatzDict):
      if (backtrackMemoization):
        stack.append(n)
      else:
        length = length + 1
      if (n % 2):
        n = 3 * n + 1
      else:
        n = n // 2
    
    if (backtrackMemoization):
      additionalLength = 1
      while (len(stack) > 0):
        collatzDict[stack.pop()] = collatzDict[n] + additionalLength
        additionalLength = additionalLength + 1
    else:
      collatzDict[target] = collatzDict[n] + length

    if (collatzDict[target] > collatzDict[maxChainValue[0]]):
      maxChainValue[0] = target

def benchmarkAlgo(maxNum, backtrackMemoization):
  start = time.time()
  maxChainValue = [1]
  collatzDict = {1:0}
  
  collatz(backtrackMemoization, start, maxChainValue, collatzDict)
  
  results(backtrackMemoization, start, maxChainValue, collatzDict)

try:
  maxNum = int(input("enter upper bound> "))
  print("setting upper bound to " + str(maxNum))
except:
  maxNum = 100000
  print("defaulting upper bound to " + str(maxNum))

benchmarkAlgo(maxNum, True)
benchmarkAlgo(maxNum, False)

Answer 1

您的代码中存在权衡。如果没有回溯记忆，字典查找的遗漏次数将是使用它时的两倍。例如，如果 maxNum = 1,000,000 那么错过字典查找的次数是

没有回溯记忆：5,226,259
带回溯记忆：2,168,610

另一方面，通过回溯记忆，您正在构建一个更大的字典，因为您不仅要为目标值收集链的长度，还要为在链中间遇到的任何值收集链的长度。这是 maxNum = 1,000,000 的 collatzDict 的最终长度：

没有回溯记忆：999,999
带回溯记忆：2,168,611

多次写入此字典、从堆栈中弹出所有这些附加值等都会产生成本。最终，这种成本似乎超过了减少字典查找未命中的好处。在我的测试中，带回溯记忆的代码运行慢了大约 20%。

可以优化回溯记忆，以保持字典查找未命中率低，同时降低构建字典的成本：

让堆栈由元组组成 (n, i) 其中 n 与您的代码中一样， i 是到目前为止遍历的链的长度（即 i 在 while 循环的每次迭代中递增）。这样的元组只有在n < maxNum时才会入栈。此外，在找到字典中已有的值之前，请跟踪整个链的长度（即 while 循环的迭代总数）。
以这种方式收集的信息可以让您从放在堆栈上的元组中构造新的字典条目。

这样得到的字典和没有回溯记忆的字典完全一样，但是会以更高效的方式构建，因为第一个键n会被添加遭遇。出于这个原因，字典查找未命中率仍然比没有回溯记忆时低得多。这是我在 maxNum = 1,000,000:

中获得的失误数

没有回溯记忆：5,226,259
带回溯记忆：2,168,610
经过优化的回溯记忆：2,355,035

对于较大的 maxNum 值，优化代码应该运行比没有回溯记忆更快。在我的测试中，maxNum >= 1,000,000 .

的速度提高了大约 25%

为什么 Collatz 链的无碰撞子链的记忆比没有记忆慢？

Why is memoization of collision-free sub-chains of Collatz chains slower than without memoization?

python

stack

memoization

collatz

为什么 Collat​​z 链的无碰撞子链的记忆比没有记忆慢？

Why is memoization of collision-free sub-chains of Collatz chains slower than without memoization?

python

stack

memoization

collatz

为什么 Collatz 链的无碰撞子链的记忆比没有记忆慢？