almost 4 years ago

matlab 的強項在於矩陣運算
所以通常有個觀念是能用矩陣的思維取代(對其他語言來說)直觀的思維(e.g. loop)就盡量用

另外一個加速的方法是有很多內建的函式都很好用
但是因為太好用了(做的事情很多),在量很大的時候就有空間可以加速

有人可能會說需要速度快就別用 matlab,或者改用 C 寫 mex 取代大迴圈
的確,若要追求速度的極限那乾脆別用 matlab
但有時候實作時間有限,改個寫法就可以加速也是有它的價值在
另外一個附加價值就是能理解 matlab function 的行為(e.g. 做哪些事情是很花時間的)

以下是我遇過的兩個例子

  • 測試環境:16 core (Intel Xeon CPU E5530 2.40GHz)

unique

有些時候內建的 function 會被用到很多次,像 unique 就是很常用的 function

sort+diff 可以當做一部分 unique 的功能使用
ref: faster way to achieve unique() in matlab if assumed 1d pre-sorted vector?

vector = [4 1 3 5 2 4];
vector = sort(vector)
vector =
     1     2     3     4     4     5
uniqueVector = vector([true;diff(vector(:))>0])
uniqueVector =
     1     2     3     4     5

但是什麼情況下 sort+diff 會比 unique 快呢?

來比較一下 uniquesort+diff 所花費的時間

unique.m
for numElement = [100,10000,100000,1000000]
    tic;
    for i=1:1000
        vector = randi(100,1,numElement);
        uniqueVector = unique(vector);
    end
    toc;
end
result
Elapsed time is 0.103313 seconds.
Elapsed time is 0.987119 seconds.
Elapsed time is 6.199297 seconds.
Elapsed time is 60.371398 seconds.
sort+diff.m
for numElement = [100,10000,100000,1000000]
    tic;
    for i=1:1000
        vector = randi(100,1,numElement);
        vector = sort(vector);
        uniqueVector = vector([true;diff(vector(:))>0]);
    end
    toc;
end
result
Elapsed time is 0.031016 seconds.
Elapsed time is 0.877409 seconds.
Elapsed time is 5.852163 seconds.
Elapsed time is 61.032015 seconds.

結論

  • 如參考連結,給定已經排序好的 vector 只要使用 diff 就可以取得 unique vector,非常快速 (實際上原因是大部分時間都花在 sort,這裡就不貼出測試資料了)
  • size 很小的 vector (<100)使用 sort+diff 也會比 unique 來得快
  • 如果是 size 很大的未排序 vector,用 sort+diff 就跟 unique 相差無幾了

計算出現頻率

use unique + histc to get the relative frequency.
ref: Determining the number of occurrences of each unique element in a vector

除了 unique 之外,還有一個常見的需求是計算某個值出現了幾次
一個是直接用內建的 histc

example_histc.m
A=[1,2,3,1,2,4,2,1]; % an example vector

unqA=unique(A)
unqA =
     1     2     3     4

To get the number of occurances,

countElA=histc(A,unqA) % get the count of elements

countElA =
     3     3     1     1
relFreq=countElA/numel(A)
relFreq = 
    0.3750    0.3750    0.1250    0.1250
which is the relative frequency of the unique elements.
This will work for both integers and floating points.

但還有另一個方法是先排序之後,利用 unique 得到排序過的 index
再藉由 diff 得到每一個元素的個數
直覺上應該是會比 histc 快一些
詳細方法就直接放在原始碼裡面不多做說明,以下是測試:

histc.m
for numElement = [100,10000,100000,1000000]
    tic;
    for i=1:1000
        A = randi(100,1,numElement);
        unqA = unique(A);
        countElA = histc(A,unqA);
    end
    toc;
end
result
Elapsed time is 0.147729 seconds.
Elapsed time is 1.547588 seconds.
Elapsed time is 12.222510 seconds.
Elapsed time is 119.633619 seconds.
pre-sort+diff.m
for numElement = [100,10000,100000,1000000]
    tic;
    for i=1:1000
        A = randi(100,1,numElement);
        sortA = sort(A);
        dupA = [sortA, sortA(size(sortA,2))+1];
        [unqA, idx] = unique(dupA, 'first');
        countElA = diff([idx,idx(size(idx,2))+1]);
        countElA = countElA(1:end-1);
    end
    toc;
end
result
Elapsed time is 0.194604 seconds.
Elapsed time is 1.169871 seconds.
Elapsed time is 7.556745 seconds.
Elapsed time is 72.559933 seconds.

結果不意外的是後者比較快

雖然 pre-sort+diff 方法乍看之下好像會做兩次排序
但其實將 sorted vector 丟給 unique 不會再做額外排序,因此整體來說還是只做一次
diff 做的事情比 histc 少,所以比較快是合理的。

← 在學校裡寫程式 vs. 在企業裡寫程式 Commit binary 檔案到 Git 之前請三思 →
 
comments powered by Disqus