React的“差异化”启发式算法背后的动机是什么？

Question

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

引用：

有一些通用的解决方案来解决生成将一个树转换为另一个树所需的最小操作数量的算法问题。然而，现代算法的复杂度大约为O(n^3)，其中n是树中元素的数量。

1.为什么将一棵树转换成另一棵树的复杂度是O(n^3)?

如果我们在React中使用它，显示1000个元素将需要进行大约10亿次比较。这太昂贵了。相反，React实现了一种基于两个假设的启发式O(n)算法:

- 两个不同类型的元素将产生不同的树。 - 开发人员可以通过key属性提示哪些子元素可能在不同的渲染之间保持稳定。

2.你能详细说明一下React实现中的启发式是什么吗？ 3.这些假设使其在平均情况下成为O(n)吗？

- Dennis Vash

---

O(n^3) 是一种最先进的复杂度，用于查找将一个树转换为另一个树所需的绝对最小差异的diff算法。React的算法没有这个特性，例如，它可能会生成更多操作来将一个树转换为另一个树，而不是最小所需操作。然而，它生成时间较短，并且在平均情况下可能是最优的。 - undefined

在“实际应用场景”中，它的时间复杂度是O(n)，但它也可能使一棵树的转换变得比O(n^3)还要糟糕？ - undefined

不，这意味着差异算法需要线性时间（基于节点数量）进行转换，但通常情况下，这种转换会有更多的操作。所以在通常情况下，如果不需要或者没有任何区别来找到最小操作量，它可以是最优的。 - undefined

Answer 1

React的diff算法有很好的理由，但文件中所述的“动机”并不足以成为真相。首先，虽然一个最优的“树形差异”需要O（N3）时间，但“树形差异”算法并不是React实际所做的单一最佳选择，实际上根本不适合React的渲染过程。这主要是因为，在最坏的情况下，渲染react组件会产生一个列表（而不是树），需要将其与预先存在的组件列表匹配起来。在执行差异之前，没有新的树，因为需要将新列表与现有树匹配，以决定是否重新渲染子元素。因此，在匹配这些列表时，我们可能会将React diff与标准的最长公共子序列算法进行比较，这是一种O（N2）算法。这仍然相当慢，因为LCS如果像React diff那样快，它肯定在渲染过程中占据一席之地。但是，LCS不仅速度慢，而且还不能正确地处理事情。当React将新元素列表与旧树匹配时，它会决定每个元素是新组件还是对预先存在的组件的prop更新。LCS可以找到元素类型的最大可能匹配，但最大可能匹配不一定是开发人员想要的。因此，LCS（或树形差异，如果您确实想推动该点）的问题不仅在于它很慢，而且在于它很慢并且提供的答案仍然只是对开发人员意图的猜测。当它们仍然会犯错误时，慢算法是不值得的。还有许多其他快速算法，React开发人员可以使用这些算法在大多数情况下更准确，但问题是“值得吗？”通常的答案是“不”，因为没有算法可以很好地猜测开发人员的意图，并且猜测开发人员的意图实际上是不必要的。当对开发人员很重要时，他的新元素与现有组件正确匹配，以便他们不必重新渲染时，开发人员应确保这是正确的。这很容易-他只需在呈现列表时提供关键道具即可。开发人员在呈现列表时几乎总是应该这样做，以便组件匹配可以是完美的，他们不必接受任何猜测。

如果您在必须使用key props以使匹配无歧义的地方没有放置它们，则React将产生警告，这比更好的差异要有用得多。当您看到它时，应通过添加适当的key props来修复组件，然后匹配将是完美的，不需要担心其他算法可以在编写不良组件时做得更好。

最初的回答：

如果您没有在必须使用key props以使匹配无歧义的地方放置它们，React会发出警告。这比更好的差异更有帮助。当您看到此警告时，请通过添加适当的key props来修复组件。然后，匹配将是完美的。不必担心其他算法可以在编写不良组件时做得更好。

- Matt Timmermans

Answer 2

• 只基于假设进行转换

• 不同类型的两个元素将产生不同的树。
• 开发人员可以通过键属性提示哪些子元素在不同的渲染中可能是稳定的。

如果键值不变或没有添加新元素，则整个树不会重新渲染

• 这种管理是基于经验的假设，因此是启发式的

- Mosè Raguzzini

Answer 3

目前最先进的差异算法在查找将一棵树转换为另一棵树所需的最小变换操作数量时，其复杂度为O(n^3)（n为节点数）。但正如React文档所提到的，这种复杂度可能过高，在通常情况下并不需要。

这就是为什么React使用一种启发式方法，平均时间复杂度为O(n)（线性时间）。

1. 不同类型的两个元素将产生不同的树。
2. 开发人员可以通过key属性提示哪些子元素在不同渲染之间可能保持稳定。

启发式方法意味着在某些情况下，差异可能会产生比必要的变换更多的变换（总体上并不是最优解），然而在通常和经常使用的情况下，两种算法（最优解和启发式方法）可以产生完全相同的结果（启发式方法生成时间更短），或者两种算法之间的差异对性能影响很小。

附注：

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

为了回答这个问题，我们需要研究最先进的算法。但总体来说，答案是需要进行许多比较（节点与其子节点之间的比较），以找到所需的最小转换次数。

- Nikos M.