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 b263ae6b18173016b9b90f399225c61c105bfc52 Author: Lei Rui <[email protected]> AuthorDate: Wed Jan 22 00:45:36 2025 +0800 de --- .../db/query/eBUG/TimestampPriorityQueue.java | 42 +++---- .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 121 +++++++++++---------- .../db/query/eBUG/{eBUG.java => eBUG_old_tmp.java} | 50 +++++---- 3 files changed, 107 insertions(+), 106 deletions(-) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/TimestampPriorityQueue.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/TimestampPriorityQueue.java index 222790aed42..15c2dbc051c 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/TimestampPriorityQueue.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/TimestampPriorityQueue.java @@ -1,10 +1,5 @@ package org.apache.iotdb.db.query.eBUG; -import java.util.ArrayList; -import java.util.Comparator; -import java.util.List; -import java.util.PriorityQueue; - import java.util.*; public class TimestampPriorityQueue { @@ -16,43 +11,40 @@ public class TimestampPriorityQueue { public TimestampPriorityQueue(int e) { this.e = e; this.insertionOrder = new LinkedList<>(); - this.queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.timestamp)); + this.queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.x)); + } + + public int size() { + return queue.size(); } // 插入新的元素 public void insert(Point newPoint) { // 如果队列已满，移除最早插入的点 if (queue.size() == e) { - Point removedPoint = insertionOrder.removeFirst(); // 移除最早加入的点 - queue.remove(removedPoint); // 从优先队列中移除该点 + Point removedPoint = insertionOrder.removeFirst(); // 移除最早加入的点 复杂度1 + queue.remove(removedPoint); // 从优先队列中移除该点 TODO 复杂度O(e)! } // 将新点添加到插入顺序队列中 - insertionOrder.addLast(newPoint); + insertionOrder.addLast(newPoint); // 复杂度1 // 插入到优先队列，保持时间戳顺序 - queue.offer(newPoint); + queue.offer(newPoint); // 复杂度log(e) } // 获取队列中的所有元素（按时间戳排序） public List<Point> getQueue() { - return new ArrayList<>(queue); + return new ArrayList<>(queue); // 浅复制 } - // Point 类，代表一个带时间戳的点 - public static class Point { - int value; - long timestamp; - - public Point(int value, long timestamp) { - this.value = value; - this.timestamp = timestamp; - } - - @Override - public String toString() { - return "Value: " + value + ", Timestamp: " + timestamp; + public String toString() { + StringBuffer stringBuffer = new StringBuffer(); + for (Point point : queue) { + stringBuffer.append(point.toString()); + stringBuffer.append(","); } + return stringBuffer.toString(); } public static void main(String[] args) { @@ -61,7 +53,7 @@ public class TimestampPriorityQueue { tq.insert(new Point(10, 1000)); tq.insert(new Point(20, 2000)); tq.insert(new Point(15, 1500)); - tq.insert(new Point(25, 2500)); + tq.insert(new Point(25, 500)); // 打印队列内容 for (Point point : tq.getQueue()) { 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 62e67a0f1f9..61721a9e328 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 @@ -19,6 +19,8 @@ package org.apache.iotdb.db.query.eBUG; +import java.io.FileWriter; +import java.io.IOException; import java.util.*; import static org.apache.iotdb.db.query.eBUG.Tool.total_areal_displacement; @@ -26,12 +28,9 @@ import static org.apache.iotdb.db.query.eBUG.Tool.triArea; public class eBUG { - public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, + public static List<Point> findEliminated(Polyline lineToSimplify, TimestampPriorityQueue recentEliminatedOrdered, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 - // 从最近淘汰的e个点里寻找位于pa~pb之间的：e - // 把上一步找到的点和pa pi pb一起按照时间戳递增排序：记c=b-a。如果e<c，那么eloge，否则c - // 后面鞋带公式计算面积：min(e+3,c) // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ // pi: the point whose significance needs updating // pa: left adjacent non-eliminated point of pi @@ -53,7 +52,7 @@ public class eBUG { // return res; // pa pi pb已经按照时间戳递增 // } - if (recentEliminated.length >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region + if (recentEliminatedOrdered.size() >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region // System.out.println("[c=(b-a-2)]<=e, use T directly"); // worst case下, k=c res = lineToSimplify.getVertices().subList(pa_idx, pb_idx + 1); // 左闭右开 return res; // 已经按照时间戳递增 @@ -62,23 +61,26 @@ public class eBUG { // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 // System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); - res.add(pi); - res.add(pb); // 包括了c>e=0的情况 - for (int idx : recentEliminated) { // e points - if (idx == 0) { // init, not filled by real eliminated points yet + boolean addPi = false; + for (Point p : recentEliminatedOrdered.getQueue()) { // 已经按时间戳递增排序，为了后面计算total areal displacement需要 + if (p.x <= pa.x) { + continue; + } + if (p.x >= pb.x) { break; } - Point p = lineToSimplify.get(idx); - if (p.x > pa.x && p.x < pb.x) { - res.add(p); + if (p.x > pi.x && !addPi) { + res.add(pi); + addPi = true; } + res.add(p); } - - // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 - res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 TODO 这样的话时间复杂度要变成e*log(e)了吧？ - + if (!addPi) { // may happen when no eliminated points found above + res.add(pi); + } + res.add(pb); return res; } @@ -91,8 +93,9 @@ public class eBUG { // results.addAll(lineToSimplify.getVertices()); // TODO debug // TODO 需要一个东西来记录最近淘汰的点依次是谁 - int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated - int recentEliminatedIdx = 0; // index in the array, circulate +// int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated +// int recentEliminatedIdx = 0; // index in the array, circulate + TimestampPriorityQueue recentEliminatedOrdered = new TimestampPriorityQueue(e); int total = lineToSimplify.size(); if (total < 3) { @@ -140,11 +143,12 @@ public class eBUG { System.out.println("(1) eliminate " + lineToSimplify.get(tri.indices[1])); } if (e > 0) { // otherwise e=0 - recentEliminated[recentEliminatedIdx] = tri.indices[1]; - recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate +// recentEliminated[recentEliminatedIdx] = tri.indices[1]; +// recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate + recentEliminatedOrdered.insert(lineToSimplify.get(tri.indices[1])); } if (debug) { - System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); + System.out.println("the e most recently eliminated points:" + recentEliminatedOrdered); } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） @@ -173,7 +177,7 @@ public class eBUG { tri.prev.indices[2] = tri.indices[2]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, tri.prev.indices[0], tri.prev.indices[1], tri.prev.indices[2]); // TODO complexity ? @@ -222,7 +226,7 @@ public class eBUG { tri.next.indices[0] = tri.indices[0]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, tri.next.indices[0], tri.next.indices[1], tri.next.indices[2]); // TODO complexity @@ -262,7 +266,8 @@ public class eBUG { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 1000_0000; +// int n = 1000_0000; + int n = 20; int p = 10; for (int i = 0; i < n; i += p) { @@ -277,52 +282,52 @@ public class eBUG { polylineList.add(polylineBatch); } -// try (FileWriter writer = new FileWriter("raw.csv")) { -// // 写入CSV头部 -// writer.append("x,y,z\n"); -// -// // 写入每个点的数据 -// for (int i = 0; i < polyline.size(); i++) { -// Point point = polyline.get(i); -// writer.append(point.x + "," + point.y + "," + point.z + "\n"); -// } -// System.out.println("Data has been written"); -// } catch (IOException e) { -// System.out.println("Error writing to CSV file: " + e.getMessage()); -// } + try (FileWriter writer = new FileWriter("raw.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < polyline.size(); i++) { + Point point = polyline.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } System.out.println("---------------------------------"); // List<Point> results = new ArrayList<>(); // 计算运行时间 int eParam = 10; long startTime = System.currentTimeMillis(); - List<Point> results = buildEffectiveArea(polyline, eParam, false); + List<Point> results = buildEffectiveArea(polyline, eParam, true); // 输出结果 long endTime = System.currentTimeMillis(); System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); System.out.println(results.size()); -// if (results.size() <= 100) { -// System.out.println("+++++++++++++++++++"); -// for (int i = 0; i < results.size(); i++) { -// Point point = results.get(i); -// System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); -// } -// } + if (results.size() <= 100) { + System.out.println("+++++++++++++++++++"); + for (int i = 0; i < results.size(); i++) { + Point point = results.get(i); + System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); + } + } -// try (FileWriter writer = new FileWriter("fast.csv")) { -// // 写入CSV头部 -// writer.append("x,y,z\n"); -// -// // 写入每个点的数据 -// for (int i = 0; i < results.size(); i++) { -// Point point = results.get(i); -// writer.append(point.x + "," + point.y + "," + point.z + "\n"); -// } -// System.out.println("Data has been written"); -// } catch (IOException e) { -// System.out.println("Error writing to CSV file: " + e.getMessage()); -// } + try (FileWriter writer = new FileWriter("fast.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < results.size(); i++) { + Point point = results.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } // System.out.println("---------------------------------"); // List<List<Point>> resultsBatchList = new ArrayList<>(); 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_old_tmp.java similarity index 93% copy from server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG.java copy to server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old_tmp.java index 62e67a0f1f9..2270b8253c2 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_old_tmp.java @@ -19,13 +19,15 @@ package org.apache.iotdb.db.query.eBUG; +import java.io.FileWriter; +import java.io.IOException; import java.util.*; import static org.apache.iotdb.db.query.eBUG.Tool.total_areal_displacement; import static org.apache.iotdb.db.query.eBUG.Tool.triArea; -public class eBUG { +public class eBUG_old_tmp { public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 @@ -262,7 +264,7 @@ public class eBUG { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 1000_0000; + int n = 20; int p = 10; for (int i = 0; i < n; i += p) { @@ -294,35 +296,37 @@ public class eBUG { System.out.println("---------------------------------"); // List<Point> results = new ArrayList<>(); // 计算运行时间 +// int eParam = 10; +// for (int eParam = 0; eParam < 2 * n; eParam += 1000) { int eParam = 10; long startTime = System.currentTimeMillis(); List<Point> results = buildEffectiveArea(polyline, eParam, false); // 输出结果 long endTime = System.currentTimeMillis(); - System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); + System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms"); System.out.println(results.size()); -// if (results.size() <= 100) { -// System.out.println("+++++++++++++++++++"); -// for (int i = 0; i < results.size(); i++) { -// Point point = results.get(i); -// System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); -// } -// } + if (results.size() <= 100) { + System.out.println("+++++++++++++++++++"); + for (int i = 0; i < results.size(); i++) { + Point point = results.get(i); + System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")"); + } + } -// try (FileWriter writer = new FileWriter("fast.csv")) { -// // 写入CSV头部 -// writer.append("x,y,z\n"); -// -// // 写入每个点的数据 -// for (int i = 0; i < results.size(); i++) { -// Point point = results.get(i); -// writer.append(point.x + "," + point.y + "," + point.z + "\n"); -// } -// System.out.println("Data has been written"); -// } catch (IOException e) { -// System.out.println("Error writing to CSV file: " + e.getMessage()); -// } + try (FileWriter writer = new FileWriter("fast2.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); + + // 写入每个点的数据 + for (int i = 0; i < results.size(); i++) { + Point point = results.get(i); + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println("Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } // System.out.println("---------------------------------"); // List<List<Point>> resultsBatchList = new ArrayList<>();
