C++加Python比C加Python还牛逼!让你的Python应…

2018-07-27 06:28:31来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

算法

进群:125240963  即可获取数十套PDF哦!

要判断两首歌曲是否相似,需要比较它们的声音指纹。听上去很容易(实际上的确不难),但并不是初看上去那么直接。acoustid 计算出的声音指纹并不是一个数字,而是一个数字的数组,更准确地说,是一系列字符的数组。因此不能比较数字本身,而要比较数字中的字符。如果所有字符完全一致,则可以认为两首歌曲是同一个。如果 99% 的字符一致,则可以认为有 99% 的可能性两者相同,两者的差异可能是由编码问题(如一首歌用 192kbits/s 编码成 mp3,另一首用的是 128kbits/s)等造成的。

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

最初的 Python 实现

Bard 是用 Python 写的,所以第一版实现采用了 Python 的列表以整数数组的方式保存指纹。每次迭代过程中需要移位时,我会在其中一个指纹数组前面加个 0,然后迭代整个数组,依次比较每个元素。比较的方法是对两个元素执行异或操作,然后用一个算法来数出整数中的比特个数:

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

第一个改进

第一个改进,我尝试将比特计数算法改成较快的gmpy.popcount(http://gmpy2.readthedocs.io/en/latest/mpz.html#mpz-functions),还加入了终止阈值来改进算法。这个新的算法会在超过终止阈值时判断为不可能匹配,从而停止比较。例如,如果在计算的过程中发现,即使剩余的比特全部匹配,两首歌的匹配程度也不可能超过 55%,那就直接返回“不同歌曲”(但还是要与其他歌曲比较,以防万一)。这个改进使得比较速度几乎提高到了两倍速。

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

第二次并行尝试

我需要找个我能用的并行版本的 for_each。幸运的是,最终我发现 gcc 包含了 C++ 标准库中部分算法的实验性并行实现,其中包含了__gnu_parallel::for_each(https://gcc.gnu.org/onlinedocs/libstdc++/manual/parallel_mode_using.html,文档页面上还有更多的并行算法)。只需要链接 openmp 库就可以了。

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

很显然我却忘记了的重要改进

在检查 Bard 的编译器时,我发现我没有使用优化速度的编译器开关!于是我给编译器加上了 -Ofast-march=native -mtune=native -funroll-loops,就这么简单。猜猜发生了什么……

速度提高到了 6552 倍,约 30050 首歌曲/秒,1000 首歌曲只需 16 秒。

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

最终的优化

我还没做的一个非常明显的优化就是把 map 换成 vector,这样就无需每次调用 for_each 之前进行转换了。而且,vector 能提前分配空间,由于我知道在整个算法结束时 vector 的最终大小,因此我修改了代码,以便事先分配空间。

这个修改给了我最后一次提速,速度提高到 7998 倍,36680 首歌曲/秒,完全处理 1000 首歌曲的曲库仅需 13 秒。

C++加Python比C加Python还牛逼!让你的Python应用提速 8000倍!

 

凡是都要会灵活应用撒。这样的效果就快多了不是吗!

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:django入门三(视图)

下一篇:面试题之--实现取余