You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@iotdb.apache.org by le...@apache.org on 2025/02/23 17:44:24 UTC
(iotdb) 23/44: return bottom-up order
This is an automated email from the ASF dual-hosted git repository.
leirui pushed a commit to branch research/area-visualization
in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 5ee9e320f4c473516ff3cea64a2d07824f2af757
Author: Lei Rui <10...@qq.com>
AuthorDate: Thu Jan 23 18:34:02 2025 +0800
return bottom-up order
---
.../java/org/apache/iotdb/db/query/eBUG/Test1.java | 10 ++++-
.../java/org/apache/iotdb/db/query/eBUG/Test2.java | 51 +++++++++++++---------
.../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 25 ++++++++---
3 files changed, 57 insertions(+), 29 deletions(-)
diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java
index f53f5719217..91df7751e50 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java
@@ -3,6 +3,7 @@ package org.apache.iotdb.db.query.eBUG;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
+import java.util.Comparator;
import java.util.List;
import java.util.Random;
@@ -13,8 +14,9 @@ public class Test1 {
public static void main(String[] args) {
Polyline polyline = new Polyline();
List<Polyline> polylineList = new ArrayList<>();
- Random rand = new Random(3);
+ Random rand = new Random(10);
int n = 10000;
+ int eParam = 0;
int p = 10;
for (int i = 0; i < n; i += p) {
@@ -44,14 +46,18 @@ public class Test1 {
}
System.out.println("---------------------------------");
- int eParam = 1;
long startTime = System.currentTimeMillis();
+ // 注意现在返回的结果是按照Sig递增也就是bottom-up淘汰的顺序排列的，而不是按照时间戳递增排列
List<Point> results = buildEffectiveArea(polyline, eParam, false);
// 输出结果
long endTime = System.currentTimeMillis();
System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
System.out.println(results.size());
+ // 注意现在返回的结果是按照Sig递增也就是bottom-up淘汰的顺序排列的，而不是按照时间戳递增排列
+ // 按照时间戳递增排序整理:
+ results.sort(Comparator.comparingDouble(point -> point.x));
+
if (results.size() <= 100) {
System.out.println("+++++++++++++++++++");
for (int i = 0; i < results.size(); i++) {
diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java
index 589603525e5..fb7de582f17 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test2.java
@@ -2,6 +2,7 @@ package org.apache.iotdb.db.query.eBUG;
import io.jsonwebtoken.lang.Assert;
+import java.util.Comparator;
import java.util.List;
import java.util.Random;
@@ -10,32 +11,42 @@ import static org.apache.iotdb.db.query.eBUG.eBUG.buildEffectiveArea;
public class Test2 {
// 用于测试在线采样
public static void main(String[] args) {
- int n = 100000;
+ int n = 20;
int eParam = 1;
-// int m = 100; // >2代表在线采样，<=2代表预计算
- for (int m = 9900; m <= n; m++) {
+ int m = 2; // >2代表在线采样，<=2代表预计算
+// for (int m = 9900; m <= n; m++) {
- Polyline polyline = new Polyline();
- Random rand = new Random(2);
- for (int i = 0; i < n; i++) {
- double v = rand.nextInt(1000000);
- polyline.addVertex(new Point(i, v));
- }
+ Polyline polyline = new Polyline();
+ Random rand = new Random(2);
+ for (int i = 0; i < n; i++) {
+ double v = rand.nextInt(1000000);
+ polyline.addVertex(new Point(i, v));
+ }
- long startTime = System.currentTimeMillis();
- List<Point> results = buildEffectiveArea(polyline, eParam, false, m);
- long endTime = System.currentTimeMillis();
- System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
+ long startTime = System.currentTimeMillis();
+ List<Point> results = buildEffectiveArea(polyline, eParam, false, m);
+ long endTime = System.currentTimeMillis();
+ System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms");
- System.out.println(results.size());
+ System.out.println(results.size());
+ if (m > 2 && m < n) {
Assert.isTrue(results.size() == m);
+ } else {
+ Assert.isTrue(results.size() == n);
+ }
+ if (results.size() <= 100) {
+ System.out.println("+++++++++++++++++++");
+ for (Point point : results) {
+ System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")");
+ }
+ // 注意现在返回的结果是按照Sig递增也就是bottom-up淘汰的顺序排列的，而不是按照时间戳递增排列
+ // 按照时间戳递增排序整理:
+ results.sort(Comparator.comparingDouble(point -> point.x));
+ System.out.println("+++++++++++++++++++");
+ for (Point point : results) {
+ System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")");
+ }
}
-// if (results.size() <= 100) {
-// System.out.println("+++++++++++++++++++");
-// for (Point point : results) {
-// System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")");
-// }
-// }
}
}
diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java
index b9147e4c574..e177b1dcf20 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java
@@ -66,12 +66,17 @@ public class eBUG {
}
if (m > 2) {
- System.out.println("online sampling mode, returning " + m + " sampled points");
+ System.out.println("online sampling mode, " +
+ "returning " + m + " sampled points sorted by time in ascending order");
} else {
- System.out.println("offline precomputation mode, returning each point with dominated significance");
+ System.out.println("offline precomputation mode, " +
+ "returning each point sorted by dominated significance (DS) in ascending order");
}
- List<Point> results = lineToSimplify.getVertices(); // 浅复制
+// List<Point> results = lineToSimplify.getVertices(); // 浅复制
+ // TODO 预计算结果改成按照bottom-up逐点淘汰顺序（DS递增）排列而不是按照时间戳，这样省去在线时对DS排序的过程
+ // add的是Point引用，所以没有多用一倍的空间
+ List<Point> resultsBottomUpEliminated = new ArrayList<>();
// 存储的是点的引用，这样可以修改原来序列里点的淘汰状态
// 存储的是距离当前最新状态的滞后的尚未施加、待施加的e个淘汰点
@@ -79,7 +84,7 @@ public class eBUG {
int total = lineToSimplify.size();
if (total < 3) {
- return results; // 不足 3 个点无法形成三角形
+ return lineToSimplify.getVertices(); // 不足 3 个点无法形成三角形
}
int nTriangles = total - 2;
@@ -155,7 +160,9 @@ public class eBUG {
if (tri.area > previousEA) {
previousEA = tri.area;
}
- results.get(tri.indices[1]).z = previousEA; // dominated significance
+// results.get(tri.indices[1]).z = previousEA; // dominated significance
+ lineToSimplify.get(tri.indices[1]).z = previousEA; // dominated significance
+ resultsBottomUpEliminated.add(lineToSimplify.get(tri.indices[1])); // TODO add的是Point引用，所以没有多用一倍的空间
if (debug) {
System.out.println(Arrays.toString(tri.indices) + ", Dominated Sig=" + previousEA);
}
@@ -270,13 +277,17 @@ public class eBUG {
Point start = lineToSimplify.get(0);
Point end = lineToSimplify.get(lineToSimplify.size() - 1);
while (start != end) { // Point类里增加prev&next指针，这样T'_max{0,k-e}里点的连接关系就有了，这样从Pa开始沿着指针，遍历点数一定不超过e+3
- onlineSampled.add(start);
+ onlineSampled.add(start); // 注意未淘汰的点的Dominated significance尚未赋值，还都是infinity
start = start.next; // when e=0, only traversing three points pa pi pb
}
onlineSampled.add(end);
return onlineSampled;
} else { // offline precomputation mode, for precomputing the dominated significance of each point
- return results; // 注意这就是lineToSimplify.getVertices()
+// return results; // 注意这就是lineToSimplify.getVertices()
+ // TODO
+ resultsBottomUpEliminated.add(lineToSimplify.get(0)); // 全局首点
+ resultsBottomUpEliminated.add(lineToSimplify.get(lineToSimplify.size() - 1)); // 全局尾点
+ return resultsBottomUpEliminated;
}
}