Re: [討論] 如何更有效率？

[mp19990920 (郝渴連)]

※ 引述《DIDIMIN ( )》之銘言：
: 已知有一行向量 X = [a, b, c, d]'
: 想要生成
: Y = [ a, 0, 0, 0 ]
:     [ b, a, 0, 0 ]
:     [ c, b, a, 0 ]
:     [ d, c, b, a ]  4x4 矩陣
: 目前的寫法
: tic
: X = [1:n]';
: i = 1; Y = zeros(numel(X),numel(X));
: while i <= numel(X)
:     Y(:,i) = [zeros(i-1,1);X(1:numel(X)+1-i,1)];
:     i = i+1;
: end
: toc
: 當 n 為 1000 時，計算時間為 0.008490 秒
: 當 n 為 5000 時，計算時間為 0.147806 秒
: 當 n 為 10000 時，計算時間為 0.462627 秒
: 當 n 為 20000 時，計算時間為 1.777377 秒
: 電腦配備：i7-2600 3.4GHz、RAM 8G、Windows 8、Matlab R2013a
: 請問各位大大有沒有更有效率的寫法？

法一：去除你原本code中多餘的運算

(1)numel多餘
(2)i=i+1多餘(但影響極小)
(3)沒必要重設整個column
X = [1:n]';
Y = eye(n);
for i = 2:n
   Y(i:n, i) = i:n;
end

p.s. 在我的電腦中n=1000跑1000次平均時間
原本: 0.06610 sec
加速: 0.02339 sec
你的電腦可真快呢!!!


法二：用mex來改寫

難度高，debug麻煩，不太建議


法三：重新檢視你的演算法

產生這個矩陣很沒意義，
且用n^2的儲存空間來表示n個資訊非常的不經濟

--
 哀愁猶如雪花梢然飄落,
   白雪厚積,
     終究成了孤獨的小結晶,
       誰能融化我冰凍已久的孤寂?

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 111.67.52.211
→ Feis:我可以請教一下為什麼內建的 toeplitz() 慢很多 Q_Q
function t = toeplitz(c,r)

[step 0] 初始化
r = r(:);                                   % force column structure
p = length(r);
m = length(c);

[step 1] 產生出待放元素表
x = [r(p:-1:2) ; c(:)];                     % build vector of user data

[step 2] 產生出拿取待放元素時要用的idx
xclass = class(x);
cidx = (zeros(xclass):m-1)';
ridx = p:-1:ones(xclass);
t = cidx(:,ones(p,1)) + ridx(ones(m,1),:);  % Toeplitz subscripts

[step 3] 把元素從從元素表中拿出來
t(:) = x(t);                                % actual data

step 2 中
(1) 用 x(:, [1 1 1 ... l]) 的方式來複製 vector 比較慢
(2) 記憶體需產生兩個大小跟結果相同的矩陣後再做加總的動作
記憶體需要做2次額外的配置與釋放，而且還要做 O(N^2) 的運算

step 3 可用我上面的方式來避掉
※ 編輯: mp19990920      來自: 111.67.52.211        (09/07 18:41)

若你對效能有疑慮的話，
可以使用 matlab 內建的工具 "Profiler"，
快速按鈕就放在 help 的左邊，
超超超好用的!!!
※ 編輯: mp19990920      來自: 111.67.52.211        (09/07 18:45)
※ 編輯: mp19990920      來自: 111.67.52.211        (09/07 18:47)
推 DIDIMIN:謝謝你
推 Feis:謝謝! 這蠻有趣的. 另外請教一下, Matlab 內建的比較慢是有
→ Feis:什麼語法特性還是說他內建的比較泛用? 謝謝 : )
→ Feis:抱歉, 我不是很懂 Matlab 的哲學. 我會自己去查一下
推 bridge23:= [1:n]';