【云原生】SPL 提速天体聚类任务 2000 倍【文末送书】

您好，我是码农飞哥，感谢您阅读本文，欢迎一键三连哦。
💪🏻 1. Python基础专栏，基础知识一网打尽，9.9元买不了吃亏，买不了上当。 Python从入门到精通
❤️ 2. Python爬虫专栏，系统性的学习爬虫的知识点。9.9元买不了吃亏，买不了上当 。python爬虫入门进阶
❤️ 3. Ceph实战，从原理到实战应有尽有。 Ceph实战
❤️ 4. Java高并发编程入门，打卡学习Java高并发。 Java高并发编程入门
😁 5. 社区逛一逛，周周有福利，周周有惊喜。码农飞哥社区，飞跃计划

问题描述

国家天文台有个聚类任务：共11份数据，每份数据是从一张照片中提取出来的，包含500多万条记录，每条记录是一个天体的坐标及属性。11张“照片”中有些天体坐标是重复的，但这些重复的坐标不完全相同，他们会有一些差别但距离不会太远。任务就是把其中一张“照片”作为基础，从其他照片中找出重复的天体，把重复天体的坐标及属性均值作为该天体的最终坐标和属性，即把距离很近的天体聚成一类再做聚合运算，这样就可以得到一张坐标清晰且信息更加准确的天体“照片”。

问题分析

这个任务不算复杂，只要循环基础照片中的每一个天体坐标，将其与其他照片中的每个天体坐标计算距离，不超过某个阈值就认为是同一个天体，视作一类，最后将每一类中所有天体坐标求均值就得到了该天体的坐标。

但是当用计算机计算时就发现这个任务的计算量是惊人的，基础照片需要循环500多万次，其中的每个天体坐标又要与其他照片中的5000多万个坐标计算距离，计算复杂度是500多万*5000多万，这将是个天文数字。

事实也确实如此，在实验阶段，把每张照片的数据量减小10倍，即每张照片的天体坐标量为50万，用Python写出代码实现上述方法计算出11张照片的聚类结果需要的时间是6.5天。按计算复杂度来算，500多万的数据量，计算量是50万数据量的100倍，即需要耗时650天，这肯定是一个无法接受的数字。

同样的50万数据量，被装入了某分布式数据库后用SQL实现，动用了100颗CPU后，跑了3.8小时完成了计算。看起来比Python快了很多倍，但Python的6.5天是单线程，细算下来SQL的单核性能还不如Python（3.8小时*100>6.5天）。巨大的资源消耗已经难以容忍，而且计算500多万规模时也要380小时。

解决方案

我们来考虑哪里可以优化以减少计算量。

基础照片中的天体坐标是必须循环的，这样才能保证每个天体都被用来聚类了，其他照片中的天体坐标不用每次都遍历，只要找到基础天体坐标附近的坐标就可以了。这类查找任务很适合二分法，它可以大量减少计算量。

具体过程是这样的：先对每张照片中的天体坐标排序，用二分法找到某个阈值范围内的天体坐标，这样就排除了大多数天体，这是粗筛过程；用基础天体与粗筛结果中的天体计算距离，找出符合条件的结果，这是细筛过程。

来看看粗筛加细筛方法的计算量，10张照片每张排序一次，计算量是500万*log(500万)10；二分法粗筛，计算量是500万log(500万)10；细筛过程，计算量不确定，但根据经验，粗筛后的结果通常不超过1万个，粗筛的计算量中log(500万)还要再加1万；这样算下来，总的计算量大概是500万log(500万)10+500万(log(500万)+1万)*10，相较于原来的方法，计算量只有原来的五百分之一。

技术选型

方法有了，还要选择程序工具，之前实现时使用Python，不可否认Python很强大，有天文学计算的现成框架，比如计算距离的方法，只要调用现成的类库就可以轻松算出来。

但Python也有着非常严重的弊端：

1. Python中没有原生的二分法方法，第三方的类库还要结合Pandas来完成，期间需要做一些数据转换，这些都必然会带来一些不必要的开销。

