MATLAB R2017b新函數介紹之mink, maxk

先上個禪師遇到理科生的故事引題:

青年：為什麼在一次比賽中冠軍和亞軍都付出了同樣的努力，而人們只記住了冠軍呢？

禪師：我給你講個人生哲學吧！

青年：好！

禪師：世界第一高峰是哪個？

青年：珠穆朗瑪峰！

禪師：世界第二高峰呢？

青年：喬戈里峰！

禪師：第三高峰呢？

青年：干城章嘉峰！

禪師：第四高峰？

青年：洛子峰

禪師：第五？

青年：馬卡魯峰！

禪師：……

青年：哎，說起來，你剛才說想給我講的人生哲學是什麼啊？

禪師：……

這個故事告訴我們: 不僅需要知道第一名, 還需要知道前K名, 要不然, 容易被禪師忽悠:)

求第一名的MATLAB函數，我想幾乎所有人都知道是max或min, 但是求前K名呢?

之前版本好像沒有最直接的方法, 最naive的方法是先降序排序, 再取前K個, 比如下面代碼:

vec = randn(1e6, 1);nvec_sorted = sort(vec, descend);ntop5 = vec_sorted(1:5);n

想想就知道, 好浪費資源啊! 我只想得到5個值, 卻把一百萬個數字排了個序！

N個數字排序的時間複雜度為O(N*log(N)).

實際上， 求top K的時間複雜度只要O(N*log(K)).

找出N個數中最小的k個數問題(複雜度O(N*logk)) - Jingle Guo - 博客園

但是我懶得自己寫， 當整個程序的性能瓶頸不在這一步時， 就用上面代碼湊合了， 當這一步是整個程序的性能瓶頸時， 我在MATLAB central file exchange裡面找到了我需要的函數：

Min/Max selection - File Exchange - MATLAB Central

測試性能（為了和file exchange的函數比較， 這裡求最小的k個，而不是最大的k個）：

vec = randn(1e6, 1);n%% 最naive的方法， 先排序ntic;nvec_sorted = sort(vec);ntop5_sorted = vec_sorted(1:5);nt1= toc;n%% 使用file exchange裡面搜到的代碼， 編譯成mex文件ntic;ntop5_minkmex = minkmex(vec, 5);nt2 = toc;n%% 使用R2017b的新函數minkntic;ntop5_mink = mink(vec, 5);nt3 = toc;n%% 對比性能， 並確認結果是否一致ndisp(t1 / t2) %file exchange代碼速度是排序法的4.5倍ndisp(t1 / t3) %mink是排序法的15.3倍ndisp(t2 / t3) %mink是file exchange代碼的3.4倍nassert(all(top5_sorted == sort(top5_minkmex))) %確認是一致的nassert(all(top5_sorted == top5_mink)) % 確認是一致的n

1 mink是最快的， 一百萬數據測試發現， 速度是排序法的15.3倍， 是file exchange函數minkmex的3.4倍。

2 minkmex有一個缺點， 得到top k不保證是排過序， 大概率是亂序的，它只保證這k個值時最小的k個， 但不保證是順序輸出！

3 minkmex還有一個缺點，它依賴於編譯器， 比如你用visual studio 2015編譯後， 給別人使用， 對方電腦上只安裝了visual studio 2010，運行有可能會崩！

綜上， 強烈推薦使用新函數mink， maxk。