作者sean791121 (尚恩)
看板MATLAB
標題[討論] 請問有沒有比較快的寫法
時間Thu May 28 23:31:39 2015
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://webptt.com/m.aspx?n=bbs/MATLAB/M.1432827101.A.BA5.html
1F：→ sean791121: 因為迴圈內的每一圈都處理不同大小的空間，所以不行用 05/28 23:34
2F：→ sean791121: parfor 求比較快的方法 05/28 23:34
3F：推 sunev: sub2ind 05/28 23:59
4F：→ sean791121: 意思是用兩層for然後用sub2ind找位置嗎? 05/29 00:33
5F：→ sean791121: 其實用一層loop也可以，我加速了快兩倍，可是和預期 05/29 00:45
6F：→ sean791121: 的速度還是有落差，請問還有更快的寫法嗎? 05/29 00:45
7F：→ celestialgod: 我測試了一下，A,B如果都是兩萬乘兩萬的矩陣 05/29 00:56
8F：→ celestialgod: idx是長度10000，也只要2.345秒而已 05/29 00:57
9F：→ celestialgod: 這樣還是不夠快嗎？ 05/29 00:57
10F：→ sean791121: cpu是i5 跑出來大概1.X秒 05/29 01:26
11F：→ sean791121: 看文獻 Pentium 4 跑這段code再加上很多有的沒的 1秒 05/29 01:27
12F：→ sean791121: 我猜文獻應該有用更快的方法 or我的演算法太爛了 05/29 01:28
13F：→ sean791121: 對不起，忘記說明A和B都是sparse的 05/29 01:29
14F：→ sean791121: A(sub_index)=B(sub_index)是不是比較慢呢? 05/29 01:30
15F：→ sean791121: 因為matlab建議使用sparse(I,J,V,m,m) 05/29 01:31
16F：→ celestialgod: 文獻也是用MATLAB? 而且你矩陣大小多少? 05/29 02:16
19F：→ celestialgod: 我稍微試了一下，迴圈應該是MATLAB中最快的了 05/29 03:41
20F：→ celestialgod: 要再加速就要靠MEX了，還不能複製input才做得到 05/29 03:41
21F：→ celestialgod: 環境: MATLAB 2015a, windows 7 64bit, 05/29 03:42
23F：→ sean791121: 文獻也是用MATLAB，我的矩陣5000乘5000 05/29 05:18
24F：→ sean791121: 謝謝你提供方法，我會研究一下的 05/29 05:18
25F：→ sean791121: 想請問您 為什麼matlab的速度會與C差這麼多? 05/29 05:22
26F：→ sean791121: 因為MATLAB都會先判斷一些性質(矩陣、函數)的關係嗎? 05/29 05:23
27F：→ sean791121: 對不起，我跑你的C++檔會出現bug，code沒問題呀XD 05/29 06:08
28F：推 sunev: celestialgod太厲害了，可以想出這麼多寫法。 05/29 09:21
29F：→ sunev: 我實際用c大給的code稍稍profile了一下。發現實際做出idx的 05/29 09:22
30F：→ sunev: 方法(2~4)，其實在真正assign的那行A(idx)=B(idx)並沒有比 05/29 09:23
31F：→ sunev: 迴圈省下太多時間，所以算出idx的時間成本反而蓋過了直接 05/29 09:24
32F：→ sunev: assign的效益。 05/29 09:24
33F：→ sunev: 另外method 3中，應為triu(....,1)，下面的 2:end可以去掉 05/29 09:26
34F：→ celestialgod: 我昨天沒有想到一個可以直接產生idx的方法 05/29 09:27
35F：→ sunev: 如果把(idx3>0)改成triu(true(mat_size,mat_size),1)會快 05/29 09:27
36F：→ sunev: 一點，但仍比不上迴圈。 05/29 09:28
37F：推 celestialgod: 我等等試試看，感謝 05/29 09:29
38F：→ sunev: 另外我的經驗是，sparse在這種大量不規則assign的情況下 05/29 09:30
39F：→ celestialgod: 原PO，我的c code，自己跑是沒問題的，我編譯的指令 05/29 09:31
40F：→ celestialgod: 也在上面，你可能需要再研究一下。 05/29 09:31
41F：→ sunev: 速度是慢了點，因為要一直改non-zero element很麻煩。 05/29 09:32
42F：→ sunev: 所以官方才會建議用sparse一起解決。 05/29 09:33
43F：→ celestialgod: 這裡sparse matrix不會比較快 05/29 09:34
44F：→ celestialgod: 原po, c的速度會快本來就不意外..... 05/29 09:36
45F：推 celestialgod: 這題只要想到怎樣產生(1, 1, 2, 1, 2, 3, 1, 2, 3, 05/29 09:38
46F：→ celestialgod: 4, 1, 2, 3, 4, 5,... )的方法就會很快(不用矩陣 05/29 09:38
47F：→ celestialgod: 取上三角... 這個會用到太多記憶體還是會慢) 05/29 09:38
48F：推 sunev: 沒錯，不過true只要1byte，所以還好。XD 05/29 09:55
49F：推 sunev: 剛發現不錯的寫法 05/29 10:43
50F：→ sunev: A(idx,idx)=tril(B(idx,idx),-1)+triu(A(idx,idx)); 05/29 10:43
51F：→ sunev: 但如果idx很大，B(idx,idx)這個sparse有可能會吃很多記憶體 05/29 10:44
52F：→ celestialgod: 我測試的結果是assign反而比較久 05/29 10:57
53F：→ celestialgod: 我算idx的時間大概0.5秒，assign要花2.1秒 05/29 10:57
54F：→ celestialgod: 我也試著用gpuArray去算idx，但是還是卡在assign 05/29 10:59
55F：推 sunev: 你矩陣是5000*5000，idx長度是10000嗎？ 05/29 11:04
56F：→ sunev: 這樣你矩陣還會是 "sparse" 嗎? 05/29 11:04
57F：→ celestialgod: 5000*5000, 10000也只占0.04%..不過我用15000*15000 05/29 11:08
58F：→ celestialgod: 我錯了XD，idx長度10000，要改將近5000萬個值 05/29 11:10
59F：推 sunev: 我是問原作者啦。不確定他想加速到什麼程度，所以想確定 05/29 11:12
60F：→ sunev: 問題的size 05/29 11:12
61F：→ celestialgod: 剛剛有發現XDD 05/29 11:13
62F：→ celestialgod: 如果assign的成本比算idx的成本還貴，這問題無解 05/29 11:14
63F：→ celestialgod: 只能用C去更動矩陣的值才會快上不少 05/29 11:14
64F：推 sunev: 再回樓上，我的意思不是assign比算idx久，而是一行assign 05/29 11:15
65F：→ sunev: 比迴圈assign省不了多少時間，而算idx會超過省下的時間。 05/29 11:16
66F：→ celestialgod: 喔喔，我懂了 05/29 11:17
67F：→ celestialgod: 一行assign省下的時間沒有比算idx的時間短 05/29 11:18
68F：→ sean791121: 對不起，K大概4800，謝謝兩位的幫忙 05/29 12:54