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 b8eb70f98c88baabeb3a4b82f2faa72422803c5f Author: Lei Rui <[email protected]> AuthorDate: Wed Jan 22 02:02:07 2025 +0800 just array for e --- .../db/query/eBUG/TimestampPriorityQueue.java | 38 +++++---- .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 91 ++++++++++++---------- .../org/apache/iotdb/db/query/eBUG/eBUG_old.java | 3 +- .../apache/iotdb/db/query/eBUG/eBUG_old_tmp.java | 4 +- .../db/query/eBUG/{eBUG.java => eBUG_tmp.java} | 8 +- 5 files changed, 82 insertions(+), 62 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 15c2dbc051c..8e8fb18ebfa 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 @@ -5,42 +5,54 @@ import java.util.*; public class TimestampPriorityQueue { private final int e; // 队列的最大大小 private final LinkedList<Point> insertionOrder; // 保持插入顺序 - public final PriorityQueue<Point> queue; // 按时间戳排序的优先队列 + // public final PriorityQueue<Point> queue; // 按时间戳排序的优先队列 + private final List<Point> sortedList; // 维护排序后的列表 // 构造函数：初始化队列大小、插入顺序队列和优先队列 public TimestampPriorityQueue(int e) { this.e = e; this.insertionOrder = new LinkedList<>(); - this.queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.x)); +// this.queue = new PriorityQueue<>(Comparator.comparingDouble(p -> p.x)); + this.sortedList = new ArrayList<>(); } public int size() { - return queue.size(); +// return queue.size(); + return sortedList.size(); } // 插入新的元素 public void insert(Point newPoint) { // 如果队列已满，移除最早插入的点 - if (queue.size() == e) { + if (sortedList.size() == e) { Point removedPoint = insertionOrder.removeFirst(); // 移除最早加入的点 复杂度1 - queue.remove(removedPoint); // 从优先队列中移除该点 TODO 复杂度O(e)! +// queue.remove(removedPoint); // 从优先队列中移除该点 TODO 复杂度O(e)! + sortedList.remove(removedPoint); // 从排序后的列表中移除该点 复杂度O(e) } // 将新点添加到插入顺序队列中 insertionOrder.addLast(newPoint); // 复杂度1 // 插入到优先队列，保持时间戳顺序 - queue.offer(newPoint); // 复杂度log(e) +// queue.add(newPoint); // 复杂度log(e) + + // 插入到排序后的列表中，保持有序 + int insertIndex = Collections.binarySearch(sortedList, newPoint, Comparator.comparingDouble(p -> p.x)); // 复杂度log(e) + if (insertIndex < 0) { + insertIndex = -(insertIndex + 1); // 如果未找到，binarySearch返回插入点的负值 + } + sortedList.add(insertIndex, newPoint); // 复杂度O(e) } // 获取队列中的所有元素（按时间戳排序） public List<Point> getQueue() { - return new ArrayList<>(queue); // 浅复制 +// return new ArrayList<>(queue); // 这个不是排序的！ + return sortedList; } public String toString() { StringBuffer stringBuffer = new StringBuffer(); - for (Point point : queue) { + for (Point point : sortedList) { stringBuffer.append(point.toString()); stringBuffer.append(","); } @@ -48,12 +60,12 @@ public class TimestampPriorityQueue { } public static void main(String[] args) { - TimestampPriorityQueue tq = new TimestampPriorityQueue(3); + TimestampPriorityQueue tq = new TimestampPriorityQueue(10); - tq.insert(new Point(10, 1000)); - tq.insert(new Point(20, 2000)); - tq.insert(new Point(15, 1500)); - tq.insert(new Point(25, 500)); + tq.insert(new Point(0, 1000)); + tq.insert(new Point(3, 2000)); + tq.insert(new Point(11, 1500)); + tq.insert(new Point(5, 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 61721a9e328..1596f32a726 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,7 @@ package org.apache.iotdb.db.query.eBUG; -import java.io.FileWriter; -import java.io.IOException; +import java.io.*; import java.util.*; import static org.apache.iotdb.db.query.eBUG.Tool.total_areal_displacement; @@ -266,8 +265,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 n = 100_0000; int p = 10; for (int i = 0; i < n; i += p) { @@ -282,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, 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 + ")"); +// int eParam = 10; + try (PrintWriter writer = new PrintWriter(new File("exp2.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<>(); diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old.java index 81825ff1b79..180f277c44e 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old.java @@ -299,7 +299,8 @@ public class eBUG_old { // 计算运行时间 // 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}; + int[] eParamList = {0, 1, 100, 500, 1000, 5000, 10000, 50000, 10_0000, 30_0000, 50_0000, 60_0000, + 70_0000, 80_0000, 90_0000, 100_0000, 150_0000, 200_0000, 250_0000, 300_0000}; // for (int eParam = 0; eParam < 2 * n; eParam += 1000) { for (int eParam : eParamList) { long startTime = System.currentTimeMillis(); diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old_tmp.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old_tmp.java index 2270b8253c2..5cfafb59110 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old_tmp.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old_tmp.java @@ -264,7 +264,7 @@ public class eBUG_old_tmp { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); - int n = 20; + int n = 10000; int p = 10; for (int i = 0; i < n; i += p) { @@ -298,7 +298,7 @@ public class eBUG_old_tmp { // 计算运行时间 // int eParam = 10; // for (int eParam = 0; eParam < 2 * n; eParam += 1000) { - int eParam = 10; + int eParam = 22; long startTime = System.currentTimeMillis(); List<Point> results = buildEffectiveArea(polyline, eParam, false); // 输出结果 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_tmp.java similarity index 99% 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_tmp.java index 61721a9e328..a04c4c17920 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_tmp.java @@ -27,7 +27,7 @@ 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_tmp { public static List<Point> findEliminated(Polyline lineToSimplify, TimestampPriorityQueue recentEliminatedOrdered, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 @@ -267,7 +267,7 @@ public class eBUG { List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); // int n = 1000_0000; - int n = 20; + int n = 10000; int p = 10; for (int i = 0; i < n; i += p) { @@ -299,9 +299,9 @@ public class eBUG { System.out.println("---------------------------------"); // List<Point> results = new ArrayList<>(); // 计算运行时间 - int eParam = 10; + int eParam = 0; long startTime = System.currentTimeMillis(); - List<Point> results = buildEffectiveArea(polyline, eParam, true); + List<Point> results = buildEffectiveArea(polyline, eParam, false); // 输出结果 long endTime = System.currentTimeMillis(); System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms");
