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:09 UTC
(iotdb) 08/44: fix
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 997e8c0687fe1d02e359985b5b5812190cd3cf55
Author: Lei Rui <10...@qq.com>
AuthorDate: Fri Jan 17 20:52:57 2025 +0800
fix
---
.../iotdb/db/query/simpiece/Visval_standard.java | 115 +++++----
.../db/query/simpiece/Visval_standard_slow.java | 279 ---------------------
2 files changed, 60 insertions(+), 334 deletions(-)
diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java
index 28f0f26618a..369c0fec918 100644
--- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java
+++ b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard.java
@@ -22,6 +22,7 @@ package org.apache.iotdb.db.query.simpiece;
import java.io.FileWriter;
import java.io.IOException;
import java.util.*;
+import java.util.stream.Collectors;
// adapted from the open source C++ code
// https://github.com/ofZach/Visvalingam-Whyatt/blob/master/src/testApp.cpp
@@ -159,13 +160,15 @@ public class Visval_standard {
results.get(tri.indices[1]).z = previousEA;
// System.out.println(tri.indices[1] + "," + previousEA);
- System.out.println(Arrays.toString(tri.indices) + "," + previousEA);
+// System.out.println(Arrays.toString(tri.indices) + "," + previousEA);
// 更新相邻三角形
if (tri.prev != null) {
+ // 标记为失效点，同时new一个新的对象接管它的一切数据和前后连接关系，然后更新前后连接关系、更新significance、加入heap使其排好序
+
// 1. 处理旧的tri.prev被标记删除的事情（角色替代）
// triangleHeap.remove(tri.prev); // Avoid using heap.remove(x) as it is O(n) complexity!
- tri.prev.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只有poll到它就跳过就可以
+ tri.prev.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只要heap poll到它就跳过就可以
Triangle newPre = new Triangle(tri.prev); // deep copy and inherit connection
// tri.prev = newPre; // replace TODO can omit
@@ -183,6 +186,8 @@ public class Visval_standard {
}
if (tri.next != null) {
+ // 标记为失效点，同时new一个新的对象接管它的一切数据和前后连接关系，然后更新前后连接关系、更新significance、加入heap使其排好序
+
// 1. 处理旧的tri.next被标记删除的事情（角色替代）
// triangleHeap.remove(tri.next); // Avoid using heap.remove(x) as it is O(n) complexity
tri.next.markDeleted(); // O(1) 这个点标记为废掉，前后关联都砍断，但是不remove因为那太耗时，只有poll到它就跳过就可以
@@ -211,9 +216,9 @@ public class Visval_standard {
Polyline polyline = new Polyline();
List<Polyline> polylineList = new ArrayList<>();
Random rand = new Random(1);
- int n = 100000; //1000_000;
+ int n = 1000_000;
- int p = 100;
+ int p = 1000;
for (int i = 0; i < n; i += p) {
Polyline polylineBatch = new Polyline();
for (int j = i; j < Math.min(i + p, n); j++) {
@@ -226,19 +231,19 @@ public class Visval_standard {
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++) {
- vPoint 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++) {
+// vPoint 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<vPoint> results = new ArrayList<>();
@@ -258,47 +263,47 @@ public class Visval_standard {
}
}
- try (FileWriter writer = new FileWriter("fast.csv")) {
- // 写入CSV头部
- writer.append("x,y,z\n");
-
- // 写入每个点的数据
- for (int i = 0; i < results.size(); i++) {
- vPoint 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<vPoint>> resultsBatchList = new ArrayList<>();
-// // 计算运行时间
-// int cnt = 0;
-// startTime = System.currentTimeMillis();
-// for (Polyline polylineBatch : polylineList) {
-// List<vPoint> resultsBatch = new ArrayList<>();
-// buildEffectiveArea(polylineBatch, resultsBatch);
-// cnt += resultsBatch.size();
-// resultsBatchList.add(resultsBatch);
-// }
-// // 输出结果
-// endTime = System.currentTimeMillis();
-// System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms");
-// System.out.println(cnt);
+// try (FileWriter writer = new FileWriter("fast.csv")) {
+// // 写入CSV头部
+// writer.append("x,y,z\n");
//
-// System.out.println("---------------------------------");
-// // 使用 Stream API 合并所有列表
-// List<vPoint> mergedList =
-// resultsBatchList.stream().flatMap(List::stream).collect(Collectors.toList());
-// int sameCnt = 0;
-// for (int i = 0; i < mergedList.size(); i++) {
-// if (mergedList.get(i).z == results.get(i).z) {
-// sameCnt += 1;
+// // 写入每个点的数据
+// for (int i = 0; i < results.size(); i++) {
+// vPoint 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("sameCnt=" + sameCnt + ", percent=" + sameCnt * 1.0 / mergedList.size());
+
+ System.out.println("---------------------------------");
+ List<List<vPoint>> resultsBatchList = new ArrayList<>();
+ // 计算运行时间
+ int cnt = 0;
+ startTime = System.currentTimeMillis();
+ for (Polyline polylineBatch : polylineList) {
+ List<vPoint> resultsBatch = new ArrayList<>();
+ buildEffectiveArea(polylineBatch, resultsBatch);
+ cnt += resultsBatch.size();
+ resultsBatchList.add(resultsBatch);
+ }
+ // 输出结果
+ endTime = System.currentTimeMillis();
+ System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms");
+ System.out.println(cnt);
+
+ System.out.println("---------------------------------");
+ // 使用 Stream API 合并所有列表
+ List<vPoint> mergedList =
+ resultsBatchList.stream().flatMap(List::stream).collect(Collectors.toList());
+ int sameCnt = 0;
+ for (int i = 0; i < mergedList.size(); i++) {
+ if (mergedList.get(i).z == results.get(i).z) {
+ sameCnt += 1;
+ }
+ }
+ System.out.println("sameCnt=" + sameCnt + ", percent=" + sameCnt * 1.0 / mergedList.size());
}
// float[] vlist = new float[]{11346, 33839, 35469, 23108, 22812, 5519, 5526, 4865, 5842,
diff --git a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard_slow.java b/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard_slow.java
deleted file mode 100644
index 33259cc4cff..00000000000
--- a/server/src/main/java/org/apache/iotdb/db/query/simpiece/Visval_standard_slow.java
+++ /dev/null
@@ -1,279 +0,0 @@
-///*
-// * Licensed to the Apache Software Foundation (ASF) under one
-// * or more contributor license agreements. See the NOTICE file
-// * distributed with this work for additional information
-// * regarding copyright ownership. The ASF licenses this file
-// * to you under the Apache License, Version 2.0 (the
-// * "License"); you may not use this file except in compliance
-// * with the License. You may obtain a copy of the License at
-// *
-// * http://www.apache.org/licenses/LICENSE-2.0
-// *
-// * Unless required by applicable law or agreed to in writing,
-// * software distributed under the License is distributed on an
-// * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
-// * KIND, either express or implied. See the License for the
-// * specific language governing permissions and limitations
-// * under the License.
-// */
-//
-//package org.apache.iotdb.db.query.simpiece;
-//
-//import java.io.FileWriter;
-//import java.io.IOException;
-//import java.util.*;
-//import java.util.stream.Collectors;
-//
-//// adapted from the open source C++ code
-//// https://github.com/ofZach/Visvalingam-Whyatt/blob/master/src/testApp.cpp
-//class Triangle {
-//
-// int[] indices = new int[3];
-// double area;
-// Triangle prev;
-// Triangle next;
-//
-// public Triangle(int index1, int index2, int index3, double area) {
-// this.indices[0] = index1;
-// this.indices[1] = index2;
-// this.indices[2] = index3;
-// this.area = area;
-// }
-//}
-//
-//class vPoint {
-//
-// double x, y, z;
-//
-// public vPoint(double x, double y) {
-// this.x = x;
-// this.y = y;
-// this.z = Double.POSITIVE_INFINITY; // effective area
-// }
-//}
-//
-//class Polyline {
-//
-// private List<vPoint> vertices = new ArrayList<>();
-//
-// public void addVertex(vPoint point) {
-// vertices.add(point);
-// }
-//
-// public List<vPoint> getVertices() {
-// return new ArrayList<>(vertices);
-// }
-//
-// public int size() {
-// return vertices.size();
-// }
-//
-// public vPoint get(int index) {
-// return vertices.get(index);
-// }
-//}
-//
-//public class Visval_standard_slow {
-//
-// // 计算三角形面积
-// private static double triArea(vPoint d0, vPoint d1, vPoint d2) {
-// double dArea = ((d1.x - d0.x) * (d2.y - d0.y) - (d2.x - d0.x) * (d1.y - d0.y)) / 2.0;
-// return (double) ((dArea > 0.0) ? dArea : -dArea); // abs
-// }
-//
-// public static void buildEffectiveArea(Polyline lineToSimplify, List<vPoint> results) {
-// results.clear();
-// results.addAll(lineToSimplify.getVertices());
-//
-// int total = lineToSimplify.size();
-// if (total < 3) {
-// return; // 不足 3 个点无法形成三角形
-// }
-//
-// int nTriangles = total - 2;
-// Triangle[] triangles = new Triangle[nTriangles];
-//
-// // 创建所有三角形并计算初始面积
-// for (int i = 1; i < total - 1; i++) {
-// int index1 = i - 1, index2 = i, index3 = i + 1;
-// double area =
-// triArea(
-// lineToSimplify.get(index1), lineToSimplify.get(index2), lineToSimplify.get(index3));
-// triangles[i - 1] = new Triangle(index1, index2, index3, area);
-// }
-//
-// // 设置三角形的前后关系
-// for (int i = 0; i < nTriangles; i++) {
-// triangles[i].prev = (i == 0 ? null : triangles[i - 1]);
-// triangles[i].next = (i == nTriangles - 1 ? null : triangles[i + 1]);
-// }
-//
-// // 使用优先队列构建 minHeap
-// PriorityQueue<Triangle> triangleHeap =
-// new PriorityQueue<>(Comparator.comparingDouble(t -> t.area));
-// Collections.addAll(triangleHeap, triangles);
-//
-// double previousEA = -1;
-// while (!triangleHeap.isEmpty()) {
-// // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作
-// // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小
-// Triangle tri = triangleHeap.poll(); // O(logn)
-//
-//// System.out.println(Arrays.toString(tri.indices));
-//
-// // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标）
-// if (tri.area > previousEA) {
-// previousEA = tri.area;
-// }
-// results.get(tri.indices[1]).z = previousEA;
-// // System.out.println(tri.indices[1] + "," + previousEA);
-//
-// System.out.println(Arrays.toString(tri.indices) + "," + previousEA);
-//
-// // 更新相邻三角形
-// if (tri.prev != null) {
-// // 前一个三角形连到后一个三角形
-// tri.prev.next = tri.next;
-// tri.prev.indices[2] = tri.indices[2];
-// tri.prev.area =
-// triArea(
-// lineToSimplify.get(tri.prev.indices[0]),
-// lineToSimplify.get(tri.prev.indices[1]),
-// lineToSimplify.get(tri.prev.indices[2]));
-//
-// // 重新加入堆
-// // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序
-// // 所以必须通过 remove 和 add 来显式重新插入修改后的元素
-// triangleHeap.remove(tri.prev); // TODO 但是这个操作复杂度是O(n)!!!!
-// triangleHeap.add(tri.prev); // O(logn)
-// }
-//
-// if (tri.next != null) {
-// // 后一个三角形连到前一个三角形
-// tri.next.prev = tri.prev;
-// tri.next.indices[0] = tri.indices[0];
-// tri.next.area =
-// triArea(
-// lineToSimplify.get(tri.next.indices[0]),
-// lineToSimplify.get(tri.next.indices[1]),
-// lineToSimplify.get(tri.next.indices[2]));
-//
-// // 重新加入堆
-// triangleHeap.remove(tri.next);
-// triangleHeap.add(tri.next);
-// }
-// }
-// }
-//
-// public static void main(String[] args) {
-// Polyline polyline = new Polyline();
-// List<Polyline> polylineList = new ArrayList<>();
-// Random rand = new Random(1);
-//// int n = 1000_000;
-// int n = 100000;
-//
-// int p = 100;
-// for (int i = 0; i < n; i += p) {
-// Polyline polylineBatch = new Polyline();
-// for (int j = i; j < Math.min(i + p, n); j++) {
-// double v = rand.nextInt(1000000);
-//
-// polyline.addVertex(new vPoint(j, v));
-//
-// polylineBatch.addVertex(new vPoint(j, v));
-// }
-// polylineList.add(polylineBatch);
-// }
-//
-// System.out.println("---------------------------------");
-// List<vPoint> results = new ArrayList<>();
-// // 计算运行时间
-// long startTime = System.currentTimeMillis();
-// buildEffectiveArea(polyline, results);
-// // 输出结果
-// 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++) {
-// vPoint point = results.get(i);
-// System.out.println("Point: (" + point.x + ", " + point.y + ", " + point.z + ")");
-// }
-// }
-//
-// try (FileWriter writer = new FileWriter("slow.csv")) {
-// // 写入CSV头部
-// writer.append("x,y,z\n");
-//
-// // 写入每个点的数据
-// for (int i = 0; i < results.size(); i++) {
-// vPoint 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<vPoint>> resultsBatchList = new ArrayList<>();
-//// // 计算运行时间
-//// int cnt = 0;
-//// startTime = System.currentTimeMillis();
-//// for (Polyline polylineBatch : polylineList) {
-//// List<vPoint> resultsBatch = new ArrayList<>();
-//// buildEffectiveArea(polylineBatch, resultsBatch);
-//// cnt += resultsBatch.size();
-//// resultsBatchList.add(resultsBatch);
-//// }
-//// // 输出结果
-//// endTime = System.currentTimeMillis();
-//// System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms");
-//// System.out.println(cnt);
-////
-//// System.out.println("---------------------------------");
-//// // 使用 Stream API 合并所有列表
-//// List<vPoint> mergedList =
-//// resultsBatchList.stream().flatMap(List::stream).collect(Collectors.toList());
-//// int sameCnt = 0;
-//// for (int i = 0; i < mergedList.size(); i++) {
-//// if (mergedList.get(i).z == results.get(i).z) {
-//// sameCnt += 1;
-//// }
-//// }
-//// System.out.println("sameCnt=" + sameCnt + ", percent=" + sameCnt * 1.0 / mergedList.size());
-//
-//
-//
-//
-//
-//
-//
-//// float[] vlist = new float[]{11346, 33839, 35469, 23108, 22812, 5519, 5526, 4865, 5842,
-//// 23089};
-//// for (int i = 0; i < vlist.length; i++) {
-//// polyline.addVertex(new vPoint(i, vlist[i]));
-//// }
-////
-//// ArrayList<Double> v = new ArrayList<>();
-//// String filePath = "D://datasets//regular//New York Stock Exchange//merged_prices.csv";
-//// try (BufferedReader br = new BufferedReader(new FileReader(filePath))) {
-//// String line;
-//// int count = 0;
-//// while ((line = br.readLine()) != null && count < 1000) {
-//// String[] columns = line.split(","); // 假设 CSV 文件以逗号分隔
-//// v.add(Double.parseDouble(columns[0])); // 读取第一列数据
-//// count++;
-//// }
-//// } catch (Exception e) {
-//// e.printStackTrace();
-//// }
-//// // 打印数据长度
-//// System.out.println("Data length: " + v.size());
-//// for (int i = 0; i < v.size(); i++) {
-//// polyline.addVertex(new vPoint(i, v.get(i)));
-//// }
-// }
-//}