This is an automated email from the ASF dual-hosted git repository.
jakevin pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/master by this push:
new ea5fd53f22 [enhancement](Nereids): optimize deepEquals (#22944)
ea5fd53f22 is described below
commit ea5fd53f22071138ed3df8233a77ade49f68f863
Author: jakevin <[email protected]>
AuthorDate: Mon Aug 21 23:03:06 2023 +0800
[enhancement](Nereids): optimize deepEquals (#22944)
---
.../org/apache/doris/nereids/trees/TreeNode.java | 37 ++++++++++++++++++----
1 file changed, 30 insertions(+), 7 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/TreeNode.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/TreeNode.java
index 3c64a043d6..10be3d74ca 100644
--- a/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/TreeNode.java
+++ b/fe/fe-core/src/main/java/org/apache/doris/nereids/trees/TreeNode.java
@@ -21,6 +21,8 @@ import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableList.Builder;
import com.google.common.collect.ImmutableSet;
+import java.util.ArrayDeque;
+import java.util.Deque;
import java.util.List;
import java.util.function.BiFunction;
import java.util.function.Consumer;
@@ -213,7 +215,7 @@ public interface TreeNode<NODE_TYPE extends
TreeNode<NODE_TYPE>> {
* @param types classes array
* @return true if it has any instance of the types
*/
- default boolean containsType(Class...types) {
+ default boolean containsType(Class... types) {
return anyMatch(node -> {
for (Class type : types) {
if (type.isInstance(node)) {
@@ -230,14 +232,35 @@ public interface TreeNode<NODE_TYPE extends
TreeNode<NODE_TYPE>> {
* @return true if all the tree is equals
*/
default boolean deepEquals(TreeNode that) {
- if (!equals(that)) {
- return false;
- }
- for (int i = 0; i < arity(); i++) {
- if (!child(i).deepEquals(that.child(i))) {
+ Deque<TreeNode> thisDeque = new ArrayDeque<>();
+ Deque<TreeNode> thatDeque = new ArrayDeque<>();
+
+ thisDeque.push(this);
+ thatDeque.push(that);
+
+ while (!thisDeque.isEmpty()) {
+ if (thatDeque.isEmpty()) {
+ // The "that" tree has been fully traversed, but the "this"
tree has not; hence they are not equal.
+ return false;
+ }
+
+ TreeNode currentNodeThis = thisDeque.pop();
+ TreeNode currentNodeThat = thatDeque.pop();
+
+ // If current nodes are not equal or the number of child nodes
differ, return false.
+ if (!currentNodeThis.equals(currentNodeThat)
+ || currentNodeThis.arity() != currentNodeThat.arity()) {
return false;
}
+
+ // Add child nodes to the deque for further processing.
+ for (int i = 0; i < currentNodeThis.arity(); i++) {
+ thisDeque.push(currentNodeThis.child(i));
+ thatDeque.push(currentNodeThat.child(i));
+ }
}
- return true;
+
+ // If the "that" tree hasn't been fully traversed, return false.
+ return thatDeque.isEmpty();
}
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
