This is an automated email from the ASF dual-hosted git repository. leirui pushed a commit to branch research/M4-visualization in repository https://gitbox.apache.org/repos/asf/iotdb.git
commit 19cc917b5b8627b20ad98c4eefb786cafdc68985 Author: Lei Rui <[email protected]> AuthorDate: Mon Jul 3 23:44:12 2023 +0800 add test --- .../iotdb/tsfile/read/common/IOMonitor2.java | 16 ++ .../iotdb/tsfile/encoding/SDTEncoderTest.java | 254 +++++++++++++++------ 2 files changed, 199 insertions(+), 71 deletions(-) diff --git a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java index 62e79e40fac..cd39d9af1e0 100644 --- a/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java +++ b/tsfile/src/main/java/org/apache/iotdb/tsfile/read/common/IOMonitor2.java @@ -247,6 +247,22 @@ public class IOMonitor2 { M4_LSM_TP_SEARCH_ARRAY_c_genBPTP_cnt = 0; } + public static class ValuePoint implements Comparable<ValuePoint> { + public final int index; + public final long value; + + public ValuePoint(int index, long value) { + this.index = index; + this.value = value; + } + + @Override + public int compareTo(ValuePoint other) { + // multiplied to -1 as the author need descending sort order + return -1 * Long.valueOf(this.value).compareTo(other.value); + } + } + public static void addMeasure(Operation operation, long elapsedTimeInNanosecond) { switch (operation) { case DCP_Server_Query_Execute: diff --git a/tsfile/src/test/java/org/apache/iotdb/tsfile/encoding/SDTEncoderTest.java b/tsfile/src/test/java/org/apache/iotdb/tsfile/encoding/SDTEncoderTest.java index 9f62a16a794..c33ee296425 100644 --- a/tsfile/src/test/java/org/apache/iotdb/tsfile/encoding/SDTEncoderTest.java +++ b/tsfile/src/test/java/org/apache/iotdb/tsfile/encoding/SDTEncoderTest.java @@ -19,15 +19,18 @@ package org.apache.iotdb.tsfile.encoding; -import static org.junit.Assert.assertEquals; +import org.apache.iotdb.tsfile.encoding.encoder.SDTEncoder; +import org.apache.iotdb.tsfile.read.common.IOMonitor2.ValuePoint; + +import org.junit.Test; import java.io.BufferedReader; import java.io.FileReader; import java.util.ArrayList; -import java.util.Collections; +import java.util.Comparator; import java.util.List; -import org.apache.iotdb.tsfile.encoding.encoder.SDTEncoder; -import org.junit.Test; + +import static org.junit.Assert.assertEquals; public class SDTEncoderTest { @@ -69,10 +72,10 @@ public class SDTEncoderTest { public void mytest1() throws Exception { String csvData = "D:\\full-game\\BallSpeed.csv"; int start = 200000; - int range = 200; + int range = 100000; int end = start + range; SDTEncoder encoder = new SDTEncoder(); - double e = 80000.0 / 2; // std/2 + double e = 100000; // std/2 encoder.setCompDeviation(e / 2); long count = 0; String line; @@ -86,8 +89,7 @@ public class SDTEncoderTest { count++; if (count >= start && count < end) { idx++; -// long time = Long.parseLong(line.split(",")[0]); - long time = idx; + long time = idx; // not real timestamp, but relative position id long value = Long.parseLong(line.split(",")[1]); timestampList.add(time); valueList.add(value); @@ -112,59 +114,128 @@ public class SDTEncoderTest { System.out.println("at=" + selectTimestamps + ";"); System.out.println("av=" + selectValues + ";"); - System.out.println("LB=av-e;\n" + "UB=av+e;\n" + "plot(t,v)\n" + "hold on,plot(t,v,'+')\n" - + "hold on,plot(at,av,'r')\n" + "%hold on,plot(at,av,'r+')\n" + "hold on,plot(at,UB,'g')\n" - + "%hold on,plot(at,UB,'g+')\n" + "hold on,plot(at,LB,'g')\n" - + "%hold on,plot(at,LB,'g+')\n" + "\n" + "% [val,idx]=max(av-e)\n" + "% yline(val)\n" + "\n" - + "[sortedX, sortedInds] = sort(LB,'descend');\n" + "% yline(sortedX(1))\n" - + "% yline(sortedX(2))\n" + "\n" + "% 依次计算UB小于Nth-max-LB的点数\n" - + "% case 1: 两端都小于threshold，则该段内的点的UB都小于threshold，都可以被剪枝\n" - + "% case 2: 两端都大于等于threshold，则该段内的点的UB都大于等于threshold，则都不可以被剪枝\n" - + "% case 3: 一端小于一端大于等于threshold，则该段内有部分点的UB小于threshold可以被剪枝\n" - + "% (t1,v1), (t2,v2), t1<t2\n" + "% y=(t-t1)*(v2-v1)/(t2-t1)+v1\n" - + "% y<thresold ===> (t-t1)*(v2-v1)/(t2-t1)+v1<threshold\n" - + "% 如果v2>=threshold>v1: 则t<(threshold-v1)*(t2-t1)/(v2-v1)+t1，于是[t1,(threshold-v1)*(t2-t1)/(v2-v1)+t1)内的点可剪枝\n" - + "% 如果v2<threshold<=v1: 则t>(threshold-v1)*(t2-t1)/(v2-v1)+t1，于是((threshold-v1)*(t2-t1)/(v2-v1)+t1,t2]内的点可剪枝\n" - + "rank=1\n" + "threshold=sortedX(rank)\n" + "hold on, yline(threshold);\n" - + "hold on, plot(at(sortedInds(rank)),threshold,'o')\n" + "\n" + "prune_t=[]; % point\n" - + "prune_v=[]; % point\n" + "prune_interval=[]; % interval\n" + "interval_start=-1;\n" - + "for i=2:1:length(av)\n" + "\tt1=at(i-1);\n" + "\tt2=at(i);\n" + "\tv1=UB(i-1);\n" - + "\tv2=UB(i);\n" + "\ta=[];\n" + "\tif v1<threshold && v2<threshold\n" - + "\t\tif i<length(av)\n" + "\t\t\ta=t1:1:t2-1;\n" + "\t\telse \n" + "\t\t\ta=t1:1:t2;\n" - + "\t\tend\n" + "\t\tif interval_start<0\n" + "\t\t\tinterval_start=t1;\n" + " end\n" - + " interval_end=t2; % continuous\n" + "\telseif v1<threshold && v2>=threshold\n" - + "\t\ta=t1:1:floor((threshold-v1)*(t2-t1)/(v2-v1)+t1); % no need -1 here\n" - + "\t\tif interval_start<0\n" + "\t\t\tinterval_start=t1;\n" + " end\n" - + " prune_interval=[prune_interval;[interval_start,floor((threshold-v1)*(t2-t1)/(v2-v1)+t1)]];\n" - + "\t\tinterval_start=-1; % discontinuous\n" + "\telseif v1>=threshold && v2<threshold\n" - + "\t\tif i<length(av)\n" + "\t\t\ta=ceil((threshold-v1)*(t2-t1)/(v2-v1)+t1):1:t2-1;\n" - + "\t\telse\n" + "\t\t\ta=ceil((threshold-v1)*(t2-t1)/(v2-v1)+t1):1:t2;\n" + "\t\tend\n" - + "\t\tinterval_start=ceil((threshold-v1)*(t2-t1)/(v2-v1)+t1);\n" + "\t\tinterval_end=t2;\n" - + "\tend\n" + "\tprune_t=[prune_t,a];\n" - + "\tprune_v=[prune_v,(a-t1)*(v2-v1)/(t2-t1)+v1];\n" + "end\n" + "if interval_start>0\n" - + "\tprune_interval=[prune_interval;[interval_start,interval_end]];\n" + "end\n" + "\n" - + "hold on,plot(prune_t,prune_v,'b.')\n" + "disp(length(prune_t)/length(t))\n" + "\n" - + "%rectangle('Position', [at(1) av(1) at(2) av(2)], 'Facec',[0.5 1 0.5])\n" - + "prune_interval\n" + "\n" + "%for i=1:1:length(prune_interval)\n" - + "%\txline(prune_interval(i,1));\n" + "%\txline(prune_interval(i,2));\n" + "%end\n" + "\n" - + "% https://se.mathworks.com/help/matlab/ref/xregion.html\n"; + "% xregion\n" + "\n" - + "for i=1:1:length(prune_interval)\n" + "\tx=prune_interval(i,1):1:prune_interval(i,2);\n" - + "\ty=[];\n" + "\tfor j=1:1:length(x)\n" + "\t\tidx=x(j);\n" + "\t\tfor n=2:1:length(at)\n" - + "\t\t\tif idx<=at(n)\n" + "\t\t\t\tt1=at(n-1);\n" + "\t\t\t\tt2=at(n);\n" - + "\t\t\t\tv1=av(n-1);\n" + "\t\t\t\tv2=av(n);\n" - + "\t\t\t\ty=[y,(idx-t1)*(v2-v1)/(t2-t1)+v1];\n" + "\t\t\t\tbreak;\n" + "\t\t\tend\n" - + "\t\tend\n" + "\tend\n" + "\ty1=y-e;\n" + "\ty2=y+e;\n" + "\tL1=[x,fliplr(x)];\n" - + "\tL2=[y1,fliplr(y2)];\n" + "\tfill(L1,L2,'b','FaceAlpha',0.1);\n" + "end"); + System.out.println( + "LB=av-e;\n" + + "UB=av+e;\n" + + "plot(t,v)\n" + + "hold on,plot(t,v,'+')\n" + + "hold on,plot(at,av,'r')\n" + + "%hold on,plot(at,av,'r+')\n" + + "hold on,plot(at,UB,'g')\n" + + "%hold on,plot(at,UB,'g+')\n" + + "hold on,plot(at,LB,'g')\n" + + "%hold on,plot(at,LB,'g+')\n" + + "\n" + + "% [val,idx]=max(av-e)\n" + + "% yline(val)\n" + + "\n" + + "[sortedX, sortedInds] = sort(LB,'descend');\n" + + "% yline(sortedX(1))\n" + + "% yline(sortedX(2))\n" + + "\n" + + "% 依次计算UB小于Nth-max-LB的点数\n" + + "% case 1: 两端都小于threshold，则该段内的点的UB都小于threshold，都可以被剪枝\n" + + "% case 2: 两端都大于等于threshold，则该段内的点的UB都大于等于threshold，则都不可以被剪枝\n" + + "% case 3: 一端小于一端大于等于threshold，则该段内有部分点的UB小于threshold可以被剪枝\n" + + "% (t1,v1), (t2,v2), t1<t2\n" + + "% y=(t-t1)*(v2-v1)/(t2-t1)+v1\n" + + "% y<thresold ===> (t-t1)*(v2-v1)/(t2-t1)+v1<threshold\n" + + "% 如果v2>=threshold>v1: 则t<(threshold-v1)*(t2-t1)/(v2-v1)+t1，于是[t1,(threshold-v1)*(t2-t1)/(v2-v1)+t1)内的点可剪枝\n" + + "% 如果v2<threshold<=v1: 则t>(threshold-v1)*(t2-t1)/(v2-v1)+t1，于是((threshold-v1)*(t2-t1)/(v2-v1)+t1,t2]内的点可剪枝\n" + + "rank=1\n" + + "threshold=sortedX(rank)\n" + + "hold on, yline(threshold);\n" + + "hold on, plot(at(sortedInds(rank)),threshold,'o')\n" + + "\n" + + "prune_t=[]; % point\n" + + "prune_v=[]; % point\n" + + "prune_interval=[]; % interval\n" + + "interval_start=-1;\n" + + "for i=2:1:length(av)\n" + + "\tt1=at(i-1);\n" + + "\tt2=at(i);\n" + + "\tv1=UB(i-1);\n" + + "\tv2=UB(i);\n" + + "\ta=[];\n" + + "\tif v1<threshold && v2<threshold\n" + + "\t\tif i<length(av)\n" + + "\t\t\ta=t1:1:t2-1;\n" + + "\t\telse \n" + + "\t\t\ta=t1:1:t2;\n" + + "\t\tend\n" + + "\t\tif interval_start<0\n" + + "\t\t\tinterval_start=t1;\n" + + " end\n" + + " interval_end=t2; % continuous\n" + + "\telseif v1<threshold && v2>=threshold\n" + + "\t\ta=t1:1:floor((threshold-v1)*(t2-t1)/(v2-v1)+t1); % no need -1 here\n" + + "\t\tif interval_start<0\n" + + "\t\t\tinterval_start=t1;\n" + + " end\n" + + " prune_interval=[prune_interval;[interval_start,floor((threshold-v1)*(t2-t1)/(v2-v1)+t1)]];\n" + + "\t\tinterval_start=-1; % discontinuous\n" + + "\telseif v1>=threshold && v2<threshold\n" + + "\t\tif i<length(av)\n" + + "\t\t\ta=ceil((threshold-v1)*(t2-t1)/(v2-v1)+t1):1:t2-1;\n" + + "\t\telse\n" + + "\t\t\ta=ceil((threshold-v1)*(t2-t1)/(v2-v1)+t1):1:t2;\n" + + "\t\tend\n" + + "\t\tinterval_start=ceil((threshold-v1)*(t2-t1)/(v2-v1)+t1);\n" + + "\t\tinterval_end=t2;\n" + + "\tend\n" + + "\tprune_t=[prune_t,a];\n" + + "\tprune_v=[prune_v,(a-t1)*(v2-v1)/(t2-t1)+v1];\n" + + "end\n" + + "if interval_start>0\n" + + "\tprune_interval=[prune_interval;[interval_start,interval_end]];\n" + + "end\n" + + "\n" + + "hold on,plot(prune_t,prune_v,'b.')\n" + + "disp(length(prune_t)/length(t))\n" + + "\n" + + "%rectangle('Position', [at(1) av(1) at(2) av(2)], 'Facec',[0.5 1 0.5])\n" + + "prune_interval\n" + + "\n" + + "%for i=1:1:length(prune_interval)\n" + + "%\txline(prune_interval(i,1));\n" + + "%\txline(prune_interval(i,2));\n" + + "%end\n" + + "\n" + + "% https://se.mathworks.com/help/matlab/ref/xregion.html\n"; + + "% xregion\n" + + "\n" + + "for i=1:1:length(prune_interval)\n" + + "\tx=prune_interval(i,1):1:prune_interval(i,2);\n" + + "\ty=[];\n" + + "\tfor j=1:1:length(x)\n" + + "\t\tidx=x(j);\n" + + "\t\tfor n=2:1:length(at)\n" + + "\t\t\tif idx<=at(n)\n" + + "\t\t\t\tt1=at(n-1);\n" + + "\t\t\t\tt2=at(n);\n" + + "\t\t\t\tv1=av(n-1);\n" + + "\t\t\t\tv2=av(n);\n" + + "\t\t\t\ty=[y,(idx-t1)*(v2-v1)/(t2-t1)+v1];\n" + + "\t\t\t\tbreak;\n" + + "\t\t\tend\n" + + "\t\tend\n" + + "\tend\n" + + "\ty1=y-e;\n" + + "\ty2=y+e;\n" + + "\tL1=[x,fliplr(x)];\n" + + "\tL2=[y1,fliplr(y2)];\n" + + "\tfill(L1,L2,'b','FaceAlpha',0.1);\n" + + "end"); } @Test public void mytest2() throws Exception { String csvData = "D:\\full-game\\BallSpeed.csv"; int start = 200000; - int range = 200; + int range = 100000; int end = start + range; SDTEncoder encoder = new SDTEncoder(); - double e = 80000.0 / 2; // std/2 + double e = 100000; // std/2 encoder.setCompDeviation(e / 2); long count = 0; String line; @@ -172,17 +243,18 @@ public class SDTEncoderTest { List<Long> valueList = new ArrayList<>(); List<Integer> selectTimestamps = new ArrayList<>(); List<Long> selectValues = new ArrayList<>(); + List<ValuePoint> points = new ArrayList<>(); int idx = 0; try (BufferedReader reader = new BufferedReader(new FileReader(csvData))) { while ((line = reader.readLine()) != null) { count++; if (count >= start && count < end) { idx++; -// long time = Long.parseLong(line.split(",")[0]); - int time = idx; + int time = idx; // not real timestamp, but relative position id long value = Long.parseLong(line.split(",")[1]); timestampList.add(time); valueList.add(value); + points.add(new ValuePoint(time, value)); if (encoder.encodeLong(time, value)) { selectTimestamps.add((int) encoder.getTime()); selectValues.add(encoder.getLongValue()); @@ -197,18 +269,31 @@ public class SDTEncoderTest { } } - System.out.println("close all;clear all;clc;"); - System.out.println("e=" + e); - System.out.println("t=" + timestampList + ";"); - System.out.println("v=" + valueList + ";"); - System.out.println("at=" + selectTimestamps + ";"); - System.out.println("av=" + selectValues + ";"); + // System.out.println("e=" + e); + // System.out.println("t=" + timestampList + ";"); + // System.out.println("v=" + valueList + ";"); + // System.out.println("at=" + selectTimestamps + ";"); + // System.out.println("av=" + selectValues + ";"); + System.out.println("v.size=" + valueList.size()); + System.out.println("av.size=" + selectTimestamps.size()); + + System.out.println("start test------"); + + // ValuePoint[] myArray = (ValuePoint[]) points.toArray(); + // Arrays.sort(points.toArray()); + points.sort( + new Comparator<ValuePoint>() { + public int compare(ValuePoint o1, ValuePoint o2) { + return ((Comparable) (o1.value)).compareTo(o2.value); + } + }); + + long startTime = System.nanoTime(); // 计算maxLB - long maxVal = Collections.max(selectValues); -// int maxIdx = selectTimestamps.get(selectValues.indexOf(maxVal)); + long maxVal = points.get(points.size() - 1).value; double threshold = maxVal - e; // maxLB - System.out.println("threshold(maxLB)=" + threshold); + // System.out.println("threshold(maxLB)=" + threshold); // 计算UB<maxLB的剪枝段 List<Integer> prune_intervals_start = new ArrayList<>(); @@ -241,13 +326,13 @@ public class SDTEncoderTest { prune_intervals_start.add(interval_start); prune_intervals_end.add(interval_end); } - System.out.println("UB<maxLB prune intervals (included ends):"); - System.out.println(prune_intervals_start); - System.out.println(prune_intervals_end); + // System.out.println("UB<maxLB prune intervals (included ends, starting from 1):"); + // System.out.println(prune_intervals_start); + // System.out.println(prune_intervals_end); // 对剪枝段取余后搜索遍历计算TP int startIdx = 1; - int endIdx = 200; + int endIdx = range; startIdx = startIdx - 1; // as excluded treated endIdx = endIdx + 1; // as excluded treated prune_intervals_start.add(endIdx); // turn into search_intervals_end (excluded) @@ -257,16 +342,43 @@ public class SDTEncoderTest { for (int i = 0; i < prune_intervals_start.size(); i++) { int search_interval_start = prune_intervals_end.get(i) + 1; // included int search_interval_end = prune_intervals_start.get(i) - 1; // included - System.out.println(search_interval_start + "," + search_interval_end); - for (int j = search_interval_start; j <= search_interval_end; j++) { - long v = valueList.get(j); + // System.out.println(search_interval_start + "," + search_interval_end); + for (int j = search_interval_start; j <= search_interval_end; j++) { // starting from 1 + long v = valueList.get(j - 1); // java list starting from 0 if (v > candidateTPvalue) { candidateTPvalue = v; candidateTPidx = j; } } } + long elapsedTime = System.nanoTime() - startTime; + System.out.println("search with value index: " + elapsedTime / 1000000.0 + " m s"); System.out.println("TP=(" + candidateTPidx + "," + candidateTPvalue + ")"); + System.out.println("search interval number=" + prune_intervals_end.size()); + int traversedPoints = 0; + for (int i = 0; i < prune_intervals_start.size(); i++) { + int search_interval_start = prune_intervals_end.get(i) + 1; // included + int search_interval_end = prune_intervals_start.get(i) - 1; // included + if (search_interval_end >= search_interval_start) { + traversedPoints += (search_interval_end - search_interval_start + 1); + } + } + System.out.println("number of traversed points: " + traversedPoints); + + System.out.println("start test------"); + startTime = System.nanoTime(); + long candidateTPvalue_raw = -1; + int candidateTPidx_raw = -1; + for (int j = 1; j <= valueList.size(); j++) { // starting from 1 + long v = valueList.get(j - 1); // java list starting from 0 + if (v > candidateTPvalue_raw) { + candidateTPvalue_raw = v; + candidateTPidx_raw = j; + } + } + elapsedTime = System.nanoTime() - startTime; + System.out.println("search without value index: " + elapsedTime / 1000000.0 + " m s"); + System.out.println("TP=(" + candidateTPidx_raw + "," + candidateTPvalue_raw + ")"); } @Test
