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 8dfbcb233e1d31c73cf0ea39e9286df714d484b1 Author: Lei Rui <[email protected]> AuthorDate: Wed Jan 22 00:11:17 2025 +0800 f --- .../db/query/eBUG/TimestampPriorityQueue.java | 117 +++++++++++++++++++++ .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 74 +++++++------ .../db/query/eBUG/{eBUG.java => eBUG_old.java} | 98 +++++++++-------- 3 files changed, 207 insertions(+), 82 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 new file mode 100644 index 00000000000..222790aed42 --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/TimestampPriorityQueue.java @@ -0,0 +1,117 @@ +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 { + private final int e; // 队列的最大大小 + private final LinkedList<Point> insertionOrder; // 保持插入顺序 + public final PriorityQueue<Point> queue; // 按时间戳排序的优先队列 + + // 构造函数：初始化队列大小、插入顺序队列和优先队列 + public TimestampPriorityQueue(int e) { + this.e = e; + this.insertionOrder = new LinkedList<>(); + this.queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.timestamp)); + } + + // 插入新的元素 + public void insert(Point newPoint) { + // 如果队列已满，移除最早插入的点 + if (queue.size() == e) { + Point removedPoint = insertionOrder.removeFirst(); // 移除最早加入的点 + queue.remove(removedPoint); // 从优先队列中移除该点 + } + + // 将新点添加到插入顺序队列中 + insertionOrder.addLast(newPoint); + + // 插入到优先队列，保持时间戳顺序 + queue.offer(newPoint); + } + + // 获取队列中的所有元素（按时间戳排序） + public List<Point> getQueue() { + 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 static void main(String[] args) { + TimestampPriorityQueue tq = new TimestampPriorityQueue(3); + + tq.insert(new Point(10, 1000)); + tq.insert(new Point(20, 2000)); + tq.insert(new Point(15, 1500)); + tq.insert(new Point(25, 2500)); + + // 打印队列内容 + for (Point point : tq.getQueue()) { + System.out.println(point); + } + } +} + + +//public class TimestampPriorityQueue { // for managing the e most recently eliminated points, sorted by time in ascending order +// private final int e; +// public final PriorityQueue<Point> queue; +// +// // 构造函数：初始化优先队列的最大大小 +// public TimestampPriorityQueue(int e) { +// this.e = e; +// this.queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.x)); +// } +// +// // 插入新的元素 +// public void insert(Point newPoint) { +// // 如果队列已满，移除最小（最早）的元素 +// if (queue.size() == e) { +// queue.poll(); +// } +// +// // 插入元素，队列会根据时间戳自动排序 +// queue.offer(newPoint); +// } +// +// // 获取队列中的所有元素 +// public List<Point> getQueue() { +// return new ArrayList<>(queue); +// } +// +// public static void main(String[] args) { +// TimestampPriorityQueue tq = new TimestampPriorityQueue(3); +// +// tq.insert(new Point(10, 1000)); +// tq.insert(new Point(20, 2000)); +// tq.insert(new Point(15, 1500)); +// tq.insert(new Point(25, 2500)); +// +// // 打印队列内容 +// long tmp = 2000; +// for (Point point : tq.getQueue()) { +// point.x = tmp--; +// System.out.println("Value: " + point.x + ", Timestamp: " + point.y); +// } +// +// System.out.println(tq.queue.poll()); +// } +//} 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 289ecf0b913..62e67a0f1f9 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,8 +19,6 @@ 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; @@ -56,13 +54,13 @@ public class eBUG { // } if (recentEliminated.length >= (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 +// 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; // 已经按照时间戳递增 } // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 - System.out.println("k>=[c=(b-a-2)]>e, search among e"); +// System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); res.add(pi); res.add(pb); @@ -264,7 +262,7 @@ public class eBUG { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 100; + int n = 1000_0000; int p = 10; for (int i = 0; i < n; i += p) { @@ -279,19 +277,19 @@ 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<>(); @@ -304,27 +302,27 @@ public class eBUG { 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 + ")"); - } - } - - try (FileWriter writer = new FileWriter("fast.csv")) { - // 写入CSV头部 - writer.append("x,y,z\n"); +// 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 + ")"); +// } +// } - // 写入每个点的数据 - 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.java similarity index 86% 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.java index 289ecf0b913..81825ff1b79 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.java @@ -19,15 +19,16 @@ package org.apache.iotdb.db.query.eBUG; -import java.io.FileWriter; -import java.io.IOException; +import java.io.File; +import java.io.FileNotFoundException; +import java.io.PrintWriter; 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 { public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 @@ -56,13 +57,13 @@ public class eBUG { // } if (recentEliminated.length >= (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 +// 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; // 已经按照时间戳递增 } // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 - System.out.println("k>=[c=(b-a-2)]>e, search among e"); +// System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); res.add(pi); res.add(pb); @@ -264,7 +265,7 @@ public class eBUG { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 100; + int n = 100_0000; int p = 10; for (int i = 0; i < n; i += p) { @@ -279,52 +280,61 @@ 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); - // 输出结果 - 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 + ")"); +// int eParam = 10; + try (PrintWriter writer = new PrintWriter(new File("exp.csv"))) { + int[] eParamList = {0, 1, 100, 500, 1000, 5000, 10000, 50000, 10_0000, 50_0000, 100_0000, 200_0000}; +// for (int eParam = 0; eParam < 2 * n; eParam += 1000) { + for (int eParam : eParamList) { + long startTime = System.currentTimeMillis(); + 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()); + writer.println(n + "," + eParam + "," + (endTime - startTime)); } + } catch (FileNotFoundException e) { + throw new RuntimeException(e); } - try (FileWriter writer = new FileWriter("fast.csv")) { - // 写入CSV头部 - writer.append("x,y,z\n"); +// 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 + ")"); +// } +// } - // 写入每个点的数据 - 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<>();
