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

算法

进群：125240963  即可获取数十套PDF哦！

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

最初的 Python 实现

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

第一个改进

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

第二次并行尝试

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

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

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

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

最终的优化

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

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

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

标签：

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