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 <[email protected]> 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; } }
