[討論] 請問有沒有比較快的寫法

[sean791121 (尚恩)]

indx是一個index的向量，A和B是矩陣，我想把B中的某些元素放到A內
舉例來說:

for i = 2:10000

A(idx(i),idx(1:i-1))=B(idx(i),idx(1:i-1))

end
請問有比較快的寫法嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.184.40.155
※ 文章網址: https://www.ptt.cc/bbs/MATLAB/M.1432827101.A.BA5.html
→ sean791121: 因為迴圈內的每一圈都處理不同大小的空間，所以不行用
→ sean791121: parfor  求比較快的方法
推 sunev: sub2ind
→ sean791121: 意思是用兩層for然後用sub2ind找位置嗎?
→ sean791121: 其實用一層loop也可以，我加速了快兩倍，可是和預期
→ sean791121: 的速度還是有落差，請問還有更快的寫法嗎?
→ celestialgod: 我測試了一下，A,B如果都是兩萬乘兩萬的矩陣
→ celestialgod: idx是長度10000，也只要2.345秒而已
→ celestialgod: 這樣還是不夠快嗎？
→ sean791121: cpu是i5  跑出來大概1.X秒
→ sean791121: 看文獻 Pentium 4  跑這段code再加上很多有的沒的 1秒
→ sean791121: 我猜文獻應該有用更快的方法 or我的演算法太爛了
→ sean791121: 對不起，忘記說明A和B都是sparse的
→ sean791121: A(sub_index)=B(sub_index)是不是比較慢呢?
→ sean791121: 因為matlab建議使用sparse(I,J,V,m,m)
→ celestialgod: 文獻也是用MATLAB? 而且你矩陣大小多少?
→ celestialgod: http://pastebin.com/D2jJSkRk MATLAB檔案
→ celestialgod: http://pastebin.com/JaUSthpX C++檔案
→ celestialgod: 我稍微試了一下，迴圈應該是MATLAB中最快的了
→ celestialgod: 要再加速就要靠MEX了，還不能複製input才做得到
→ celestialgod: 環境: MATLAB 2015a, windows 7 64bit,
→ celestialgod: [email protected]
→ sean791121: 文獻也是用MATLAB，我的矩陣5000乘5000
→ sean791121: 謝謝你提供方法，我會研究一下的
→ sean791121: 想請問您  為什麼matlab的速度會與C差這麼多?
→ sean791121: 因為MATLAB都會先判斷一些性質(矩陣、函數)的關係嗎?
→ sean791121: 對不起，我跑你的C++檔會出現bug，code沒問題呀XD
推 sunev: celestialgod太厲害了，可以想出這麼多寫法。
→ sunev: 我實際用c大給的code稍稍profile了一下。發現實際做出idx的
→ sunev: 方法(2~4)，其實在真正assign的那行A(idx)=B(idx)並沒有比
→ sunev: 迴圈省下太多時間，所以算出idx的時間成本反而蓋過了直接
→ sunev: assign的效益。
→ sunev: 另外method 3中，應為triu(....,1)，下面的 2:end可以去掉
→ celestialgod: 我昨天沒有想到一個可以直接產生idx的方法
→ sunev: 如果把(idx3>0)改成triu(true(mat_size,mat_size),1)會快
→ sunev: 一點，但仍比不上迴圈。
推 celestialgod: 我等等試試看，感謝
→ sunev: 另外我的經驗是，sparse在這種大量不規則assign的情況下
→ celestialgod: 原PO，我的c code，自己跑是沒問題的，我編譯的指令
→ celestialgod: 也在上面，你可能需要再研究一下。
→ sunev: 速度是慢了點，因為要一直改non-zero element很麻煩。
→ sunev: 所以官方才會建議用sparse一起解決。
→ celestialgod: 這裡sparse matrix不會比較快
→ celestialgod: 原po, c的速度會快本來就不意外.....
推 celestialgod: 這題只要想到怎樣產生(1, 1, 2, 1, 2, 3, 1, 2, 3,
→ celestialgod:  4, 1, 2, 3, 4, 5,... )的方法就會很快(不用矩陣
→ celestialgod: 取上三角... 這個會用到太多記憶體還是會慢)
推 sunev: 沒錯，不過true只要1byte，所以還好。XD
推 sunev: 剛發現不錯的寫法
→ sunev: A(idx,idx)=tril(B(idx,idx),-1)+triu(A(idx,idx));
→ sunev: 但如果idx很大，B(idx,idx)這個sparse有可能會吃很多記憶體
→ celestialgod: 我測試的結果是assign反而比較久
→ celestialgod: 我算idx的時間大概0.5秒，assign要花2.1秒
→ celestialgod: 我也試著用gpuArray去算idx，但是還是卡在assign
推 sunev: 你矩陣是5000*5000，idx長度是10000嗎？
→ sunev: 這樣你矩陣還會是 "sparse" 嗎?
→ celestialgod: 5000*5000, 10000也只占0.04%..不過我用15000*15000
→ celestialgod: 我錯了XD，idx長度10000，要改將近5000萬個值
推 sunev: 我是問原作者啦。不確定他想加速到什麼程度，所以想確定
→ sunev: 問題的size
→ celestialgod: 剛剛有發現XDD
→ celestialgod: 如果assign的成本比算idx的成本還貴，這問題無解
→ celestialgod: 只能用C去更動矩陣的值才會快上不少
推 sunev: 再回樓上，我的意思不是assign比算idx久，而是一行assign
→ sunev: 比迴圈assign省不了多少時間，而算idx會超過省下的時間。
→ celestialgod: 喔喔，我懂了
→ celestialgod: 一行assign省下的時間沒有比算idx的時間短
→ sean791121: 對不起，K大概4800，謝謝兩位的幫忙