This is an automated email from the ASF dual-hosted git repository.
zyk pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/iotdb.git
The following commit(s) were added to refs/heads/master by this push:
new c245722302 [IOTDB-4352] Optimize PatialPath#overlapWith with
MULTI_LEVEL_PATH_WILDCARD (#7262)
c245722302 is described below
commit c2457223020411e2e14d58ef5ed465d5f829e55f
Author: Chen YZ <[email protected]>
AuthorDate: Wed Sep 7 22:05:22 2022 +0800
[IOTDB-4352] Optimize PatialPath#overlapWith with MULTI_LEVEL_PATH_WILDCARD
(#7262)
[IOTDB-4352] Optimize PatialPath#overlapWith with MULTI_LEVEL_PATH_WILDCARD
(#7262)
---
.../org/apache/iotdb/commons/path/PartialPath.java | 88 ++++++++++------------
1 file changed, 40 insertions(+), 48 deletions(-)
diff --git
a/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
b/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
index a79a8a14bf..9d0b432797 100644
--- a/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
+++ b/node-commons/src/main/java/org/apache/iotdb/commons/path/PartialPath.java
@@ -367,20 +367,10 @@ public class PartialPath extends Path implements
Comparable<Path>, Cloneable {
public boolean overlapWith(PartialPath rPath) {
String[] rNodes = rPath.getNodes();
for (int i = 0; i < this.nodes.length && i < rNodes.length; i++) {
- // if encounter MULTI_LEVEL_PATH_WILDCARD, check recursively
- if (nodes[i].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- if (checkOverlapWithMultiLevelWildcard(nodes, rNodes, i + 1, i + 1)) {
- return true;
- }
- }
- if (rNodes[i].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- if (checkOverlapWithMultiLevelWildcard(rNodes, nodes, i + 1, i + 1)) {
- return true;
- }
- }
+ // if encounter MULTI_LEVEL_PATH_WILDCARD
if (nodes[i].equals(MULTI_LEVEL_PATH_WILDCARD)
- && rNodes[i].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- return false;
+ || rNodes[i].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ return checkOverlapWithMultiLevelWildcard(nodes, rNodes);
}
// if without MULTI_LEVEL_PATH_WILDCARD, scan and check
if (nodes[i].equals(ONE_LEVEL_PATH_WILDCARD) ||
rNodes[i].equals(ONE_LEVEL_PATH_WILDCARD)) {
@@ -394,47 +384,49 @@ public class PartialPath extends Path implements
Comparable<Path>, Cloneable {
}
/**
- * Try to check overlap between nodes1[pos1:] and nodes2[pos2:] recursively.
+ * Try to check overlap between nodes1 and nodes2 with
MULTI_LEVEL_PATH_WILDCARD. Time complexity
+ * O(n^2).
*
- * @param nodes1 nodes1[pos1-1] is MULTI_LEVEL_PATH_WILDCARD.
- * @param nodes2 nodes2 is another pattern path to check overlapping
- * @param pos1 start index of nodes1
- * @param pos2 start index of nodes2
* @return true if overlapping, otherwise return false
*/
- private boolean checkOverlapWithMultiLevelWildcard(
- String[] nodes1, String[] nodes2, int pos1, int pos2) {
- // make sure pos1<nodes1.length and pos2<node2.length
- if (pos1 > nodes1.length || pos2 > nodes2.length) {
- return false;
- } else if (pos1 == nodes1.length && pos2 == nodes2.length) {
- return true;
- }
- int i, j;
- for (i = pos1, j = pos2; i < nodes1.length && j < nodes2.length; i++, j++)
{
- if (nodes1[i].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- if (checkOverlapWithMultiLevelWildcard(nodes1, nodes2, pos1 + 1, pos2
+ 1)) {
- return true;
+ private boolean checkOverlapWithMultiLevelWildcard(String[] nodes1, String[]
nodes2) {
+ // dp[i][j] means if nodes1[0:i) and nodes[0:j) overlapping
+ boolean[][] dp = new boolean[nodes1.length + 1][nodes2.length + 1];
+ dp[0][0] = true;
+ for (int i = 1; i <= nodes1.length; i++) {
+ for (int j = 1; j <= nodes2.length; j++) {
+ if (nodes1[i - 1].equals(MULTI_LEVEL_PATH_WILDCARD)
+ || nodes2[j - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ // if encounter MULTI_LEVEL_PATH_WILDCARD
+ if (nodes1[i - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ // if nodes1[i-1] is MULTI_LEVEL_PATH_WILDCARD,
dp[i][k(k>=j)]=dp[i-1][j-1]
+ if (dp[i - 1][j - 1]) {
+ for (int k = j; k <= nodes2.length; k++) {
+ dp[i][k] = true;
+ }
+ }
+ }
+ if (nodes2[j - 1].equals(MULTI_LEVEL_PATH_WILDCARD)) {
+ // if nodes2[j-1] is MULTI_LEVEL_PATH_WILDCARD,
dp[k(k>=i)][j]=dp[i-1][j-1]
+ if (dp[i - 1][j - 1]) {
+ for (int k = i; k <= nodes1.length; k++) {
+ dp[k][j] = true;
+ }
+ }
+ }
+ } else {
+ // if without MULTI_LEVEL_PATH_WILDCARD, scan and check
+ if (nodes1[i - 1].equals(ONE_LEVEL_PATH_WILDCARD)
+ || nodes2[j - 1].equals(ONE_LEVEL_PATH_WILDCARD)
+ || nodes1[i - 1].equals(nodes2[j - 1])) {
+ // if nodes1[i-1] and nodes[2] is matched, dp[i][j] = dp[i-1][j-1]
+ dp[i][j] |= dp[i - 1][j - 1];
+ }
}
}
- if (nodes2[j].equals(MULTI_LEVEL_PATH_WILDCARD)) {
- if (checkOverlapWithMultiLevelWildcard(nodes2, nodes1, pos2 + 1, pos1
+ 1)) {
- return true;
- }
- }
- if (nodes1[i].equals(ONE_LEVEL_PATH_WILDCARD) ||
nodes2[j].equals(ONE_LEVEL_PATH_WILDCARD)) {
- continue;
- } else if (!nodes1[i].equals(nodes2[j])) {
- // failed to match, MULTI_LEVEL_PATH_WILDCARD should match more path
in nodes2.
- return checkOverlapWithMultiLevelWildcard(nodes1, nodes2, pos1, pos2 +
1);
- }
- }
- if (i != nodes1.length || j != nodes2.length) {
- // MULTI_LEVEL_PATH_WILDCARD should match more path in nodes2.
- return checkOverlapWithMultiLevelWildcard(nodes1, nodes2, pos1, pos2 +
1);
- } else {
- return true;
}
+
+ return dp[nodes1.length][nodes2.length];
}
@Override
