算法
私信小編007即可獲取數十套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 秒。
凡是都要會靈活應用撒。這樣的效果就快多了不是嗎！
閱讀更多 繁華落盡and曲終人散 的文章
