Java【算法分享 02】道格拉斯-普克 Douglas-Peucker 抽稀算法分析及15w个坐标点抽稀到3.7w耗时从360s+优化到365ms接近1000倍的速度提升(并行流+多线程+泛型)

简介: Java【算法分享 02】道格拉斯-普克 Douglas-Peucker 抽稀算法分析及15w个坐标点抽稀到3.7w耗时从360s+优化到365ms接近1000倍的速度提升(并行流+多线程+泛型)

1.分析

算法详细流程可查看《道格拉斯抽稀算法流程图解+使用JDK8方法实现+详细注解源码》经典的 D-P 算法描述如下【红色部分用于辅助理解 可忽略】:

  1. 连接当前矢量曲线首尾点a、b,该直线AB为当前矢量曲线的弦;
  2. 计算首尾点a、b间所有坐标点到该弦AB的距离,并获取最大距离d及其的坐标点c
  3. 比较最大距离d与给定的阈值thresholdVal,小于阈值,当前弦AB可作为曲线的近似【首尾间的坐标点将被抽稀】,该段矢量曲线处理完毕。
  4. 大于阈值,使用最大距离坐标点c分割当前矢量曲线,分割后的两段矢量曲线分别使用1~3的流程进行处理。
  5. 全部处理完毕后,依次连接各个分割点形成的折线,即可以作为整个曲线的近似。

算法耗时及问题分析:

  1. M ( x 0 , y 0 ) M(x_{0},y_{0})M(x0,y0) 到直线 A x + B y + C = 0 Ax+By+C=0Ax+By+C=0 的距离 d :image.png

坐标点较多时,每个点都要计算 A、B、C 三个参数并求解 d 将消耗不少时间。【耗时】

  1. 得到分割点后,递归调用起止点计算标记删除点方法,可能出现栈溢出。【问题】
  2. thresholdVal 值越小保留细节将越多,分割点会呈现指数级增长,耗时会增加,需要找到合理值。【耗时+问题】
  3. 返回对象包含字段不统一,抽稀算法无法接收不同类型参数。【问题】

2.优化

1️⃣ 个算法使用的封装类和 1️⃣ 个业务使用封装类用于举例【为了简洁注解未使用DOC规范】:

// 类1 坐标数据封装
@Data
public class PointData {
    // 标记是否删除(0保留 1删除)
    private int isDelete;
    // 数据点的 index 用于优化运算速度(核心优化点)
    private int indexEx;
  // 数据点的经度
    private double longitudeEx;
    // 数据点的纬度
    private double latitudeEx;
}
// 类2 业务查询返回的数据封装【主要是实现了 PointData 类】具体字段不再贴出
@Data
public class Mobile2g extends PointData implements Serializable {
}

线程池不做过多介绍:

public class ThreadAllBaseStation {
    private static int corePoolSize = Runtime.getRuntime().availableProcessors();
    private static ThreadFactory namedFactory = new ThreadFactoryBuilder().setNameFormat("XXX数据查询线程-%d").build();
    /**
     * corePoolSize用于指定核心线程数量
     * maximumPoolSize指定最大线程数
     * keepAliveTime和TimeUnit指定线程空闲后的最大存活时间
     */
    public static ThreadPoolExecutor executor = new ThreadPoolExecutor(corePoolSize, corePoolSize + 1, 10L, TimeUnit.SECONDS,
            new LinkedBlockingQueue<>(1000), namedFactory, new ThreadPoolExecutor.AbortPolicy());
}

优化后的算法核心代码【为了简洁部分注解未使用DOC规范】:

