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 65d259e51114a60ec20cda67423df30c41b18de5 Author: Lei Rui <[email protected]> AuthorDate: Wed Jan 22 14:48:53 2025 +0800 array --- .../java/org/apache/iotdb/db/query/eBUG/eBUG.java | 57 ++++++++------- ...d.java => eBUG_sortedEliminatedDeprecated.java} | 60 +++++++-------- ...va => eBUG_sortedEliminatedDeprecated_tmp.java} | 85 +++++++++++----------- .../org/apache/iotdb/db/query/eBUG/eBUG_tmp.java | 83 +++++++++++---------- 4 files changed, 143 insertions(+), 142 deletions(-) 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 1596f32a726..d4a8ebfc36f 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,7 +19,9 @@ package org.apache.iotdb.db.query.eBUG; -import java.io.*; +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; @@ -27,9 +29,12 @@ import static org.apache.iotdb.db.query.eBUG.Tool.triArea; public class eBUG { - public static List<Point> findEliminated(Polyline lineToSimplify, TimestampPriorityQueue recentEliminatedOrdered, + public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 + // 从最近淘汰的e个点里寻找位于pa~pb之间的：e + // 把上一步找到的点和pa pi pb一起按照时间戳递增排序：记c=b-a。如果e<c，那么eloge，否则c + // 后面鞋带公式计算面积：min(e+3,c) // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ // pi: the point whose significance needs updating // pa: left adjacent non-eliminated point of pi @@ -51,7 +56,7 @@ public class eBUG { // return res; // pa pi pb已经按照时间戳递增 // } - if (recentEliminatedOrdered.size() >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region + 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; // 已经按照时间戳递增 @@ -60,26 +65,23 @@ public class eBUG { // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 // System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); + res.add(pi); + res.add(pb); // 包括了c>e=0的情况 - boolean addPi = false; - for (Point p : recentEliminatedOrdered.getQueue()) { // 已经按时间戳递增排序，为了后面计算total areal displacement需要 - if (p.x <= pa.x) { - continue; - } - if (p.x >= pb.x) { + for (int idx : recentEliminated) { // e points + if (idx == 0) { // init, not filled by real eliminated points yet break; } - if (p.x > pi.x && !addPi) { - res.add(pi); - addPi = true; + Point p = lineToSimplify.get(idx); + if (p.x > pa.x && p.x < pb.x) { + res.add(p); } - res.add(p); - } - if (!addPi) { // may happen when no eliminated points found above - res.add(pi); } - res.add(pb); + + // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 + res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 TODO 这样的话时间复杂度要变成e*log(e)了吧？ + return res; } @@ -92,9 +94,8 @@ public class eBUG { // results.addAll(lineToSimplify.getVertices()); // TODO debug // TODO 需要一个东西来记录最近淘汰的点依次是谁 -// int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated -// int recentEliminatedIdx = 0; // index in the array, circulate - TimestampPriorityQueue recentEliminatedOrdered = new TimestampPriorityQueue(e); + 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) { @@ -142,12 +143,11 @@ public class eBUG { 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 - recentEliminatedOrdered.insert(lineToSimplify.get(tri.indices[1])); + recentEliminated[recentEliminatedIdx] = tri.indices[1]; + recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate } if (debug) { - System.out.println("the e most recently eliminated points:" + recentEliminatedOrdered); + System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） @@ -176,7 +176,7 @@ public class eBUG { tri.prev.indices[2] = tri.indices[2]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, tri.prev.indices[0], tri.prev.indices[1], tri.prev.indices[2]); // TODO complexity ? @@ -225,7 +225,7 @@ public class eBUG { tri.next.indices[0] = tri.indices[0]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, tri.next.indices[0], tri.next.indices[1], tri.next.indices[2]); // TODO complexity @@ -298,8 +298,9 @@ public class eBUG { // List<Point> results = new ArrayList<>(); // 计算运行时间 // 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}; + try (PrintWriter writer = new PrintWriter(new File("exp.csv"))) { + 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.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_sortedEliminatedDeprecated.java similarity index 91% rename from server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old.java rename to server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_sortedEliminatedDeprecated.java index 180f277c44e..61c508added 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_sortedEliminatedDeprecated.java @@ -19,22 +19,17 @@ package org.apache.iotdb.db.query.eBUG; -import java.io.File; -import java.io.FileNotFoundException; -import java.io.PrintWriter; +import java.io.*; 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_old { - public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, +public class eBUG_sortedEliminatedDeprecated { + public static List<Point> findEliminated(Polyline lineToSimplify, TimestampPriorityQueue recentEliminatedOrdered, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 - // 从最近淘汰的e个点里寻找位于pa~pb之间的：e - // 把上一步找到的点和pa pi pb一起按照时间戳递增排序：记c=b-a。如果e<c，那么eloge，否则c - // 后面鞋带公式计算面积：min(e+3,c) // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ // pi: the point whose significance needs updating // pa: left adjacent non-eliminated point of pi @@ -56,7 +51,7 @@ public class eBUG_old { // return res; // pa pi pb已经按照时间戳递增 // } - if (recentEliminated.length >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region + if (recentEliminatedOrdered.size() >= (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; // 已经按照时间戳递增 @@ -65,23 +60,26 @@ public class eBUG_old { // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 // System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); - 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 + boolean addPi = false; + for (Point p : recentEliminatedOrdered.getQueue()) { // 已经按时间戳递增排序，为了后面计算total areal displacement需要 + if (p.x <= pa.x) { + continue; + } + if (p.x >= pb.x) { break; } - Point p = lineToSimplify.get(idx); - if (p.x > pa.x && p.x < pb.x) { - res.add(p); + if (p.x > pi.x && !addPi) { + res.add(pi); + addPi = true; } + res.add(p); } - - // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 - res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 TODO 这样的话时间复杂度要变成e*log(e)了吧？ - + if (!addPi) { // may happen when no eliminated points found above + res.add(pi); + } + res.add(pb); return res; } @@ -94,8 +92,9 @@ public class eBUG_old { // results.addAll(lineToSimplify.getVertices()); // TODO debug // TODO 需要一个东西来记录最近淘汰的点依次是谁 - 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 + TimestampPriorityQueue recentEliminatedOrdered = new TimestampPriorityQueue(e); int total = lineToSimplify.size(); if (total < 3) { @@ -143,11 +142,12 @@ public class eBUG_old { 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 +// recentEliminated[recentEliminatedIdx] = tri.indices[1]; +// recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate + recentEliminatedOrdered.insert(lineToSimplify.get(tri.indices[1])); } if (debug) { - System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); + System.out.println("the e most recently eliminated points:" + recentEliminatedOrdered); } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） @@ -176,7 +176,7 @@ public class eBUG_old { tri.prev.indices[2] = tri.indices[2]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, tri.prev.indices[0], tri.prev.indices[1], tri.prev.indices[2]); // TODO complexity ? @@ -225,7 +225,7 @@ public class eBUG_old { tri.next.indices[0] = tri.indices[0]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, tri.next.indices[0], tri.next.indices[1], tri.next.indices[2]); // TODO complexity @@ -298,9 +298,9 @@ public class eBUG_old { // List<Point> results = new ArrayList<>(); // 计算运行时间 // int eParam = 10; - try (PrintWriter writer = new PrintWriter(new File("exp.csv"))) { - 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}; + try (PrintWriter writer = new PrintWriter(new File("exp2.csv"))) { + int[] eParamList = {0, 1, 100, 500, 1000, 5000, 10000, 50000, 10_0000, 50_0000, 60_0000, 70_0000, + 80_0000, 90_0000, 100_0000, 150_0000, 200_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_sortedEliminatedDeprecated_tmp.java similarity index 88% rename from server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_old_tmp.java rename to server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_sortedEliminatedDeprecated_tmp.java index 5cfafb59110..4d933cfcd2e 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_sortedEliminatedDeprecated_tmp.java @@ -27,13 +27,10 @@ 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_old_tmp { - public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, +public class eBUG_sortedEliminatedDeprecated_tmp { + public static List<Point> findEliminated(Polyline lineToSimplify, TimestampPriorityQueue recentEliminatedOrdered, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 - // 从最近淘汰的e个点里寻找位于pa~pb之间的：e - // 把上一步找到的点和pa pi pb一起按照时间戳递增排序：记c=b-a。如果e<c，那么eloge，否则c - // 后面鞋带公式计算面积：min(e+3,c) // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ // pi: the point whose significance needs updating // pa: left adjacent non-eliminated point of pi @@ -55,7 +52,7 @@ public class eBUG_old_tmp { // return res; // pa pi pb已经按照时间戳递增 // } - if (recentEliminated.length >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region + if (recentEliminatedOrdered.size() >= (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; // 已经按照时间戳递增 @@ -64,23 +61,26 @@ public class eBUG_old_tmp { // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 // System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); - 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 + boolean addPi = false; + for (Point p : recentEliminatedOrdered.getQueue()) { // 已经按时间戳递增排序，为了后面计算total areal displacement需要 + if (p.x <= pa.x) { + continue; + } + if (p.x >= pb.x) { break; } - Point p = lineToSimplify.get(idx); - if (p.x > pa.x && p.x < pb.x) { - res.add(p); + if (p.x > pi.x && !addPi) { + res.add(pi); + addPi = true; } + res.add(p); } - - // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 - res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 TODO 这样的话时间复杂度要变成e*log(e)了吧？ - + if (!addPi) { // may happen when no eliminated points found above + res.add(pi); + } + res.add(pb); return res; } @@ -93,8 +93,9 @@ public class eBUG_old_tmp { // results.addAll(lineToSimplify.getVertices()); // TODO debug // TODO 需要一个东西来记录最近淘汰的点依次是谁 - 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 + TimestampPriorityQueue recentEliminatedOrdered = new TimestampPriorityQueue(e); int total = lineToSimplify.size(); if (total < 3) { @@ -142,11 +143,12 @@ public class eBUG_old_tmp { 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 +// recentEliminated[recentEliminatedIdx] = tri.indices[1]; +// recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate + recentEliminatedOrdered.insert(lineToSimplify.get(tri.indices[1])); } if (debug) { - System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); + System.out.println("the e most recently eliminated points:" + recentEliminatedOrdered); } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） @@ -175,7 +177,7 @@ public class eBUG_old_tmp { tri.prev.indices[2] = tri.indices[2]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, tri.prev.indices[0], tri.prev.indices[1], tri.prev.indices[2]); // TODO complexity ? @@ -224,7 +226,7 @@ public class eBUG_old_tmp { tri.next.indices[0] = tri.indices[0]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, tri.next.indices[0], tri.next.indices[1], tri.next.indices[2]); // TODO complexity @@ -264,6 +266,7 @@ public class eBUG_old_tmp { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); +// int n = 1000_0000; int n = 10000; int p = 10; @@ -279,31 +282,29 @@ public class eBUG_old_tmp { 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; -// for (int eParam = 0; eParam < 2 * n; eParam += 1000) { - int eParam = 22; + int eParam = 0; 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("Time taken to reduce points: " + (endTime - startTime) + "ms"); System.out.println(results.size()); if (results.size() <= 100) { @@ -314,7 +315,7 @@ public class eBUG_old_tmp { } } - try (FileWriter writer = new FileWriter("fast2.csv")) { + try (FileWriter writer = new FileWriter("fast.csv")) { // 写入CSV头部 writer.append("x,y,z\n"); diff --git a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_tmp.java b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_tmp.java index a04c4c17920..93267df65a7 100644 --- a/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_tmp.java +++ b/server/src/main/java/org/apache/iotdb/db/query/eBUG/eBUG_tmp.java @@ -28,9 +28,12 @@ import static org.apache.iotdb.db.query.eBUG.Tool.triArea; public class eBUG_tmp { - public static List<Point> findEliminated(Polyline lineToSimplify, TimestampPriorityQueue recentEliminatedOrdered, + public static List<Point> findEliminated(Polyline lineToSimplify, int[] recentEliminated, int pa_idx, int pi_idx, int pb_idx) { // TODO 复杂度分析 + // 从最近淘汰的e个点里寻找位于pa~pb之间的：e + // 把上一步找到的点和pa pi pb一起按照时间戳递增排序：记c=b-a。如果e<c，那么eloge，否则c + // 后面鞋带公式计算面积：min(e+3,c) // 性质：最近淘汰的那一个点一定是位于pa~pb之间，因为正是这个点的淘汰才使得pi的significance要更新！ // pi: the point whose significance needs updating // pa: left adjacent non-eliminated point of pi @@ -52,7 +55,7 @@ public class eBUG_tmp { // return res; // pa pi pb已经按照时间戳递增 // } - if (recentEliminatedOrdered.size() >= (pb_idx - pa_idx - 2)) { // e >= the total number of eliminated points in this region + 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; // 已经按照时间戳递增 @@ -61,26 +64,23 @@ public class eBUG_tmp { // 从最近淘汰的e个点里寻找位于pa~pb之间的点，找到的有可能小于e个点 // System.out.println("k>=[c=(b-a-2)]>e, search among e"); res.add(pa); + res.add(pi); + res.add(pb); // 包括了c>e=0的情况 - boolean addPi = false; - for (Point p : recentEliminatedOrdered.getQueue()) { // 已经按时间戳递增排序，为了后面计算total areal displacement需要 - if (p.x <= pa.x) { - continue; - } - if (p.x >= pb.x) { + for (int idx : recentEliminated) { // e points + if (idx == 0) { // init, not filled by real eliminated points yet break; } - if (p.x > pi.x && !addPi) { - res.add(pi); - addPi = true; + Point p = lineToSimplify.get(idx); + if (p.x > pa.x && p.x < pb.x) { + res.add(p); } - res.add(p); - } - if (!addPi) { // may happen when no eliminated points found above - res.add(pi); } - res.add(pb); + + // 按照时间戳递增排序，这是为了后面计算total areal displacement需要 + res.sort(Comparator.comparingDouble(p -> p.x)); // 按时间戳排序 TODO 这样的话时间复杂度要变成e*log(e)了吧？ + return res; } @@ -93,9 +93,8 @@ public class eBUG_tmp { // results.addAll(lineToSimplify.getVertices()); // TODO debug // TODO 需要一个东西来记录最近淘汰的点依次是谁 -// int[] recentEliminated = new int[e]; // init 0 points to the first point, skipped in findEliminated -// int recentEliminatedIdx = 0; // index in the array, circulate - TimestampPriorityQueue recentEliminatedOrdered = new TimestampPriorityQueue(e); + 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) { @@ -143,12 +142,11 @@ public class eBUG_tmp { 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 - recentEliminatedOrdered.insert(lineToSimplify.get(tri.indices[1])); + recentEliminated[recentEliminatedIdx] = tri.indices[1]; + recentEliminatedIdx = (recentEliminatedIdx + 1) % e; // 0~e-1 circulate } if (debug) { - System.out.println("the e most recently eliminated points:" + recentEliminatedOrdered); + System.out.println("the e most recently eliminated points:" + Arrays.toString(recentEliminated)); } // 更新当前点的重要性（z 轴存储effective area,这是一个单调增的指标） @@ -177,7 +175,7 @@ public class eBUG_tmp { tri.prev.indices[2] = tri.indices[2]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, tri.prev.indices[0], tri.prev.indices[1], tri.prev.indices[2]); // TODO complexity ? @@ -226,7 +224,7 @@ public class eBUG_tmp { tri.next.indices[0] = tri.indices[0]; // e parameter - List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminatedOrdered, + List<Point> pointsForSig = findEliminated(lineToSimplify, recentEliminated, tri.next.indices[0], tri.next.indices[1], tri.next.indices[2]); // TODO complexity @@ -266,7 +264,6 @@ public class eBUG_tmp { Polyline polyline = new Polyline(); List<Polyline> polylineList = new ArrayList<>(); Random rand = new Random(1); -// int n = 1000_0000; int n = 10000; int p = 10; @@ -282,29 +279,31 @@ public class eBUG_tmp { 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 = 0; +// int eParam = 10; +// for (int eParam = 0; eParam < 2 * n; eParam += 1000) { + int eParam = 22; long startTime = System.currentTimeMillis(); List<Point> results = buildEffectiveArea(polyline, eParam, false); // 输出结果 long endTime = System.currentTimeMillis(); - System.out.println("Time taken to reduce points: " + (endTime - startTime) + "ms"); + System.out.println("n=" + n + ", e=" + eParam + ", Time taken to reduce points: " + (endTime - startTime) + "ms"); System.out.println(results.size()); if (results.size() <= 100) { @@ -315,7 +314,7 @@ public class eBUG_tmp { } } - try (FileWriter writer = new FileWriter("fast.csv")) { + try (FileWriter writer = new FileWriter("fast2.csv")) { // 写入CSV头部 writer.append("x,y,z\n");
