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:16 UTC
(iotdb) 15/44: just array for e
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 <10...@qq.com>
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");