当前位置:网站首页>A method that can make large data clustering 2000 times faster
A method that can make large data clustering 2000 times faster
2022-08-10 13:33:00 【Sichuan rookie】
一、问题描述
国家天文台有个聚类任务:共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也有着非常严重的弊端:
- Python中没有原生的二分法方法,第三方的类库还要结合Pandas来完成,期间需要做一些数据转换,这些都必然会带来一些不必要的开销.
- Python的多线程是假多线程,实际上不支持多线程并行,这也是Python不能成为本任务工具的重要原因.
关系数据库的SQL也无法高效完成.这个聚类运算本质上是个非等值连接,数据库对于等值连接还能采用HASH JOIN等优化方案来减少计算量,但对于非等值连接就只能采用遍历方案了;SQL也无法在语句中实现上面设计的复杂过程,不能识别距离的单调性而主动排序并采用二分法;再加上本来做这类数学类计算的能力不足(距离计算涉及三角函数);所以发生了前面实验阶段中SQL的单核性能还跑不过Python的现象.
Java等高级语言虽然可以实现二分法,也可以很好的并行,但代码写起来冗长,开发效率过低,会严重影响程序的可维护性.
那么,还能用什么工具来完成这个任务呢?集算器SPL是个很好的选择,它内置了很多高性能算法(如二分法),也支持多线程并行,代码写起来也简单明了,还提供了友好的可视化调试机制,能有效提高开发效率,以及降低维护成本.
五、实际效果
相较于Python来说,SPL为本任务提速2000倍,二分法能够提速500倍,多线程并行又提速4倍(笔者笔记本电脑的CPU只有4核),总计提速2000倍,使用SPL完成500多万目标规模的聚类任务只需要数个小时.
SPL的代码不仅性能优异,而且也并不复杂,关键计算代码只要23行.
A | B | C | D | E | |
---|---|---|---|---|---|
1 | =RThd | /距离阈值 | |||
2 | =NJob=4 | /并行线程数 | |||
3 | =file("BasePhoto.csv")[email protected]() | ||||
4 | [email protected](OtherPhotos) | /其他照片路径 | |||
5 | for A4 | =file(A4)[email protected]() | /其他照片 | ||
6 | [email protected](OnOrbitDec) | /排序 | |||
7 | =B6.min(DEC) | ||||
8 | =delta_ra=F(B7,RThd) | /根据DEC算RA阈值 | |||
9 | =FK(B5,NJob) | /数据索引分段 | |||
10 | fork B9 | =B5(B10) | /照片片段 | ||
11 | for A3 | =C11.OnOrbitDec | /DEC | ||
12 | =D11-delta_rad | /DEC下限 | |||
13 | =D11+delta_rad | /DEC上限 | |||
14 | =C11.RA | /RA | |||
15 | =D14-delta_ra | /RA下限 | |||
16 | =D14+delta_ra | /RA上限 | |||
17 | [email protected]([email protected](OnOrbitDec,D12:D13)) | /二分查找DEC | |||
18 | =D17.select(RA>=D10&&RA<=D11) | /查找RA | |||
19 | =D36.select(Dis(~,C11)<=A7) | /细筛 | |||
20 | if D19!=[] | /合并结果 | |||
21 | =FC(C11,D37) | ||||
22 | /汇总结果 | ||||
23 | =file(OFile)[email protected](B22) | /写出结果 |
B10格的fork是多线程并行函数,允许分段执行上述算法.B6格的[email protected]()函数是并行排序方法,数据量大时可以提高效率,数据有序是二分法使用的前提条件.C17格的[email protected](…)函数是二分查找方法,也是本任务提速的关键.
在这里插入图片描述
六、后记
性能优化的问题依赖于高性能的算法,只有把计算量降下来才能有效提高运行效率,而高性能算法需要在工作中慢慢积累,感兴趣的同学可以来这里学习常用的性能优化算法:性能优化算法.
高性能算法需要高效的编程工具来实现,之前已经说过,Python、SQL、java等语言都有其弊端,要么无法并行,要么实现困难、维护困难.SPL有足够的算法底层支持且允许高并发,代码能做到很简洁,还提供了友好的可视化调试机制,能有效提高开发效率,以及降低维护成本.
## 七、SPL资料
高性能算法需要高效的编程工具来实现,之前已经说过,Python、SQL、java等语言都有其弊端,要么无法并行,要么实现困难、维护困难.SPL有足够的算法底层支持且允许高并发,代码能做到很简洁,还提供了友好的可视化调试机制,能有效提高开发效率,以及降低维护成本.
边栏推荐
猜你喜欢
Wirshark common operations and tcp three-way handshake process example analysis
MySQL面试题整理
发送post请求前台无法获取数据
SenseTime self-developed robotic arm, the first product is an AI chess-playing robot: Guo Jingjing is also invited as an endorsement
商汤自研机械臂,首款产品是AI下棋机器人:还请郭晶晶作代言
M²BEV: Multi-Camera Joint 3D Detection and Segmentation with Unified Bird’s-Eye View Representation
表中存在多个索引问题? - 聚集索引,回表,覆盖索引
ABAP file operations involved in the Chinese character set of problems and solutions for trying to read
网络安全——XSS之被我们忽视的Cookie
高数_证明_曲率公式
随机推荐
想问下大佬们 ,cdc oracle初始化一张300万的表任务运行着后面就这个错 怎么解决哇
AWS 安全基础知识
C# 当前上下文中不存在InitializeComponent()
BEVDet4D: Exploit Temporal Cues in Multi-camera 3D Object Detection 论文笔记
Detailed explanation of es6-promise object
矩阵键盘&基于51(UcosII)计算器小项目
网络安全——XSS之被我们忽视的Cookie
2022 Recruitment Notice for Academician Zhao Guoping Group of Shenzhen Institute of Advanced Technology, Chinese Academy of Sciences
OTA自动化测试解决方案---整体方案介绍
Open Office XML 格式里如何描述多段具有不同字体设置的段落
Makefile missing separator. Stop.怎么解决「建议收藏」
教育Codeforces轮41(额定Div。2)大肠Tufurama
Requirements for the construction of Loudi stem cell preparation laboratory
Jenkins修改默认主目录
系统的安全和应用(不会点安全的东西你怎么睡得着?)
LeetCode·每日一题·640.求解方程·模拟构造
kubernetes介绍
Error: Rule can only have one resource source (provided resource and test + include + exclude)
LeetCode medium topic search of two-dimensional matrix
高数_证明_弧微分公式