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 98cdae627c79981b57c75de2eceec1913d99d1f9 Author: Lei Rui <[email protected]> AuthorDate: Thu Jan 23 02:56:14 2025 +0800 Add --- .../java/org/apache/iotdb/db/query/eBUG/Point.java | 20 ++ .../org/apache/iotdb/db/query/eBUG/Polyline.java | 4 + .../java/org/apache/iotdb/db/query/eBUG/Test1.java | 6 +- .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 175 +++++------ .../eBUG/eBUG_circulateArrayForEliminated.java | 325 +++++++++++++++++++++ 5 files changed, 439 insertions(+), 91 deletions(-) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java index 77ebdb4cb39..70aa19ea531 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Point.java @@ -4,10 +4,30 @@ public class Point { double x, y, z; +// public boolean eliminated; // 滞后e个淘汰点 for eBUG usage + public Point prev; // 指向T'_max{0,k-e}里当前点的前一个点 for eBUG usage + public Point next; // 指向T'_max{0,k-e}里当前点的后一个点 for eBUG usage + // 注意Triangle里的prev&next用于最新状态下存在三角形之间的连接关系， + // 而这里Point的prev&next用于滞后e个淘汰点（也就是最近的e个淘汰点先不施加）状态下的未淘汰点之间的连接关系 + public Point(double x, double y) { this.x = x; this.y = y; this.z = Double.POSITIVE_INFINITY; // effective area + + // for eBUG usage +// this.eliminated = false; + this.prev = null; + this.next = null; + } + + public void markEliminated() { +// eliminated = true; + + // to avoid traversing each point between pa to pb, + // instead only traversing at most e most recently eliminated points lagged + prev.next = next; + next.prev = prev; } @Override diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java index bed14731832..1ddfe2ebbe1 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Polyline.java @@ -8,6 +8,10 @@ public class Polyline { private List<Point> vertices = new ArrayList<>(); public void addVertex(Point point) { +// if (!vertices.isEmpty()) { //before adding this point +// vertices.get(vertices.size() - 1).next = point; +// point.prev = vertices.get(vertices.size() - 1); +// } vertices.add(point); } diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java index 56e73cc17e0..28b0eebd53e 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Test1.java @@ -43,11 +43,7 @@ public class Test1 { } System.out.println("---------------------------------"); -// List<Point> results = new ArrayList<>(); - // 计算运行时间 -// int eParam = 10; -// for (int eParam = 0; eParam < 2 * n; eParam += 1000) { - int eParam = 2; + int eParam = 1000000; 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.java index 77e21a27067..906bc4e2366 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 @@ -29,56 +29,35 @@ import static org.apache.iotdb.db.query.eBUG.Tool.triArea; public class eBUG { - public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, - int pa_idx, int pi_idx, int pb_idx) { - // 复杂度分析 记c=b-a。 - // 如果e<c，那么从最近淘汰的e个点里寻找位于pa~pb之间的，找到的点和pa pi pb一起按照时间戳递增排序，后面鞋带公式计算面积：O(e+eloge) - // 否则e>=c，直接取T[a:b]，已经排序号了，后面鞋带公式计算面积：O(c) - - // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ - - // pi: the point whose significance needs updating + public static List<Point> findEliminated(Polyline lineToSimplify, int pa_idx, int pb_idx) { // pa: left adjacent non-eliminated point of pi // pb: right adjacent non-eliminated point of pi - // return a list of points, containing pa,p,pb and points between pa&pa from the e most recently eliminated points, - // order by time in ascending order + // return a list of points, T'_max{0,k-e}[a:b] order by time in ascending order - Point pa = lineToSimplify.get(pa_idx); - Point pi = lineToSimplify.get(pi_idx); - Point pb = lineToSimplify.get(pb_idx); + // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！至于其他全局更早淘汰的点则不一定位于a:b之间 + // pa,xxx,pi,xxx,pb + // when e=0，遍历点数就是3 + // when e>0，遍历点数大于等于4、小于等于e+3 List<Point> res = new ArrayList<>(); - - // TODO note: here may happen because e=c=0 or just 0<c<=e - 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 - res = lineToSimplify.getVertices().subList(pa_idx, pb_idx + 1); // 左闭右开 - return res; // 已经按照时间戳递增 + Point start = lineToSimplify.get(pa_idx); + Point end = lineToSimplify.get(pb_idx); +// int cnt = 0; + while (start != end) { // Point类里增加prev&next指针，这样T'_max{0,k-e}里点的连接关系就有了，这样从Pa开始沿着指针，遍历点数一定不超过e+3 + res.add(start); + start = start.next; // when e=0, only traversing three points pa pi pb +// cnt += 1; } - - // TODO note: here may happen because c>e=0 or c>e>0. the latter needs search among recentEliminated and sort by timestamp - // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 -// System.out.println("k>=[c=(b-a-2)]>e, search among e"); - res.add(pa); // 注意pa pi pb已经按照时间戳递增 - 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 - break; - } - Point p = lineToSimplify.get(idx); - if (p.x > pa.x && p.x < pb.x) { - res.add(p); - } - } - - // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 - if (recentEliminated.length > 0) { // 否则e=0，不需要排序pa pi pb三个点 - res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 这样的话时间复杂度变成e*log(e) - } - + res.add(end); +// cnt += 1; +// System.out.println(cnt); // 3<=cnt<=e+3 + +// for (int i = pa_idx; i <= pb_idx; i++) { // 左闭右闭 +// Point p = lineToSimplify.get(i); +// if (!p.eliminated) { +// res.add(p); +// } +// } return res; } @@ -90,8 +69,12 @@ public class eBUG { List<Point> results = lineToSimplify.getVertices(); // 浅复制 // 用循环数组来记录最近淘汰的点 - 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 + + // 存储的是点的引用，这样可以修改原来序列里点的淘汰状态 + // 存储的是距离当前最新状态的滞后的尚未施加、待施加的e个淘汰点 + LinkedList<Point> laggedEliminatedPoints = new LinkedList<>(); int total = lineToSimplify.size(); if (total < 3) { @@ -102,10 +85,21 @@ public class eBUG { Triangle[] triangles = new Triangle[nTriangles]; // 创建所有三角形并计算初始面积 +// lineToSimplify.get(0).eliminated = false; // 初始化点的状态 for eBUG usage + lineToSimplify.get(0).prev = null; + lineToSimplify.get(0).next = lineToSimplify.get(1); +// lineToSimplify.get(total - 1).eliminated = false; // 初始化点的状态 for eBUG usage + lineToSimplify.get(total - 1).next = null; + lineToSimplify.get(total - 1).prev = lineToSimplify.get(total - 2); 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 eBUG usage +// lineToSimplify.get(i).eliminated = false; + lineToSimplify.get(i).prev = lineToSimplify.get(i - 1); + lineToSimplify.get(i).next = lineToSimplify.get(i + 1); } // 设置三角形的前后关系 @@ -138,12 +132,18 @@ public class eBUG { if (debug) { 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 + if (e > 0) { + if (laggedEliminatedPoints.size() == e) { + // 已经有e个滞后淘汰点了，为了把最近淘汰点加入，得先把最老的淘汰点施加上去 + Point removedPoint = laggedEliminatedPoints.removeFirst(); // 取出最早加入的淘汰点 复杂度1 + removedPoint.markEliminated(); // 注意是引用，所以改的内容后面可以看到 + } + laggedEliminatedPoints.addLast(lineToSimplify.get(tri.indices[1])); // 加入最新的淘汰点，滞后在这里先不施加 + } else { // e=0 没有滞后 立即标记删除 T'_k + lineToSimplify.get(tri.indices[1]).markEliminated(); } if (debug) { - System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); + System.out.println("the e most recently eliminated points (lagged):" + laggedEliminatedPoints); } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） @@ -172,12 +172,10 @@ public class eBUG { tri.prev.indices[2] = tri.indices[2]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, - tri.prev.indices[0], - tri.prev.indices[1], - tri.prev.indices[2]); // TODO complexity ? + List<Point> pointsForSig = findEliminated(lineToSimplify, tri.prev.indices[0], tri.prev.indices[2]); if (debug) { System.out.println("(2) update point on the left " + lineToSimplify.get(tri.prev.indices[1])); + System.out.println("3<=cnt<=e+3. cnt=" + pointsForSig.size()); for (Point point : pointsForSig) { System.out.println("\t" + point); } @@ -221,12 +219,10 @@ public class eBUG { tri.next.indices[0] = tri.indices[0]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, - tri.next.indices[0], - tri.next.indices[1], - tri.next.indices[2]); // TODO complexity + List<Point> pointsForSig = findEliminated(lineToSimplify, tri.next.indices[0], tri.next.indices[2]); if (debug) { System.out.println("(2) updating point on the right " + lineToSimplify.get(tri.next.indices[1])); + System.out.println("3<=cnt<=e+3. cnt=" + pointsForSig.size()); for (Point point : pointsForSig) { System.out.println("\t" + point); } @@ -259,45 +255,52 @@ public class eBUG { public static void main(String[] args) { - int eParam = 2000_0000; - try (PrintWriter writer = new PrintWriter(new File("exp_varyN_e" + eParam + ".csv"))) { - for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度 - // TODO 注意 要有一个点是n=300w - - Polyline polyline = new Polyline(); - int seed = 1; - Random rand = new Random(seed); // TODO 注意seed在每轮里重设 - for (int i = 0; i < n; i++) { - double v = rand.nextInt(1000000); - polyline.addVertex(new Point(i, v)); - } +// int eParam = 0; + int[] eParamList = {0, 1, 2, 3, 4, 5, 10, 14, 15, 16, 20, 30, 40, 50, 100, 200, 500, 1000, 2000, 5000, + 10000, 50000, 10_0000, 50_0000, 100_0000, 200_0000, 300_0000, + 500_0000, 800_0000, 1000_0000, + 1500_0000, 2000_0000, 2500_0000, 3000_0000}; + for (int eParam : eParamList) { + try (PrintWriter writer = new PrintWriter(new File("exp_varyN_e" + eParam + ".csv"))) { + for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度 + // TODO 注意 要有一个点是n=300w + + Polyline polyline = new Polyline(); + int seed = 1; + Random rand = new Random(seed); // TODO 注意seed在每轮里重设 + for (int i = 0; i < n; i++) { + double v = rand.nextInt(1000000); + polyline.addVertex(new Point(i, v)); + } - long startTime = System.currentTimeMillis(); - List<Point> results = buildEffectiveArea(polyline, eParam, false); - long endTime = System.currentTimeMillis(); + 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"); - writer.println(n + "," + eParam + "," + (endTime - startTime)); - System.out.println(results.size()); + System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms"); + writer.println(n + "," + eParam + "," + (endTime - startTime)); + System.out.println(results.size()); - // clear - polyline.clear(); - results.clear(); - polyline = null; - results = null; - System.gc(); +// // clear +// polyline.clear(); +// results.clear(); +// polyline = null; +// results = null; +// System.gc(); + } + } catch (FileNotFoundException e) { + throw new RuntimeException(e); } - } catch (FileNotFoundException e) { - throw new RuntimeException(e); } // int n = 300_0000; +// // int seed = 1; // Random rand = new Random(seed); // TODO 注意seed在每轮里重设 // Polyline polyline = new Polyline(); // 注意：如果是固定n变化e实验，这个数据要一次性生成，不然每次随机不一样 // for (int i = 0; i < n; i++) { // double v = rand.nextInt(1000000); -// polyline.addVertex(new Point(i, v)); +// polyline.addVertex(new Point(i, v)); // point的状态会在buildEffectiveArea里重置的，所以在下面的e遍历里可以复用这一份数据 // } // // try (PrintWriter writer = new PrintWriter(new File("exp_varyE_n" + n + ".csv"))) { @@ -314,7 +317,7 @@ public class eBUG { // System.out.println(results.size()); // // // clear 注意不能把原始数据清除，还要接着用 -// System.gc(); +//// System.gc(); // } // } catch (FileNotFoundException e) { // throw new RuntimeException(e); diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_circulateArrayForEliminated.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_circulateArrayForEliminated.java new file mode 100644 index 00000000000..38e9c96ad4e --- /dev/null +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_circulateArrayForEliminated.java @@ -0,0 +1,325 @@ +///* +// * 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.eBUG; +// +//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_circulateArrayForEliminated { +// public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, +// int pa_idx, int pi_idx, int pb_idx) { +// // 复杂度分析 记c=b-a。 +// // 如果e<c，那么从最近淘汰的e个点里寻找位于pa~pb之间的，找到的点和pa pi pb一起按照时间戳递增排序，后面鞋带公式计算面积：O(e+eloge) +// // 否则e>=c，直接取T[a:b]，已经排序号了，后面鞋带公式计算面积：O(c) +// +// // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ +// +// // pi: the point whose significance needs updating +// // pa: left adjacent non-eliminated point of pi +// // pb: right adjacent non-eliminated point of pi +// // return a list of points, containing pa,p,pb and points between pa&pa from the e most recently eliminated points, +// // order by time in ascending order +// +// Point pa = lineToSimplify.get(pa_idx); +// Point pi = lineToSimplify.get(pi_idx); +// Point pb = lineToSimplify.get(pb_idx); +// +// List<Point> res = new ArrayList<>(); +// +// // TODO note: here may happen because e=c=0 or just 0<c<=e +// 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 +// res = lineToSimplify.getVertices().subList(pa_idx, pb_idx + 1); // 左闭右开 +// return res; // 已经按照时间戳递增 +// } +// +// // TODO note: here may happen because c>e=0 or c>e>0. the latter needs search among recentEliminated and sort by timestamp +// // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 +//// System.out.println("k>=[c=(b-a-2)]>e, search among e"); +// res.add(pa); // 注意pa pi pb已经按照时间戳递增 +// 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 +// break; +// } +// Point p = lineToSimplify.get(idx); +// if (p.x > pa.x && p.x < pb.x) { +// res.add(p); +// } +// } +// +// // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 +// if (recentEliminated.length > 0) { // 否则e=0，不需要排序pa pi pb三个点 +// res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 这样的话时间复杂度变成e*log(e) +// } +// +// return res; +// } +// +// public static List<Point> buildEffectiveArea(Polyline lineToSimplify, int e, boolean debug) { +// if (e < 0) { +// throw new IllegalArgumentException("Parameter e must be non-negative."); +// } +// +// List<Point> results = lineToSimplify.getVertices(); // 浅复制 +// +// // 用循环数组来记录最近淘汰的点 +// int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated +// int recentEliminatedIdx = 0; // index in the array, circulate +// +// int total = lineToSimplify.size(); +// if (total < 3) { +// return results; // 不足 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++) { // TODO 这个可以和上一个循环合并吗？？好像不可以 +// 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); // complexity TODO O(n) or O(nlogn)? +// +// double previousEA = -1; +// while (!triangleHeap.isEmpty()) { +// // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作 +// // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小 +// Triangle tri = triangleHeap.poll(); // O(logn) +// +// // 如果该三角形已经被删除，跳过. Avoid using heap.remove(x) as it is O(n) complexity +// // 而且除了heap里，已经没有其他节点会和它关联了，所有的connections关系已经迁移到新的角色替代节点上 +// if (tri.isDeleted) { +// if (debug) { +// System.out.println(">>>bottom-up, remaining " + triangleHeap.size() + " triangles (including those marked for removal)"); +// } +// continue; +// } +// +// // 真正的淘汰点 +// // 记录最近淘汰的点，注意不要重复记录也就是在上面执行之后再确认淘汰 +// if (debug) { +// 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 +// } +// if (debug) { +// System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); +// } +// +// // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） +// if (tri.area > previousEA) { +// previousEA = tri.area; +// } +// results.get(tri.indices[1]).z = previousEA; // dominated significance +// if (debug) { +// System.out.println(Arrays.toString(tri.indices) + ", Dominated Sig=" + 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因为那太耗时，只要heap poll到它就跳过就可以 +// +// Triangle newPre = new Triangle(tri.prev); // deep copy and inherit connection +// // tri.prev = newPre; // can omit, because already done by new Triangle(tri.prev) +// +// // 2. 处理pi被淘汰引起tri.prev被更新的事情 +// // 前一个三角形连到后一个三角形 +// tri.prev.next = tri.next; // ATTENTION!!!: 这里的tri.next后面可能会因为处理旧的tri.next被标记删除的事情被换掉！到时候要重新赋值！ +// tri.prev.indices[2] = tri.indices[2]; +// +// // e parameter +// List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, +// tri.prev.indices[0], +// tri.prev.indices[1], +// tri.prev.indices[2]); // TODO complexity ? +// if (debug) { +// System.out.println("(2) update point on the left " + lineToSimplify.get(tri.prev.indices[1])); +// for (Point point : pointsForSig) { +// System.out.println("\t" + point); +// } +// } +// List<Point> baseLine = new ArrayList<>(); +// baseLine.add(pointsForSig.get(0)); +// baseLine.add(pointsForSig.get(pointsForSig.size() - 1)); // 直接连接左右两边最近的未被淘汰的点 +// double sig = total_areal_displacement(pointsForSig, baseLine, false); +// tri.prev.area = sig; +// +// if (debug) { +// System.out.println("sig=" + sig); +// double tmpTri = triArea(lineToSimplify.get(tri.prev.indices[0]), +// lineToSimplify.get(tri.prev.indices[1]), +// lineToSimplify.get(tri.prev.indices[2])); +// System.out.println("\t" + "tri=" + tmpTri + ", " + ((tmpTri > sig) ? "over-estimated" : "equal/less-estimated")); +// } +// +// // 重新加入堆 +// // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 +// // 所以必须通过add来显式重新插入修改后的元素 +// triangleHeap.add(tri.prev); // O(logn) 注意加入的是一个新的对象isDeleted=false +// } +// +// 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到它就跳过就可以 +// +// Triangle newNext = new Triangle(tri.next); // deep copy and inherit connection +// // tri.next = newNext; // omit, because already done by new Triangle(tri.prev) +// +// if (tri.prev != null) { +// tri.prev.next = tri.next; // ATTENTION!!!: 这里的tri.next已经被换掉！所以之前的要重新赋值！ +// } +// +// // 2. 处理pi被淘汰引起tri.next被更新的事情 +// tri.next.prev = tri.prev; // 注意此时tri.prev已经是替代后的节点，tri.next也是，从而被标记为废点的前后关联真正砍断 +// tri.next.indices[0] = tri.indices[0]; +// +// // e parameter +// List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, +// tri.next.indices[0], +// tri.next.indices[1], +// tri.next.indices[2]); // TODO complexity +// if (debug) { +// System.out.println("(2) updating point on the right " + lineToSimplify.get(tri.next.indices[1])); +// for (Point point : pointsForSig) { +// System.out.println("\t" + point); +// } +// } +// List<Point> baseLine = new ArrayList<>(); +// baseLine.add(pointsForSig.get(0)); +// baseLine.add(pointsForSig.get(pointsForSig.size() - 1)); // 直接连接左右两边最近的未被淘汰的点 +// double sig = total_areal_displacement(pointsForSig, baseLine, false); +// tri.next.area = sig; +// +// if (debug) { +// System.out.println("sig=" + sig); +// double tmpTri = triArea(lineToSimplify.get(tri.next.indices[0]), +// lineToSimplify.get(tri.next.indices[1]), +// lineToSimplify.get(tri.next.indices[2])); +// System.out.println("\t" + "tri=" + tmpTri + ", " + ((tmpTri > sig) ? "over-estimated" : "equal/less-estimated")); +// } +// +// // 重新加入堆 +// // 在 Java 的 PriorityQueue 中，修改元素的属性不会自动更新堆的顺序 +// // 所以必须通过add 来显式重新插入修改后的元素 +// triangleHeap.add(tri.next); // 注意加入的是一个新的对象isDeleted=false +// } +// if (debug) { +// System.out.println(">>>bottom-up, remaining " + triangleHeap.size() + " triangles (including those marked for removal)"); +// } +// } +// return results; // 注意这就是lineToSimplify.getVertices() +// } +// +// public static void main(String[] args) { +// +// int eParam = 2000_0000; +// try (PrintWriter writer = new PrintWriter(new File("exp_varyN_e" + eParam + ".csv"))) { +// for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度 +// // TODO 注意 要有一个点是n=300w +// +// Polyline polyline = new Polyline(); +// int seed = 1; +// Random rand = new Random(seed); // TODO 注意seed在每轮里重设 +// for (int i = 0; i < n; i++) { +// double v = rand.nextInt(1000000); +// polyline.addVertex(new Point(i, v)); +// } +// +// 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"); +// writer.println(n + "," + eParam + "," + (endTime - startTime)); +// System.out.println(results.size()); +// +// // clear +// polyline.clear(); +// results.clear(); +// polyline = null; +// results = null; +// System.gc(); +// } +// } catch (FileNotFoundException e) { +// throw new RuntimeException(e); +// } +// +//// int n = 300_0000; +//// int seed = 1; +//// Random rand = new Random(seed); // TODO 注意seed在每轮里重设 +//// Polyline polyline = new Polyline(); // 注意：如果是固定n变化e实验，这个数据要一次性生成，不然每次随机不一样 +//// for (int i = 0; i < n; i++) { +//// double v = rand.nextInt(1000000); +//// polyline.addVertex(new Point(i, v)); +//// } +//// +//// try (PrintWriter writer = new PrintWriter(new File("exp_varyE_n" + n + ".csv"))) { +//// int[] eParamList = {0, 1, 2, 10, 1000, 10000, 10_0000, 30_0000, 50_0000, 60_0000, 80_0000, 100_0000, 150_0000, 200_0000}; +//// for (int eParam : eParamList) { +//// eParam *= 3; // TODO 注意 因为n=300w而不是100w +//// +//// 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"); +//// writer.println(n + "," + eParam + "," + (endTime - startTime)); +//// System.out.println(results.size()); +//// +//// // clear 注意不能把原始数据清除，还要接着用 +//// System.gc(); +//// } +//// } catch (FileNotFoundException e) { +//// throw new RuntimeException(e); +//// } +// +// System.out.println("finish"); +// } +//}
