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 c35524ad1a6f3f26a393b3df18e2a3ab1192d74a Author: Lei Rui <[email protected]> AuthorDate: Mon Feb 24 01:40:29 2025 +0800 add --- .../apache/iotdb/db/query/eBUG/BottomUpYdiff.java | 4 +- .../java/org/apache/iotdb/db/query/eBUG/DNSL1.java | 160 ++++++------- .../iotdb/db/query/eBUG/LTD_slow_deprecated.java | 255 --------------------- .../java/org/apache/iotdb/db/query/eBUG/Rdp.java | 2 +- .../java/org/apache/iotdb/db/query/eBUG/SWAB.java | 6 +- .../org/apache/iotdb/db/query/eBUG/SWAB_AD.java | 4 +- .../java/org/apache/iotdb/db/query/eBUG/Tmp.java | 44 ---- .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 6 +- 8 files changed, 91 insertions(+), 390 deletions(-) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/BottomUpYdiff.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/BottomUpYdiff.java index 6090415241f..ee78ec309a2 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/BottomUpYdiff.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/BottomUpYdiff.java @@ -42,7 +42,7 @@ public class BottomUpYdiff { } // 设置三角形的前后关系 - for (int i = 0; i < nTriangles; i++) { // TODO 这个可以和上一个循环合并吗？？好像不可以 + 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]); } @@ -50,7 +50,7 @@ public class BottomUpYdiff { // 使用优先队列构建 minHeap PriorityQueue<Triangle> triangleHeap = new PriorityQueue<>(Comparator.comparingDouble(t -> t.area)); - Collections.addAll(triangleHeap, triangles); // complexity TODO O(n) or O(nlogn)? + Collections.addAll(triangleHeap, triangles); int remainNonTerminalPoint = m - 2; int fakeCnt = 0; diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java index 28f26a3f619..e28f347a1d5 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/DNSL1.java @@ -9,94 +9,94 @@ import java.util.Random; import static org.apache.iotdb.db.query.eBUG.DP.dynamic_programming; public class DNSL1 { - // 默认使用linear interpolation连接分段首尾点来近似 - // 默认使用L1 error - // 使用divide and conquer算法 - public static List<Point> reducePoints(List<Point> points, int m, boolean debug) { - int n = points.size(); - int k = m - 1; // 分段数 - int intervalNum = (int) Math.pow((double) n / k, (double) 2 / 3); // divide batch点数 - int intervalPts = n / intervalNum; + // 默认使用linear interpolation连接分段首尾点来近似 + // 默认使用L1 error + // 使用divide and conquer算法 + public static List<Point> reducePoints(List<Point> points, int m, boolean debug) { + int n = points.size(); + int k = m - 1; // 分段数 + int intervalNum = (int) Math.pow((double) n / k, (double) 2 / 3); // divide batch点数 + int intervalPts = n / intervalNum; - if (debug) { - System.out.println("interval point length=" + intervalPts); - } + if (debug) { + System.out.println("interval point length=" + intervalPts); + } - // divide into intervalPts equal-length intervals - List<Point> allSampledPoints = new ArrayList<>(); - for (int start = 0; start < n; start += intervalPts) { - int end = Math.min(start + intervalPts, n); - List<Point> batch = points.subList(start, end); // 左闭右开 - if (debug) { - System.out.println("Processing batch: [" + start + "," + end + ")"); - } - List<Point> sampledForBatch = dynamic_programming(batch, k, DP.ERRORtype.L1, false); - allSampledPoints.addAll(sampledForBatch); // 把上一步的结果加到大的容器里 - } + // divide into intervalPts equal-length intervals + List<Point> allSampledPoints = new ArrayList<>(); + for (int start = 0; start < n; start += intervalPts) { + int end = Math.min(start + intervalPts, n); + List<Point> batch = points.subList(start, end); // 左闭右开 + if (debug) { + System.out.println("Processing batch: [" + start + "," + end + ")"); + } + List<Point> sampledForBatch = dynamic_programming(batch, k, DP.ERRORtype.L1, false); + allSampledPoints.addAll(sampledForBatch); // 把上一步的结果加到大的容器里 + } - // 在大的容器上最后执行DP.dynamic_programming得到最后的m个采样点 - if (debug) { - System.out.println("number of points from batch sampling: " + allSampledPoints.size()); - } + // 在大的容器上最后执行DP.dynamic_programming得到最后的m个采样点 + if (debug) { + System.out.println("number of points from batch sampling: " + allSampledPoints.size()); + } - // TODO 但是注意这里用的是linear interpolation近似，而不是DNS原文的constant - List<Point> finalSampledPoints = - dynamic_programming(allSampledPoints, k, DP.ERRORtype.L1, false); - if (debug) { - System.out.println("result point number: " + finalSampledPoints.size()); - } - return finalSampledPoints; + // TODO 但是注意这里用的是linear interpolation近似，而不是DNS原文的constant + List<Point> finalSampledPoints = + dynamic_programming(allSampledPoints, k, DP.ERRORtype.L1, false); + if (debug) { + System.out.println("result point number: " + finalSampledPoints.size()); } + return finalSampledPoints; + } - public static void main(String[] args) { - Random rand = new Random(10); - String input = "raw.csv"; - boolean hasHeader = true; - int timeIdx = 0; - int valueIdx = 1; - int N = 100_0000; -// List<Point> points = Tool.readFromFile(input, hasHeader, timeIdx, valueIdx, N); - Polyline polyline = new Polyline(); - for (int i = 0; i < N; i += 1) { - double v = rand.nextInt(1000); - polyline.addVertex(new Point(i, v)); - } - List<Point> points = polyline.getVertices(); - try (FileWriter writer = new FileWriter("raw.csv")) { - // 写入CSV头部 - writer.append("x,y,z\n"); + public static void main(String[] args) { + Random rand = new Random(10); + String input = "raw.csv"; + boolean hasHeader = true; + int timeIdx = 0; + int valueIdx = 1; + int N = 100_0000; + // List<Point> points = Tool.readFromFile(input, hasHeader, timeIdx, valueIdx, N); + Polyline polyline = new Polyline(); + for (int i = 0; i < N; i += 1) { + double v = rand.nextInt(1000); + polyline.addVertex(new Point(i, v)); + } + List<Point> points = polyline.getVertices(); + try (FileWriter writer = new FileWriter("raw.csv")) { + // 写入CSV头部 + writer.append("x,y,z\n"); - // 写入每个点的数据 - for (Point point : points) { - writer.append(point.x + "," + point.y + "," + point.z + "\n"); - } - System.out.println(points.size() + " Data has been written"); - } catch (IOException e) { - System.out.println("Error writing to CSV file: " + e.getMessage()); - } + // 写入每个点的数据 + for (Point point : points) { + writer.append(point.x + "," + point.y + "," + point.z + "\n"); + } + System.out.println(points.size() + " Data has been written"); + } catch (IOException e) { + System.out.println("Error writing to CSV file: " + e.getMessage()); + } - // int m = (int) Math.pow(points.size(), 0.5); - int m = 1_000; + // int m = (int) Math.pow(points.size(), 0.5); + int m = 1_000; - // long startTime = System.currentTimeMillis(); - // List<Point> sampled = dynamic_programming(points, m - 1, DP.ERROR.area, false); - // long endTime = System.currentTimeMillis(); - // System.out.println("Time taken: " + (endTime - startTime) + "ms"); - // for (Point p : sampled) { - // System.out.println(p); - // } - // System.out.println(sampled.size()); + // long startTime = System.currentTimeMillis(); + // List<Point> sampled = dynamic_programming(points, m - 1, DP.ERROR.area, false); + // long endTime = System.currentTimeMillis(); + // System.out.println("Time taken: " + (endTime - startTime) + "ms"); + // for (Point p : sampled) { + // System.out.println(p); + // } + // System.out.println(sampled.size()); - long startTime2 = System.currentTimeMillis(); - // System.out.println(points.size() * m / (Math.pow(points.size() * 1.0 / (m - 1), 2 / - // 3.0))); - // System.out.println(10000000 * (2 / (Math.pow(10000000 * 1.0 / (2 - 1), 2 / 3.0)))); - List<Point> sampled2 = reducePoints(points, m, true); - long endTime2 = System.currentTimeMillis(); - System.out.println("Time taken: " + (endTime2 - startTime2) + "ms"); - // for (Point p : sampled2) { - // System.out.println(p); - // } - // System.out.println(sampled2.size()); - } + long startTime2 = System.currentTimeMillis(); + // System.out.println(points.size() * m / (Math.pow(points.size() * 1.0 / (m - 1), 2 / + // 3.0))); + // System.out.println(10000000 * (2 / (Math.pow(10000000 * 1.0 / (2 - 1), 2 / 3.0)))); + List<Point> sampled2 = reducePoints(points, m, true); + long endTime2 = System.currentTimeMillis(); + System.out.println("Time taken: " + (endTime2 - startTime2) + "ms"); + // for (Point p : sampled2) { + // System.out.println(p); + // } + // System.out.println(sampled2.size()); + } } diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/LTD_slow_deprecated.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/LTD_slow_deprecated.java deleted file mode 100644 index 7746a5c8f8d..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/LTD_slow_deprecated.java +++ /dev/null @@ -1,255 +0,0 @@ -package org.apache.iotdb.db.query.eBUG; - -import java.io.*; -import java.util.ArrayList; -import java.util.LinkedList; -import java.util.List; -import java.util.Random; - -public class LTD_slow_deprecated { - public static Point calculateAveragePoint(List<Point> points, int startClosed, int endClosed) { - double sumX = 0; - double sumY = 0; - for (int i = startClosed; i <= endClosed; i++) { - sumX += points.get(i).x; - sumY += points.get(i).y; - } - int len = endClosed - startClosed + 1; - return new Point(sumX / len, sumY / len); - } - - public static double[] calculateLinearRegressionCoefficients( - List<Point> points, int startClosed, int endClosed) { - Point averages = calculateAveragePoint(points, startClosed, endClosed); - double avgX = averages.x; - double avgY = averages.y; - - double aNumerator = 0.0; - double aDenominator = 0.0; - for (int i = startClosed; i <= endClosed; i++) { - aNumerator += (points.get(i).x - avgX) * (points.get(i).y - avgY); - aDenominator += (points.get(i).x - avgX) * (points.get(i).x - avgX); - } - - double a = aNumerator / aDenominator; - double b = avgY - a * avgX; - - return new double[] {a, b}; - } - - public static double calculateSSEForBucket(List<Point> points, int startClosed, int endClosed) { - double[] coefficients = calculateLinearRegressionCoefficients(points, startClosed, endClosed); - double a = coefficients[0]; - double b = coefficients[1]; - - double sse = 0.0; - - for (int i = startClosed; i <= endClosed; i++) { - double error = points.get(i).y - (a * points.get(i).x + b); - sse += error * error; - } - - return sse; - } - - public static List<Integer> getLtdBinIdxs(List<Point> points, int m, int maxIter, boolean debug) { - int numOfIterations = (int) (points.size() * 1.0 / m * 10); - if (maxIter >= 0) { - // numOfIterations = Math.min(numOfIterations, maxIter); - numOfIterations = maxIter; // overwrite - } - double blockSize = (points.size() - 3) * 1.0 / (m - 2); - - List<Integer> offset = new LinkedList<>(); - for (double i = 1; i < points.size(); i += blockSize) { - offset.add((int) i); // 1~n-2, 这样最后一个offset+1才不会超出边界 - } - if (debug) { - System.out.println("numOfIterations=" + numOfIterations); - System.out.println(offset); - } - - List<Double> sse = new LinkedList<>(); - - // Initialization - for (int i = 0; i < m - 2; i++) { - // with one extra point overlapping for each adjacent bucket - sse.add(calculateSSEForBucket(points, offset.get(i) - 1, offset.get(i + 1) + 1)); - } - - for (int c = 0; c < numOfIterations; c++) { - if (debug) { - System.out.println("--------------[" + c + "]----------------"); - } - // Find the bucket to be split - int maxSSEIndex = -1; - double maxSSE = Double.NEGATIVE_INFINITY; - for (int i = 0; i < m - 2; i++) { - if (offset.get(i + 1) - offset.get(i) <= 1) { - continue; - } - if (sse.get(i) > maxSSE) { - maxSSE = sse.get(i); - maxSSEIndex = i; - } - } - if (maxSSEIndex < 0) { - if (debug) { - System.out.println(c); - System.out.println(maxSSEIndex); - System.out.println("break max"); - } - break; - } - - // Find the buckets to be merged - int minSSEIndex = -1; - double minSSE = Double.POSITIVE_INFINITY; - for (int i = 0; i < m - 3; i++) { - if (i == maxSSEIndex || i + 1 == maxSSEIndex) { - continue; - } - if (sse.get(i) + sse.get(i + 1) < minSSE) { - minSSE = sse.get(i) + sse.get(i + 1); - minSSEIndex = i; - } - } - if (minSSEIndex < 0) { - if (debug) { - System.out.println(c); - System.out.println(minSSEIndex); - System.out.println("break min"); - } - break; - } - - // Split - int startIdx = offset.get(maxSSEIndex); - int endIdx = offset.get(maxSSEIndex + 1); - if (debug) { - System.out.println("+++To split bucket: " + startIdx + "," + endIdx + ":" + maxSSE); - } - int middleIdx = (startIdx + endIdx) / 2; - offset.add(maxSSEIndex + 1, middleIdx); - - // Update SSE affected by split - sse.set( - maxSSEIndex, - calculateSSEForBucket( - points, offset.get(maxSSEIndex) - 1, offset.get(maxSSEIndex + 1) + 1)); - - double newSse = - calculateSSEForBucket( - points, offset.get(maxSSEIndex + 1) - 1, offset.get(maxSSEIndex + 2) + 1); - - sse.add(maxSSEIndex + 1, newSse); - - // Merge - if (minSSEIndex > maxSSEIndex) { - minSSEIndex += 1; // Adjust index - } - offset.remove(minSSEIndex + 1); - - if (debug) { - System.out.println("---To merge bucket: " + offset.get(minSSEIndex) + ":" + minSSE); - } - - sse.set( - minSSEIndex, - calculateSSEForBucket( - points, offset.get(minSSEIndex) - 1, offset.get(minSSEIndex + 1) + 1)); - - sse.remove(minSSEIndex + 1); - } - - // Convert ArrayList to int[] and return - if (debug) { - System.out.println(offset); - } - return offset; - } - - public static List<Point> LTTB(List<Point> points, List<Integer> bins) { - List<Point> res = new ArrayList<>(); - res.add(points.get(0)); - - for (int i = 0; i < bins.size() - 1; i++) { - Point leftAnchor = res.get(res.size() - 1); - Point rightFloater; - if (i == bins.size() - 2) { - rightFloater = points.get(points.size() - 1); - } else { - rightFloater = calculateAveragePoint(points, bins.get(i + 1), bins.get(i + 2)); - } - int bestIdx = -1; - double maxArea = -Double.MAX_VALUE; - for (int j = bins.get(i); j < bins.get(i + 1); j++) { - double area = Tool.triArea(points.get(j), leftAnchor, rightFloater); - if (area > maxArea) { - maxArea = area; - bestIdx = j; - } - } - if (bestIdx > 0) { - res.add(points.get(bestIdx)); - } - } - res.add(points.get(points.size() - 1)); - return res; - } - - public static List<Point> LTD(List<Point> points, int m, int maxIter, boolean debug) { - List<Integer> bins = getLtdBinIdxs(points, m, maxIter, debug); - return LTTB(points, bins); - } - - public static void main(String[] args) { - Random rand = new Random(10); - String input = "D:\\datasets\\regular\\tmp2.csv"; - boolean hasHeader = true; - int timeIdx = 0; - int valueIdx = 1; - int N = 100_0000; - // List<Point> points = Tool.readFromFile(input, hasHeader, timeIdx, valueIdx, N); - Polyline polyline = new Polyline(); - for (int i = 0; i < N; i += 1) { - double v = rand.nextInt(1000); - polyline.addVertex(new Point(i, v)); - } - List<Point> points = polyline.getVertices(); - try (FileWriter writer = new FileWriter("raw.csv")) { - // 写入CSV头部 - writer.append("x,y,z\n"); - - // 写入每个点的数据 - for (Point point : points) { - writer.append(point.x + "," + point.y + "," + point.z + "\n"); - } - System.out.println(points.size() + " Data has been written"); - } catch (IOException e) { - System.out.println("Error writing to CSV file: " + e.getMessage()); - } - - int m = 1000; - int maxIter = -1; - long startTime = System.currentTimeMillis(); - // List<Integer> bins = getLtdBinIdxs(points, m, true); - List<Point> sampled = LTD(points, m, maxIter, false); - long endTime = System.currentTimeMillis(); - System.out.println("Time taken: " + (endTime - startTime) + "ms"); - - for (Point p : sampled) { - System.out.println(p); - } - - try (PrintWriter writer = new PrintWriter(new File("output.csv"))) { - // 写入字符串 - for (int i = 0; i < sampled.size(); i++) { - writer.println(sampled.get(i).x + "," + sampled.get(i).y); - } - - } catch (FileNotFoundException e) { - e.printStackTrace(); - } - } -} diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Rdp.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Rdp.java index 7111624e9f9..7add7ab57cc 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Rdp.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Rdp.java @@ -48,7 +48,7 @@ public class Rdp { keep[0] = true; keep[points.size() - 1] = true; - int count = 0; // TODO debug + int count = 0; while (!stack.isEmpty()) { int[] range = stack.pop(); diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB.java index 5c29355fec1..871efecad78 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB.java @@ -147,7 +147,7 @@ public class SWAB { } // 设置三角形的前后关系 - for (int i = 0; i < nTriangles; i++) { // TODO 这个可以和上一个循环合并吗？？好像不可以 + 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]); } @@ -155,10 +155,10 @@ public class SWAB { // 使用优先队列构建 minHeap PriorityQueue<Triangle> triangleHeap = new PriorityQueue<>(Comparator.comparingDouble(t -> t.area)); - Collections.addAll(triangleHeap, triangles); // complexity TODO O(n) or O(nlogn)? + Collections.addAll(triangleHeap, triangles); int fakeCnt = 0; - while (!triangleHeap.isEmpty() && triangleHeap.peek().area < maxError) { // TODO + while (!triangleHeap.isEmpty() && triangleHeap.peek().area < maxError) { // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作 // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小 Triangle tri = triangleHeap.poll(); // O(logn) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB_AD.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB_AD.java index 3fed7cc4ef0..0cc9a227314 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB_AD.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/SWAB_AD.java @@ -43,10 +43,10 @@ public class SWAB_AD { // 使用优先队列构建 minHeap PriorityQueue<Triangle> triangleHeap = new PriorityQueue<>(Comparator.comparingDouble(t -> t.area)); - Collections.addAll(triangleHeap, triangles); // complexity TODO O(n) or O(nlogn) + Collections.addAll(triangleHeap, triangles); int fakeCnt = 0; - while (!triangleHeap.isEmpty() && triangleHeap.peek().area < maxError) { // TODO + while (!triangleHeap.isEmpty() && triangleHeap.peek().area < maxError) { // 注意peek只需要直接访问该位置的元素，不涉及任何重排或堆化操作 // 而poll是删除堆顶元素，需要重新堆化以维护堆的性质，复杂度是O(logk),k是当前堆的大小 Triangle tri = triangleHeap.poll(); // O(logn) diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tmp.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tmp.java deleted file mode 100644 index 270aca1dee7..00000000000 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/Tmp.java +++ /dev/null @@ -1,44 +0,0 @@ -package org.apache.iotdb.db.query.eBUG; - -import java.io.File; -import java.io.FileNotFoundException; -import java.io.PrintWriter; -import java.util.Comparator; -import java.util.PriorityQueue; -import java.util.Random; - -public class Tmp { - // 用于debug为什么n>2kw的耗时增大明显 - public static void main(String[] args) { - int seed = 10; - Random rand = new Random(seed); - int eParam = 1; - try (PrintWriter writer = new PrintWriter(new File("tmp.csv"))) { - for (int n = 100_0000; - n < 100000_0000; - n += 5000_0000) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度 - // for (int n = 19000000; n < 3000_0000; n +=200_0000) { - PriorityQueue<Point> heap = new PriorityQueue<>(Comparator.comparingDouble(t -> t.y)); - for (int i = 0; i < n; i++) { - double v = rand.nextInt(1000000); - heap.add(new Point(i, v)); - } - - long startTime = System.currentTimeMillis(); - long sum = 0; - while (!heap.isEmpty()) { - Point p = heap.poll(); - sum += p.x; - } - long endTime = System.currentTimeMillis(); - System.out.println(n + ", Time taken to reduce points: " + (endTime - startTime) + "ms"); - writer.println(n + "," + "0" + "," + (endTime - startTime)); - System.out.println(sum); - } - } catch (FileNotFoundException e) { - throw new RuntimeException(e); - } - - System.out.println("finish"); - } -} 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 86d9abaccde..cb67d53a086 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 @@ -123,7 +123,7 @@ public class eBUG { } // 设置三角形的前后关系 - for (int i = 0; i < nTriangles; i++) { // TODO 这个可以和上一个循环合并吗？？好像不可以 + 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]); } @@ -131,7 +131,7 @@ public class eBUG { // 使用优先队列构建 minHeap PriorityQueue<Triangle> triangleHeap = new PriorityQueue<>(Comparator.comparingDouble(t -> t.area)); - Collections.addAll(triangleHeap, triangles); // complexity TODO O(n) or O(nlogn)? + Collections.addAll(triangleHeap, triangles); double previousEA = -1; // while (!triangleHeap.isEmpty()) { // TODO 注意triangleHeap里装的是non-terminal point对应的三角形 @@ -374,7 +374,7 @@ public class eBUG { int[] eParamList = {100_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) { // 超过两千万就都变得慢多了，感觉可能是内存有限的原因，而不是算法复杂度 + for (int n = 100_0000; n < 2000_0000; n += 200_0000) { // TODO 注意 要有一个点是n=300w Polyline polyline = new Polyline();