@Slf4j
public class Douglas {
    // 点数据
    private static List<? extends PointData> points = new ArrayList<>();
    // 距离阈值(值越大效果越好但丢失细节就越多)【这个值已经算很小的了】
    private static final double DISTANCE_THRESHOLD = 0.00001;
    // 最大线程数
    private static final int MAX_THREAD_SIZE = 60;
    /**
     * 标记要删除的点(并获取分割点数据)
     *
     * @param from 矢量曲线的起始点
     * @param to   矢量曲线的终止点
     * @return 起始点 终止点 分割点
     */
    private static PointData[] markDeletePointsAndGetSplitPoint(PointData from, PointData to) {
        // 计算由起始点和终止点构成直线方程一般式的系数
        double fromLat = from.getLatitudeEx();
        double fromLng = from.getLongitudeEx();
        double toLat = to.getLatitudeEx();
        double toLng = to.getLongitudeEx();
        // 求解点到直线距离方程的参数
        double fromLatMinusToLat = fromLat - toLat;
        double fromLngMinusToLng = fromLng - toLng;
        double sqrtPowAddVal = Math.sqrt(Math.pow(fromLatMinusToLat, 2) + Math.pow(fromLngMinusToLng, 2));
        double parameterA = (fromLatMinusToLat) / sqrtPowAddVal;
        double parameterB = (toLng - fromLng) / sqrtPowAddVal;
        double parameterC = (fromLng * toLat - toLng * fromLat) / sqrtPowAddVal;
        // 获取点数据下标(并排除相邻两点的情况)【最核心的优化】
        int fromIndex = from.getIndexEx();
        int toIndex = to.getIndexEx();
        if (toIndex == fromIndex + 1) {
            return new PointData[]{};
        }
        // 起止点之间的点到起止点连线的距离数据集合并获取最大距离及分割点
        double distanceMax = 0;
        PointData splitPoint = null;
        double powAddRes = Math.pow(parameterA, 2) + Math.pow(parameterB, 2);
        for (int i = fromIndex + 1; i < toIndex; i++) {
            double lng = points.get(i).getLongitudeEx();
            double lat = points.get(i).getLatitudeEx();
            // 点到直线的距离
            double distance = Math.abs(parameterA * (lng) + parameterB * (lat) + parameterC) / Math.sqrt(powAddRes);
            if (distance > distanceMax) {
                distanceMax = distance;
                splitPoint = points.get(i);
            }
        }
        // 最大距离与距离阈值进行比较
        if (distanceMax < DISTANCE_THRESHOLD) {
            // 小于则标记 points(fromIndex,toIndex) 内的坐标(用于删除)
            for (int i = fromIndex + 1; i < toIndex; i++) {
                points.get(i).setIsDelete(1);
            }
        } else {
            // 返回起止点和分割点坐标
            return new PointData[]{from, to, splitPoint};
        }
        return new PointData[]{};
    }
    /**
     * 进行抽稀:标记要删除的点并筛选
     *
     * @param source 矢量曲线点数据
     * @return 抽稀后的点数据
     */
    public static List<? extends PointData> toDilute(List<? extends PointData> source) throws InterruptedException {
        // 抽稀前的点数据
        points = source;
        // 进行标记
        if (!CollectionUtils.isEmpty(points)) {
            // 首次标记
            long s1 = System.currentTimeMillis();
            PointData[] pointData = markDeletePointsAndGetSplitPoint(points.get(0), points.get(points.size() - 1));
            long s2 = System.currentTimeMillis();
            log.info("首次标记用时:" + (s2 - s1) + "ms");
            // 如果有分割点将进行分割标记
            int pointDataLength = 3;
            if (pointData.length == pointDataLength) {
                CopyOnWriteArrayList<PointData[]> splitPointList = new CopyOnWriteArrayList<>();
                splitPointList.add(pointData);
                // 使用线程池进行分割标记
                do {
                    splitPointList = markDeletePointsAndGetSplitPointByThread(splitPointList);
                } while (!splitPointList.isEmpty());
            }
        }
        // 筛选掉标记为删除的点
        return points.parallelStream().filter(point -> point.getIsDelete() != 1).collect(Collectors.toList());
    }
    /**
     * 使用多线程:标记要删除的点(并获取分割点数据)
     *
     * @param splitPointList 起始点及分割点栈数据
     * @return 新的起始点及分割点栈数据
     * @throws InterruptedException 线程等待可能出现的问题
     */
    private static CopyOnWriteArrayList<PointData[]> markDeletePointsAndGetSplitPointByThread(CopyOnWriteArrayList<PointData[]> splitPointList) throws InterruptedException {
        // 新一轮要处理的分割数据
        CopyOnWriteArrayList<PointData[]> splitPointListRes = new CopyOnWriteArrayList<>();
        int pointDataLength = 3;
        int splitPointListSize = splitPointList.size();
        log.info("当前列表Size:" + splitPointListSize);
        int numberBatch = MAX_THREAD_SIZE;
        double number = splitPointListSize * 1.0 / numberBatch;
        int n = ((Double) Math.ceil(number)).intValue();
        for (int i = 0; i < n; i++) {
            int end = numberBatch * (i + 1);
            if (end > splitPointListSize) {
                end = splitPointListSize;
            }
            List<PointData[]> pointData = splitPointList.subList(numberBatch * i, end);
            log.info("当前执行 " + numberBatch * i + " 到 " + end + "条数据");
            CountDownLatch countDownLatch = new CountDownLatch(pointData.size());
            ThreadPoolExecutor executor = ThreadAllBaseStation.executor;
            pointData.forEach(point -> {
                executor.submit(() -> {
                    PointData[] pointDataLeft = markDeletePointsAndGetSplitPoint(point[0], point[2]);
                    if (pointDataLeft.length == pointDataLength) {
                        splitPointListRes.add(pointDataLeft);
                    }
                    PointData[] pointDataRight = markDeletePointsAndGetSplitPoint(point[2], point[1]);
                    if (pointDataRight.length == pointDataLength) {
                        splitPointListRes.add(pointDataRight);
                    }
                    countDownLatch.countDown();
                });
            });
            countDownLatch.await();
        }
        return splitPointListRes;
    }
}

