行将开播：4月29日，民生银行郭庆谈商业银行金融科技赋能的探求与实际

在人工智能浪潮之下，全民学习 Python 已成为必然趋向。Python 作为一门胶水言语，以复杂的语法、良好的交互性、移植性等优势遭到诸多开发者的喜欢，但要和老牌的 C++ 相较而言，谁运转的速度更快一些？置信很多开发者会毫无疑问地选择了 C++，而本文作者也证明了这一点。

最近我在开发一个名为 Bard（https://github.com/antlarr/bard）的命令行运用，它是个管理本地音乐库的音乐管理器。Bard 会依据歌曲生成声响指纹（应用 acoustid：https://acoustid.org/）并将一切歌曲的元数据保存到 sqlite 数据库中。这样你就可以很容易地停止查询，并找到重复的歌曲，即使歌曲的标签不正确也能找到。本文笔者分享了查找重复歌曲的算法，并运用 Python 和 C++ 对该算法停止两次优化，探求如何使这个算法比原来快 8000 倍。

1.算法

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

但在比较歌曲时还需求思索更多状况。有时两首歌扫尾的空白时间长短不同，因此指纹的比特不会完美地对齐，直接比较会不婚配，但将其中一个指纹移动一位能够就能婚配。

因此，要比较两首歌，我们不只要比较它们的指纹，还要模拟添加或增加扫尾空白的长度，看看它们的婚配水平是上升还是下降。目前 Bard 会将数组向一个方向移动 100 位，再向相反方向移动 100 位，也就是说每首歌都要停止 200 次指纹比较。

因此，假设要比较一个曲库中的一切歌曲以查找重复，我们需求比较 ID1 和 2，然后将 ID 3 与 ID 1 和 ID 2 比较，普通来说每首歌都要与前面的一切歌曲停止比较。这样，假设曲库里有 100 首歌曲，那么需求比较 1000 * 1001/ 2 = 500500 首歌曲（也就是说，要比较 100100000 次指纹）。

2.最后的 Python 完成

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

def count_bits_set(i):

i = i – ((i >> 1) & 0x55555555)

i = (i & 0x33333333) + ((i >> 2) & 0x33333333)

return (((i + (i >> 4) & 0xF0F0F0F) * 0x1010101) & 0xffffffff) >> 24

我们把这个完成的速度作为参考值，称之为一倍速。

3.第一个改良

第一个改良，我尝试将比特计数算法改成较快的gmpy.popcount（#mpz-functions），还参加了终止阈值来改良算法。这个新的算法会在超过终止阈值时判别为不能够婚配，从而中止比较。例如，假设在计算的进程中发现，即使剩余的比特全部婚配，两首歌的婚配水平也不能够超过 55%，那就直接前往“不同歌曲”（但还是要与其他歌曲比较，以防万一）。

这个改良使得比较速度简直提高到了两倍速。

4.运用 C++

此时，我以为这段代码没办法很容易扩展到更大的曲库上，因此我以为 Bard 需求更好的完成。修正内存很慢，而 C/C++ 可以完成更细粒度的底层优化，但我并不想用 C++ 重写整个运用，因此我采用了Boost.Python（https://www.boost.org/doc/libs/1_65_0/libs/python/doc/html/index.html），仅把这个算法用 C++ 完成了，并从 Python 运用中调用这个算法。不得不说，我发如今 Python 中集成 C++ 办法十分容易，因此我十分引荐运用 Boost.Python。

在新的 C++ 完成中，我运用了 STL 的 vector 来保存指纹，并且事前参加了最大的偏移量，这样在算法中就无需修正向量中的元素，只需模拟位移即可。我还运用 STL 的 map，以歌曲的 ID 为索引来保存一切指纹。最后，我还添加了一个重要的优化措施，经过 gcc 的__builtin_popcount（https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-_005f_005fbuiltin_005fpopcount），应用 CPU 指令来计算字符。

这个算法最大的益处就是比较进程不会修正或复制任何指纹，这使得速度添加了 126.47 倍。此时我末尾计算另一个度量：每秒钟比较的歌曲数（别忘了每比较一对歌曲就要做 200 次指纹比较）。这个算法的平均速度是 580 首/秒。或许换句话说，要想比较 1000 首歌，需求破费大约 14 分 22 秒（留意原来的 Python 完成大约需求一天 6 小时 16 分 57 秒）。

5.初次并行算法尝试

(责任编辑：admin)