2. Python的多线程是假多线程，实际上不支持多线程并行，这也是Python不能成为本任务工具的重要原因。

关系数据库的SQL也无法高效完成。这个聚类运算本质上是个非等值连接，数据库对于等值连接还能采用HASH JOIN等优化方案来减少计算量，但对于非等值连接就只能采用遍历方案了；SQL也无法在语句中实现上面设计的复杂过程，不能识别距离的单调性而主动排序并采用二分法；再加上本来做这类数学类计算的能力不足（距离计算涉及三角函数）；所以发生了前面实验阶段中SQL的单核性能还跑不过Python的现象。

Java等高级语言虽然可以实现二分法，也可以很好的并行，但代码写起来冗长，开发效率过低，会严重影响程序的可维护性。

那么，还能用什么工具来完成这个任务呢？

集算器SPL是个很好的选择，它内置了很多高性能算法（如二分法），也支持多线程并行，代码写起来也简单明了，还提供了友好的可视化调试机制，能有效提高开发效率，以及降低维护成本。

实际效果

相较于Python来说，SPL为本任务提速2000倍，二分法能够提速500倍，多线程并行又提速4倍（笔者笔记本电脑的CPU只有4核），总计提速2000倍，使用SPL完成500多万目标规模的聚类任务只需要数个小时。

SPL的代码不仅性能优异，而且也并不复杂，关键计算代码只要23行。

B10格的fork是多线程并行函数，允许分段执行上述算法。

B6格的sort@m()函数是并行排序方法，数据量大时可以提高效率，数据有序是二分法使用的前提条件。

C17格的select@b(…)函数是二分查找方法，也是本任务提速的关键。

后记

性能优化的问题依赖于高性能的算法，只有把计算量降下来才能有效提高运行效率，而高性能算法需要在工作中慢慢积累，感兴趣的同学可以来这里学习常用的性能优化算法：性能优化课程。

高性能算法需要高效的编程工具来实现，之前已经说过，Python、SQL、java等语言都有其弊端，要么无法并行，要么实现困难、维护困难。SPL有足够的算法底层支持且允许高并发，代码能做到很简洁，还提供了友好的可视化调试机制，能有效提高开发效率，以及降低维护成本。

SPL资料

• SPL下载
• SPL源代码

送书活动

为了回馈广大粉丝们长期以来的厚爱，本博主决定给小伙伴们送出2类共4本图书。在此特别感谢 机械工业出版社有限公司的赞助，所有图书均包邮包邮包邮！！！！

第一类【Python语言从入门到精通】：共3本

Python语言从入门到精通循序渐进地讲解了使用Python语言的核心知识，并通过具体实例的实现过程讲解了各知识点的使用方法和流程。不仅适合零基础者，也适用于希望进一步提高自己Python开发水平的读者

第二类【微服务设计：企业架构转型之道】：共1本

《微服务设计：企业架构转型之道》根据企业数字化转型的客观需要，引入了企业架构的规划和实施的概念，具体讲述了如何规划企业架构，包括业务架构、应用架构、数据架构和技术架构；企业架构的服务化过程，以及其完成后的企业服务架构的微服务过程；企业微服务架构的治理和管理。

如何免费获得该书呢？

所有获奖用户先三连：评论，点赞，收藏。

1. 评论获得

1. 本文优质评论两条，且该评论点赞数是最高的，分别获得《Python语言从入门到精通》一本！

例如2条评论点赞数并列第一的，以评论的时间谁早！

2. 抽奖获得

2. 私聊博主，博主会随机抽取两个小伙伴，获得《Python语言从入门到精通》一本或《微服务设计：企业架构转型之道》一本。

统计截止时间：2022/09/28 18:00:00

文章来源: feige.blog.csdn.net，作者：码农飞哥，版权归原作者所有，如需转载，请联系作者。

原文链接：feige.blog.csdn.net/article/details/127016838