算法使用结合业务【伪代码】:

@OverrideData
    public void douglasAlgorithmTest() {
        // 抽稀前数据查询(坐标点需要有序)
        List<Mobile2g> beforeDouglas = selectData("queryParam");
        // 抽稀字段处理(坐标点)【优化】
        beforeDouglas.forEach(bd -> {
          bd.setIndexEx(indexEx.getAndIncrement());
            bd.setLongitudeEx(bd.getLongitude());
            bd.setLatitudeEx(bd.getLatitude());
        });
        // 抽稀后保存
        List<Mobile2g> afterDouglas = null;
        try {
          // 调用抽稀算法
            afterDouglas = (List<Mobile2g>) Douglas.toDilute(beforeDouglas);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }

3.总结

  1. 使用泛型解决了不同对象的抽稀问题。
  2. 优化最大距离及分割点的获取方法。
  3. 使用多线程和并行流计算缩短了抽稀时间【增大线程MAX_THREAD_SIZE仍然可以提升效率】。
  4. 最核心的优化
// 原始代码【这个速度是很慢的 要比对每个对象才能找到 index】
int fromIndex = points.indexOf(from); 
// 事先对 PointData 对象添加了indexEx 属性 结果是惊人的快
int fromIndex = from.getIndexEx();
目录
相关文章
|
22天前
|
监控 算法 Java
Java虚拟机(JVM)垃圾回收机制深度剖析与优化策略####
本文作为一篇技术性文章,深入探讨了Java虚拟机(JVM)中垃圾回收的工作原理,详细分析了标记-清除、复制算法、标记-压缩及分代收集等主流垃圾回收算法的特点和适用场景。通过实际案例,展示了不同GC(Garbage Collector)算法在应用中的表现差异,并针对大型应用提出了一系列优化策略,包括选择合适的GC算法、调整堆内存大小、并行与并发GC调优等,旨在帮助开发者更好地理解和优化Java应用的性能。 ####
29 0
|
1天前
|
缓存 算法 搜索推荐
Java中的算法优化与复杂度分析
在Java开发中,理解和优化算法的时间复杂度和空间复杂度是提升程序性能的关键。通过合理选择数据结构、避免重复计算、应用分治法等策略,可以显著提高算法效率。在实际开发中,应该根据具体需求和场景,选择合适的优化方法,从而编写出高效、可靠的代码。
15 6
|
23天前
|
存储 监控 小程序
Java中的线程池优化实践####
本文深入探讨了Java中线程池的工作原理,分析了常见的线程池类型及其适用场景,并通过实际案例展示了如何根据应用需求进行线程池的优化配置。文章首先介绍了线程池的基本概念和核心参数,随后详细阐述了几种常见的线程池实现(如FixedThreadPool、CachedThreadPool、ScheduledThreadPool等)的特点及使用场景。接着,通过一个电商系统订单处理的实际案例,分析了线程池参数设置不当导致的性能问题,并提出了相应的优化策略。最终,总结了线程池优化的最佳实践,旨在帮助开发者更好地利用Java线程池提升应用性能和稳定性。 ####
|
14天前
|
存储 Java
Java 11 的String是如何优化存储的?
本文介绍了Java中字符串存储优化的原理和实现。通过判断字符串是否全为拉丁字符,使用`byte`代替`char`存储,以节省空间。具体实现涉及`compress`和`toBytes`方法,前者用于尝试压缩字符串,后者则按常规方式存储。代码示例展示了如何根据配置决定使用哪种存储方式。
|
23天前
|
存储 算法 Java
Java 内存管理与优化:掌控堆与栈,雕琢高效代码
Java内存管理与优化是提升程序性能的关键。掌握堆与栈的运作机制,学习如何有效管理内存资源,雕琢出更加高效的代码,是每个Java开发者必备的技能。
49 5
|
24天前
|
监控 算法 Java
jvm-48-java 变更导致压测应用性能下降,如何分析定位原因?
【11月更文挑战第17天】当JVM相关变更导致压测应用性能下降时,可通过检查变更内容(如JVM参数、Java版本、代码变更)、收集性能监控数据(使用JVM监控工具、应用性能监控工具、系统资源监控)、分析垃圾回收情况(GC日志分析、内存泄漏检查)、分析线程和锁(线程状态分析、锁竞争分析)及分析代码执行路径(使用代码性能分析工具、代码审查)等步骤来定位和解决问题。
|
21天前
|
存储 监控 算法
Java虚拟机(JVM)垃圾回收机制深度解析与优化策略####
本文旨在深入探讨Java虚拟机(JVM)的垃圾回收机制,揭示其工作原理、常见算法及参数调优方法。通过剖析垃圾回收的生命周期、内存区域划分以及GC日志分析,为开发者提供一套实用的JVM垃圾回收优化指南,助力提升Java应用的性能与稳定性。 ####
|
19天前
|
算法
基于WOA算法的SVDD参数寻优matlab仿真
该程序利用鲸鱼优化算法(WOA)对支持向量数据描述(SVDD)模型的参数进行优化,以提高数据分类的准确性。通过MATLAB2022A实现,展示了不同信噪比(SNR)下模型的分类误差。WOA通过模拟鲸鱼捕食行为,动态调整SVDD参数,如惩罚因子C和核函数参数γ,以寻找最优参数组合,增强模型的鲁棒性和泛化能力。
|
25天前
|
机器学习/深度学习 算法 Serverless
基于WOA-SVM的乳腺癌数据分类识别算法matlab仿真,对比BP神经网络和SVM
本项目利用鲸鱼优化算法(WOA)优化支持向量机(SVM)参数,针对乳腺癌早期诊断问题,通过MATLAB 2022a实现。核心代码包括参数初始化、目标函数计算、位置更新等步骤,并附有详细中文注释及操作视频。实验结果显示,WOA-SVM在提高分类精度和泛化能力方面表现出色,为乳腺癌的早期诊断提供了有效的技术支持。
|
5天前
|
供应链 算法 调度
排队算法的matlab仿真,带GUI界面
该程序使用MATLAB 2022A版本实现排队算法的仿真,并带有GUI界面。程序支持单队列单服务台、单队列多服务台和多队列多服务台三种排队方式。核心函数`func_mms2`通过模拟到达时间和服务时间,计算阻塞率和利用率。排队论研究系统中顾客和服务台的交互行为,广泛应用于通信网络、生产调度和服务行业等领域,旨在优化系统性能,减少等待时间,提高资源利用率。