reactjs - React 的 "diffing"启发式算法背后的动机是什么？

Question

我的问题是关于 Motivation用于实现启发式 O(n) 算法。

There are some generic solutions to this algorithmic problem ofgenerating the minimum number of operations to transform one tree intoanother. However, the state of the art algorithms have a complexity inthe order of O(n^3) where n is the number of elements in the tree.

• 为什么将一棵树转换为另一棵树的复杂度为 O(n^3)？

If we used this in React, displaying 1000 elements would require inthe order of one billion comparisons. This is far too expensive.Instead, React implements a heuristic O(n) algorithm based on two assumptions:

• Two elements of different types will produce different trees.
• The developer can hint at which child elements may be stable across different renders with a key prop.

• 你能详细说明什么是heuristic吗？在 React 的实现中？
• 在一般情况下，这些假设是否使它成为 O(n)？

Answer 1

React 的 diff 算法之所以如此，有很好的理由，但记录的“动机”并没有足够的意义成为真实的事实。

首先，虽然最佳“树差异”确实需要 O(N³) 时间，但“树差异”算法并不是 React 实际所做的唯一最佳替代方案，并且事实上，will 根本不适合 React 的渲染过程。这主要是因为，在最坏的情况下，渲染一个 react 组件会产生一个 react 元素的列表(而不是树)，这些 react 元素需要与预先存在的列表相匹配组件。

执行 diff 时没有新树，因为新列表需要在呈现新元素的子元素之前与预先存在的树进行匹配。事实上，需要 diff 的结果来决定是否重新渲染子项。

所以...在匹配这些列表时，我们可能会将 React diff 与标准最长公共(public)子序列算法进行比较，后者是一种 O(N²) 算法。这仍然很慢，并且有一个性能参数需要提出。如果 LCS 和 React diff 一样快，那么它肯定会在渲染过程中占有一席之地。

但是，濒海战斗舰不仅速度慢，而且没有做正确的事情。当 React 将新元素列表与旧树进行匹配时，它会决定每个元素是一个新组件，还是只是对预先存在的组件的 prop 更新。 LCS 可以找到最大可能匹配的元素类型，但最大可能匹配不一定是开发人员想要。

因此，LCS(或树差异，如果你真的想强调这一点)的问题不仅在于它很慢，而且它很慢并且它提供的答案仍然是只是对开发人员意图的猜测。当算法仍然会出错时，速度慢的算法就不值得了。

虽然有很多其他快速算法，React 开发人员可以使用它们在大多数情况下会更准确，但问题是“它值得吗？”通常，答案是否定的，因为没有任何算法可以很好地猜测开发者的意图，而猜测开发者的意图实际上没有必要。

如果开发人员认为他的新元素与其先前存在的组件正确匹配以便它们不必重新呈现很重要，那么开发人员应该确保是这种情况。这非常简单——他只需要在呈现列表时提供关键 Prop 。开发人员在呈现列表时应该几乎总是这样做，以便组件匹配可以完美，并且他们不必满足于任何猜测。

如果您没有在需要使匹配明确的地方放置关键 Prop ，React 将发出警告，这比更好的差异更有帮助。当您看到它时，您应该通过添加适当的关键 Prop 来修复您的组件，然后匹配将是完美的，并且没有其他算法可以在编写糟糕的组件上做得更好。