我决定认输。 Here是我的代码。它应该在没有预处理的情况下为单个 block 512 位输入构建 SHA-2 算法的执行树。但是，我将它从 64 次迭代减少到 4 次迭代，因为遍历树从未完成 64 次迭代。即使在 4 次迭代中，它也会遍历 10,000 个节点——即使只分配了 1000 个节点，包括一堆常量，这些常量是叶子，甚至不计入遍历计数。另外，断言保证非周期性，如果是周期性的，它根本就不会返回，不会永远等待然后返回。
到底我对这段代码做了什么，导致它需要永远遍历这么小的非循环树？
最佳答案
嗯，这是意料之中的。树可能以非常紧凑的方式存储，但它有很多很多重复的部分。它非常大。
例如，考虑这个序列:
auto s0 = la.rotate(2) ^ la.rotate(13) ^ la.rotate(22);
现在 s0 树下面有三个原始的 la 表达式。
auto t2 = s0 + maj;
... 那棵树进入 t2...
la = t1 + t2;
... 在循环结束时再次出现在 la 中。因此，la 现在(至少)有三个对前一次迭代的 la 树的引用。下一次迭代将再次将其复制三次。一遍又一遍。由此我们可以得出最终树中原始 la 的 3^64 个实例的下限(即使存储中只存在一个)。 3^64 是 3.43368382 × 10^30，即大约 3 gazillions。
树的生成采用简单的方法，只重用子树。另一方面，遍历函数最终会遍历同一个子树很多很多次。
关于c++ - 无法遍历树 - 节点被重新遍历了很多次但仍然是非循环的，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10633245/