3.1 算法一：逐一合并算法
3.1.1 算法描述
如图3.我们先将所有的时间片段按照起始时刻排序，后面的处理过程即依次判定相邻两个时间片段的三种关系，并将统计时间进行合并，合并的时间片段可以作为一个新的时间片段与后继的时间片段进行相关的计算。
图3.新的时间片段统计算法。
算法部分总共分两步，
一，将时间片段按开始时间进行排序，这里可以使用冒泡或快速排序算法。
二，1. 从第一个时间片段period 1开始，与后面的period 2 进行比较，取二者的并集，得到的新的period 2’。
2.重复上面的过程，直到最后一个时间片段并入最终的时间片段为止。
3.1.2 算法实现
为方便这里将时间都统一处理为long型，事实上，计算时间差也的确需要取date类型数据的long值再进行相关计算。
package com.example.demo.mine.time_collect; import java.util.*;import lombok.Data;import lombok.extern.slf4j.Slf4j; /* * * @author lunyu * @since 2018-03-03 /@Slf4jpublic class StatisticTime {// long currentTime = System.currentTimeMillis();</span><span>public</span> <span>static</span> <span>void</span><span> main(String[] args) { </span><span>//</span><span> 1.产生随机数据</span> <span>int</span> size = 10<span>; List</span><period> periods = <span>new</span> ArrayList<period><span>();
//不失准确性，可以设当前时间是0
long currentTime = 0;
int range = 100;
int start;
int end;
int coi;
Random random = new Random();
for (int i = 0; i < size; i++){
//区间膨胀系数
coi = random.nextInt(9)+1;
start = random.nextInt(rangecoi);
end = random.nextInt(rangecoi) + start;Period period </span>= <span>new</span> Period(currentTime + start, currentTime +<span> end); log.info(</span>"时间片段：{}-{}"<span>, period.getStartTime(), period.getEndTime()); periods.add(period); } </span><span>//</span><span>2.算法执行 </span><span>//</span><span>2.1先对各个时间段按开始时刻进行排序</span>sortPeriodsByStartTime(periods);
</span><span>//</span><span>2.2对数据统计</span> <span>long</span> totalSpendTime =<span> statisticTime(periods); log.info(</span>"总用时：{}"<span>, totalSpendTime); } </span><span>/**</span><span> * 对排序后的数据进行统计 * </span><span>@param</span><span> periods * </span><span>@return</span> <span>*/</span> <span>private</span> <span>static</span> <span>long</span> statisticTime(List<period><span> periods) { </span><span>long</span> sum = periods.get(0).getEndTime() - periods.get(0<span>).getStartTime(); </span><span>for</span>(<span>int</span> i = 0; i < periods.size() - 1; i++<span>) { </span><span>//</span><span>1.如果(period i) 和(period i+1)相交,例： </span><span>//</span><span> ------------ </span><span>//</span><span> ---------</span> <span>if</span> (periods.get(i).getEndTime() > periods.get(i + 1<span>).getStartTime() </span>&& periods.get(i).getEndTime() < periods.get(i + 1<span>).getEndTime()) { sum </span>+= periods.get(i + 1).getEndTime() -<span> periods.get(i).getEndTime(); </span><span>//</span><span>2.如果(period i) 和(period i+1)不相交,例： </span><span>//</span><span>----------- </span><span>//</span><span> ------</span> }<span>else</span> <span>if</span> (periods.get(i).getEndTime() <=>).getStartTime()) { sum += periods.get(i + 1).getEndTime() - periods.get(i + 1<span>).getStartTime(); </span><span>//</span><span>3.如果(period i) 包含(period i+1),例： </span><span>//</span><span>--------------- </span><span>//</span><span> -----------</span> }<span>else</span> <span>if</span> (periods.get(i).getEndTime() >= periods.get(i + 1<span>).getEndTime()) { </span><span>//</span><span>这时什么都不做，因为(period i) 所对应的长度即为(period i) 和(period i+1)并集的时间长度。 </span><span>//</span><span>sum +=0;</span>}
}
return sum;
}</span><span>/**</span><span> * 对时间段按开始时间进行顺序排序，简单起见，用冒泡算法 * </span><span>@param</span><span> periods </span><span>*/</span> <span>private</span> <span>static</span> <span>void</span> sortPeriodsByStartTime(List<period><span> periods) { </span><span>//</span><span>冒泡法，从后向前冒泡</span> <span>for</span>(<span>int</span> i = periods.size() - 1; i > 0; i--<span>) { </span><span>for</span>(<span>int</span> j = periods.size() - 2; j >= 0; j--<span>) { </span><span>if</span> (periods.get(j).getStartTime() > periods.get(j+1<span>).getStartTime()) { swap(periods, j, j</span>+1<span>); } } } } </span><span>/**</span><span> * 交换对象 * </span><span>@param</span><span> periods * </span><span>@param</span><span> j * </span><span>@param</span><span> i * </span><span>@return</span> <span>*/</span> <span>private</span> <span>static</span> <span>void</span> swap(List<period> periods, <span>int</span> j, <span>int</span><span> i) { Period tempPeriod </span>= <span>new</span> Period(0, 0<span>); tempPeriod </span>=<span> periods.get(j); periods.set(j, periods.get(i)); periods.set(i, tempPeriod); } </span><span>/**</span><span> * 区间对象 * </span><span>@author</span><span> lunyu * </span><span>@since</span><span> 2018-03-03 </span><span>*/</span><span> @Data </span><span>private</span> <span>static</span> <span>class</span><span> Period{ </span><span>public</span> Period(<span>long</span> startTime, <span>long</span><span> endTime) { </span><span>super</span><span>(); </span><span>this</span>.startTime =<span> startTime; </span><span>this</span>.endTime =<span> endTime; } </span><span>/**</span><span> * 开始时间 </span><span>*/</span> <span>private</span> <span>long</span><span> startTime; </span><span>/**</span><span> * 结束时间 </span><span>*/</span> <span>private</span> <span>long</span><span> endTime; }}
View Code不难知道算法的空间复杂度为O(1)，时间复杂度为O(n2) (排序冒泡算法复杂度：O(n2) + 时间片段并集计算复杂度：O(n))。
3.2 算法二：化整为零算法
3.2.1 算法描述
将每个时间片段的端点，都取出，并排序，我们就得到了n个细粒度服务分割的2n个时间点。
如图所示蓝色虚线与时间轴的交点表示每个时间端点，这些端点分割了时间从t1,t2一直持续到t2n。
将这些区间段分别与每个细粒度服务的时间片段进行比较，如果在某个细粒度服务的时间片段内，那么我们认为该时间段为执行时间。
图4.细粒度服务端点对时间的分割。
3.2.2 算法实现
import com.google.common.collect.Lists; import java.util.ArrayList; import java.util.List; import java.util.Random; import lombok.Data; import lombok.extern.slf4j.Slf4j; /* * 化整为零的方式处理代码 * @author lunyu * @since 2018-03-03 /@Slf4jpublic class StatisticTimeByAll2Part {// long currentTime = System.currentTimeMillis();</span><span>public</span> <span>static</span> <span>void</span><span> main(String[] args) { </span><span>//</span><span> 1.产生随机数据</span> <span>int</span> size = 10<span>; List</span><period> periods = <span>new</span> ArrayList<period><span>();
//不失准确性，可以设当前时间是0
long currentTime = 0;
int range = 100;
int start;
int end;
int coi;
Random random = new Random();
for (int i = 0; i < size; i++){
//区间膨胀系数
coi = random.nextInt(9)+1;
start = random.nextInt(rangecoi);
end = random.nextInt(rangecoi) + start;Period period </span>= <span>new</span> Period(currentTime + start, currentTime +<span> end); log.info(</span>"时间片段：{}-{}"<span>, period.getStartTime(), period.getEndTime()); periods.add(period); } </span><span>//</span><span>2.算法执行 </span><span>//</span><span>2.1 获取所有的时间点集合</span> List<long> allTimePoints =<span> getAllTimePoints(periods); </span><span>//</span><span>2.2 对所有的时间点集合进行排序</span>sort(allTimePoints);
</span><span>//</span><span>2.2对数据统计</span> <span>long</span> totalSpendTime =<span> statisticTime(allTimePoints, periods); log.info(</span>"总用时：{}"<span>, totalSpendTime); } </span><span>private</span> <span>static</span> <span>long</span> statisticTime(List<long> allTimePoints, List<period><span> periods) { </span><span>long</span> totolSpendTime = 0<span>; </span><span>for</span> (<span>int</span> i = 0; i < allTimePoints.size() -1; i++<span>){ </span><span>long</span> startTimePoint =<span> allTimePoints.get(i); </span><span>long</span> endTimePoint = allTimePoints.get(i + 1<span>); </span><span>//</span><span>对时间进行验证</span> <span>for</span><span> (Period period : periods){ </span><span>//</span><span>如果某个（细粒度）时间片段包含该分割的时间片段，则认为分割的时间片段执行时间</span> <span>if</span> (startTimePoint >=<span> period.getStartTime() </span>&& endTimePoint <=<span> period.getEndTime()){ totolSpendTime += (endTimePoint -<span> startTimePoint); </span><span>break</span><span>; } } } </span><span>return</span><span> totolSpendTime; } </span><span>/**</span><span> * 为简单起见，用冒泡法对时间点进行排序 </span><span>*/</span> <span>private</span> <span>static</span> <span>void</span> sort(List<long><span> allTimePoints) { </span><span>//</span><span>冒泡法，从后向前冒泡</span> <span>for</span>(<span>int</span> i = allTimePoints.size() - 1; i > 0; i--<span>) { </span><span>for</span>(<span>int</span> j = allTimePoints.size() - 2; j >= 0; j--<span>) { </span><span>if</span> (allTimePoints.get(j) > allTimePoints.get(j+1<span>)) { swap(allTimePoints, j, j</span>+1<span>); } } } } </span><span>/**</span><span> * 交换对象 * </span><span>@param</span><span> allTimePoints * </span><span>@param</span><span> j * </span><span>@param</span><span> i * </span><span>@return</span> <span>*/</span> <span>private</span> <span>static</span> <span>void</span> swap(List<long> allTimePoints, <span>int</span> j, <span>int</span><span> i) { </span><span>long</span> tempPeriod =<span> allTimePoints.get(j); allTimePoints.set(j, allTimePoints.get(i)); allTimePoints.set(i, tempPeriod); } </span><span>/**</span><span> * 获得所有的时间点 * </span><span>@param</span><span> periods * </span><span>@return</span> <span>*/</span> <span>private</span> <span>static</span> List<long> getAllTimePoints(List<period><span> periods) { List</span><long> allTimePoints =<span> Lists.newArrayList(); </span><span>for</span><span> (Period period : periods){ allTimePoints.add(period.getStartTime()); allTimePoints.add(period.getEndTime()); } </span><span>return</span><span> allTimePoints; } </span><span>/**</span><span> * 区间对象 * </span><span>@author</span><span> lunyu * </span><span>@since</span><span> 2018-03-03 </span><span>*/</span><span> @Data </span><span>private</span> <span>static</span> <span>class</span><span> Period{ </span><span>public</span> Period(<span>long</span> startTime, <span>long</span><span> endTime) { </span><span>super</span><span>(); </span><span>this</span>.startTime =<span> startTime; </span><span>this</span>.endTime =<span> endTime; } </span><span>/**</span><span> * 开始时间 </span><span>*/</span> <span>private</span> <span>long</span><span> startTime; </span><span>/**</span><span> * 结束时间 </span><span>*/</span> <span>private</span> <span>long</span><span> endTime; }}
View Code不难知道，需要一个list用以保存2n各时间端点，因此，该算法的空间复杂度为2O(n)。对2n个时间端点进行排序，其时间复杂度为4O(n2)，每个分割的时间段与细粒度服务的时间段比较，最多比较2n*n次，其时间复杂度为O(2n2)，因此总的时间复杂度为4O(n2)。
四、问题的推广
4.1 二维覆盖的情况
4.1.1 问题分析
为简单起见，这里只考虑矩形覆盖的问题。
图4. 随机分布的矩形及其覆盖。
如图，左侧是一系列随机的矩形，这些矩形可能相交，也可能不相交，我们的目的是求这些矩形覆盖的面积（右侧）。
说说问题的复杂性，这个问题本来我想用一维时间段的方式拓展到二维来处理。发现，实际上行不通。因为，二维矩形图形之间的关系不能简单划归为两个矩形之间的关系。首先图形间的关系是一种偏序关系，即按照x轴的顺序是acb但是按照y轴的顺序是abc，如图5。
图5.三个矩形的某种分布。
这样就会造成如下问题：
- 当进行面积计算的时候，随着矩形块的增加，数据的计算会越来越复杂，也就是不能像之前一样排序之后，数据可以化归到更简单的二元形式。比如上图，把a和b矩形合并后，再与c进行面积运算的时候，必须要同时计算a-c，b-c的关系。
- 矩形不能随意的移动，比如a-c间的关系，两者的关系是固定的，不能随意移动。
由于上述问题的存在，目前能想到的解决方案即通过3.2算法二（化整为零算法）的方式来解决。
4.1.2 算法描述
算法如下：
- 统计所有的矩形组成的A集合中矩形的横坐标和纵坐标，并将横坐标和纵坐标进行排序。
- 依次取相邻的横坐标，相邻的纵坐标，相邻的横坐标和相邻的纵坐标这样可以组成一个个小的矩形集合B。
- 依次对矩形B集合中元素b与矩形A集合中a进行比较，如果矩形b包含于矩形a，则加上矩形b的面积，否则，跳过。
图6. 横坐标纵坐标对图形区域的分割和覆盖。
如图6，蓝色的线将矩形块，分割成一块块更小的矩形区块，求覆盖的区块所占的面积就可以对这些小区块分别判定求和。
4.1.3 算法实现
import com.google.common.collect.Lists; import java.math.BigDecimal; import java.util.Collections; import java.util.List; import java.util.Random; import lombok.AllArgsConstructor; import lombok.Data; import lombok.experimental.Accessors; import lombok.extern.slf4j.Slf4j; /* * 面积统计 /@Slf4jpublic class AreaStatisticByAll2Part {</span><span>public</span> <span>static</span> <span>void</span><span> main(String[] args) { </span><span>//</span><span> 1.产生随机数据</span> <span>int</span> size = 2<span>; </span><span>int</span> range = 100<span>; </span><span>int</span><span> xLeft; </span><span>int</span><span> xRight; </span><span>int</span><span> yLower; </span><span>int</span><span> yUpper; </span><span>int</span><span> coi; Random random </span>= <span>new</span><span> Random(); List</span><rectangle> rectangleList =<span> Lists.newArrayList(); </span><span>for</span> (<span>int</span> i = 0; i < size; i++<span>){ </span><span>//</span><span>区间膨胀系数</span> coi = random.nextInt(9) + 1<span>; xLeft </span>= random.nextInt(range*<span>coi); xRight </span>= random.nextInt(range*coi) +<span> xLeft; coi </span>= random.nextInt(9) + 1<span>; yLower </span>= random.nextInt(range*<span>coi); yUpper </span>= random.nextInt(range*coi) +<span> yLower; Rectangle rectangle </span>= <span>new</span><span> Rectangle(xLeft, xRight, yLower, yUpper); log.info(rectangle.toString()); rectangleList.add(rectangle); } </span><span>//</span><span>1.将横坐标和纵坐标的数据分别装载并进行排序</span> List<integer> xAxes =<span> getXAxes(rectangleList); List</span><integer> yAxes =<span> getYAxes(rectangleList); Collections.sort(xAxes); Collections.sort(yAxes); </span><span>//</span><span>2.对数据进行比较</span> BigDecimal areaSum =<span> compareAndGetAreaSum(xAxes, yAxes, rectangleList); log.info(</span>"总面积:{}"<span>, areaSum.toString()); } </span><span>/**</span><span> * 比较并获得面积 </span><span>*/</span> <span>private</span> <span>static</span> BigDecimal compareAndGetAreaSum(List<integer> xAxes, List<integer> yAxes, List<rectangle><span> rectangleList) { BigDecimal areaSum </span>=<span> BigDecimal.ZERO; </span><span>for</span> (<span>int</span> i = 0; i < xAxes.size() -1; i++<span>){ </span><span>int</span> xLeft =<span> xAxes.get(i); </span><span>int</span> xRight = xAxes.get(i + 1<span>); </span><span>for</span> (<span>int</span> j = 0; j < yAxes.size() -1; j++<span>){ </span><span>int</span> yLower =<span> yAxes.get(j); </span><span>int</span> yUpper = yAxes.get(j + 1<span>); </span><span>for</span><span> (Rectangle rectangle : rectangleList){ </span><span>if</span> (xLeft >= rectangle.getXLeft() && xRight <=<span> rectangle.getXRight() && yLower>= rectangle.getYLower() && yUpper <=<span> rectangle.getYUpper()){ areaSum = areaSum.add(BigDecimal.valueOf((xRight - xLeft) * (yUpper -<span> yLower))); </span><span>break</span><span>; } } } } </span><span>return</span><span> areaSum; } </span><span>/**</span><span> * 获得所有的Y轴坐标数据 </span><span>*/</span> <span>private</span> <span>static</span> List<integer> getYAxes(List<rectangle><span> rectangleList) { List</span><integer> yAxes =<span> Lists.newArrayList(); </span><span>for</span><span> (Rectangle rectangle : rectangleList){ yAxes.add(rectangle.getYLower()); yAxes.add(rectangle.getYUpper()); } </span><span>return</span><span> yAxes; } </span><span>/**</span><span> * 获得所有的X轴坐标数据 </span><span>*/</span> <span>private</span> <span>static</span> List<integer> getXAxes(List<rectangle><span> rectangleList) { List</span><integer> xAxes =<span> Lists.newArrayList(); </span><span>for</span><span> (Rectangle rectangle : rectangleList){ xAxes.add(rectangle.getXLeft()); xAxes.add(rectangle.getXRight()); } </span><span>return</span><span> xAxes; } </span><span>/**</span><span> * 矩形实体 </span><span>*/</span><span> @Data @AllArgsConstructor @Accessors(chain </span>= <span>true</span><span>) </span><span>public</span> <span>static</span> <span>class</span><span> Rectangle { </span><span>private</span><span> Integer xLeft; </span><span>private</span><span> Integer xRight; </span><span>private</span><span> Integer yLower; </span><span>private</span><span> Integer yUpper; }}
View Code不难知道，算法的空间复杂度是 4O(n)（用以存储横坐标和纵坐标的空间是2n+2n=4n个），时间复杂度是4O(n3)(排序的时间复杂度O(n2)(以冒泡算法为例) ，循环比较的次数为2n2nn=4n3次）。
4.2 三维及以上的情形
可以以此类推，将三维或更高纬度的空间分割成一个个小的空间，将这些空间一一与随机分布的立方体（或超体）进行比较，比较的结果并统计最终结果。不难知道，k维的情形，算法的空间复杂度是O(2kn)，算法的时间复杂度是O(2(k-1)nk)。
Original: https://www.cnblogs.com/lunyu/p/10561220.html
Author: 论语
Title: 粗粒度服务的执行时间统计算法实现及问题推广
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/612568/
转载文章受原作者版权保护。转载请注明原作者出处！