为什么 findAncestorWidgetOfExactType 是 O(N) 而 dependOnInheritedWidgetOfExactType 是 O(1)
Why findAncestorWidgetOfExactType is O(N) and dependOnInheritedWidgetOfExactType is O(1)
在 Flutter 中有两个函数：
- findAncestorWidgetOfExactType
- dependOnInheritedWidgetOfExactType
在文档中他们说：findAncestorWidgetOfExactType 相对昂贵（O(N) 在树的深度）。
和 dependOnInheritedWidgetOfExactType 是 O(1) 有一个小常数因子。
谁能解释为什么？为什么第一个比另一个贵？
谢谢
要回答这个问题并理解为什么这两种方法在时间复杂度上存在差异，我们首先需要澄清两件事：
1-什么是线性搜索？
Linear search (known as sequential search) is an algorithm for finding
a target value within a list. It sequentially checks each element of
the list for the target value until a match is found or until all the
elements have been searched.
简而言之，O(1) 意味着它需要一个常数时间，（例如 10 纳秒）。
另一方面，O(N) 意味着它花费的时间与集合的大小成线性关系，因此两倍大小的集合将花费两倍的时间。您可能不想将一百万个对象放入其中一个。
因此 ( findAncestorWidgetOfExactType )
文档中的提示
"Only call this method if the distance from this widget to the desired
ancestor is known to be small and bounded."
2- 什么是通用 'Type' 每个方法搜索和 Where ?
- dependOnInheritedWidgetOfExactType< T extends InheritedWidget >
- findAncestorWidgetOfExactType< T extends Widget >
考虑到这些我们可以回答这个问题..
所以为什么 ？
因为 findAncestorWidgetOfExactType 方法在所有小部件树中搜索（因为默认情况下它们都是 Widget 类型）
这是通过线性搜索完成的，因此 => O(N)。
This part is updated thanks to Mabsten answer
另一方面 dependOnInheritedWidgetOfExactType
在小部件树中搜索 Not，而是在包含所有祖先 InheritedWidgets 的每个元素附带的 map 中搜索, 由它们的 类型 索引。
因此 'dependOn' - 直接 - 从该映射中获取正确的继承小部件，这就是 O(1) 的原因。
性能的主要区别不是因为 findAncestorWidgetOfExactType() 搜索任何 Widget 子类，而 dependOnInheritedWidgetOfExactType() 只搜索 InheritedWidget 子类。
dependOnInheritedWidgetOfExactType() 更便宜，因为每个小部件（更准确地说，每个元素）都保留所有祖先 InheritedWidget 的映射（在字段 _inheritedWidgets 中），按它们的类型索引。然后 dependOnInheritedWidgetOfExactType() 不在小部件的树中搜索，而只在这张地图中搜索。
有用的文章：
"How does Flutter InheritedWidget work?"
"Widget - State - Context - InheritedWidget"（Didier Boelens，flutter.dev 中也引用了一篇文章的作者）
在 Flutter 中有两个函数：
- findAncestorWidgetOfExactType
- dependOnInheritedWidgetOfExactType
在文档中他们说：findAncestorWidgetOfExactType 相对昂贵（O(N) 在树的深度）。
和 dependOnInheritedWidgetOfExactType 是 O(1) 有一个小常数因子。
谁能解释为什么？为什么第一个比另一个贵？
谢谢
要回答这个问题并理解为什么这两种方法在时间复杂度上存在差异，我们首先需要澄清两件事：
1-什么是线性搜索？
Linear search (known as sequential search) is an algorithm for finding a target value within a list. It sequentially checks each element of the list for the target value until a match is found or until all the elements have been searched.
简而言之，O(1) 意味着它需要一个常数时间，（例如 10 纳秒）。
另一方面，O(N) 意味着它花费的时间与集合的大小成线性关系，因此两倍大小的集合将花费两倍的时间。您可能不想将一百万个对象放入其中一个。
因此 ( findAncestorWidgetOfExactType )
文档中的提示"Only call this method if the distance from this widget to the desired ancestor is known to be small and bounded."
2- 什么是通用 'Type' 每个方法搜索和 Where ?
- dependOnInheritedWidgetOfExactType< T extends InheritedWidget >
- findAncestorWidgetOfExactType< T extends Widget >
考虑到这些我们可以回答这个问题.. 所以为什么 ？
因为 findAncestorWidgetOfExactType 方法在所有小部件树中搜索（因为默认情况下它们都是 Widget 类型）
这是通过线性搜索完成的，因此 => O(N)。
This part is updated thanks to Mabsten answer
另一方面 dependOnInheritedWidgetOfExactType
在小部件树中搜索 Not，而是在包含所有祖先 InheritedWidgets 的每个元素附带的 map 中搜索, 由它们的 类型 索引。
因此 'dependOn' - 直接 - 从该映射中获取正确的继承小部件，这就是 O(1) 的原因。
性能的主要区别不是因为 findAncestorWidgetOfExactType() 搜索任何 Widget 子类，而 dependOnInheritedWidgetOfExactType() 只搜索 InheritedWidget 子类。
dependOnInheritedWidgetOfExactType() 更便宜，因为每个小部件（更准确地说，每个元素）都保留所有祖先 InheritedWidget 的映射（在字段 _inheritedWidgets 中），按它们的类型索引。然后 dependOnInheritedWidgetOfExactType() 不在小部件的树中搜索，而只在这张地图中搜索。
有用的文章：
"How does Flutter InheritedWidget work?"
"Widget - State - Context - InheritedWidget"（Didier Boelens，flutter.dev 中也引用了一篇文章的作者）