Re: [問題] 產生稀疏矩陣及稀疏矩陣相乘?
※ 引述《LPH66 (台大我回來了!)》之銘言:
: ※ 引述《kians (臨兵鬥者皆陣列在前)》之銘言:
: : 3.兩個大量稀疏矩陣相乘的寫法?
: : 會寫矩陣相乘的程式後,接下來就是要處理稀疏矩陣了;因為稀疏矩陣有許多零值的關係
: : 所以一般情況下應該有一些方法可以來縮減資料量,以達成大量稀疏矩陣的相乘
: : 一般矩陣的話,兩個一萬X一萬矩陣相乘電腦應該就爆了吧orz
: 回這點
: (1) 不管是不是稀疏矩陣 要用三層for迴圈跑的話其實效率應該差不多
: 頂多稀疏矩陣多一個把其中一個從row major順序改成column major順序
: 這會稍微加速一下就是
: 不過稀疏矩陣有它的乘法的寫法 會比普通的三層for稍快
: (也就是充份利用稀疏矩陣的特性: 0一堆)
: (2) (應該是個很重要的一點)
: 稀疏矩陣乘稀疏矩陣不一定是個稀疏矩陣...
: 極端一點的例子例如
: [1 0 0 0 0] [1 1 1 1 1] [1 1 1 1 1]
: [1 0 0 0 0] [0 0 0 0 0] [1 1 1 1 1]
: [1 0 0 0 0] x [0 0 0 0 0] = [1 1 1 1 1]
: [1 0 0 0 0] [0 0 0 0 0] [1 1 1 1 1]
: [1 0 0 0 0] [0 0 0 0 0] [1 1 1 1 1]
: 前兩個很稀疏吧? 可第三個卻一點也不稀疏...
: 所以最後你還是得要一個一萬乘一萬的普通矩陣來存答案
: (當然其實是看你的兩個稀疏矩陣的0的分佈)
: 比較建議看有沒有辦法邊乘邊輸出結果
我來補一刀...
兩個一萬乘一萬的矩陣相乘,那需要三個一萬乘一萬的矩陣
我假設精準度不用太高,float 就夠了
4 * 3 * 10K * 10K / 1K / 1K = 1200 (MB)
hmmm? 為甚麼電腦會爆炸呢?
(前面都有人記憶體開到 8G 了... \囧/)
另外....
用 Sparse Matrix 來紀錄一個 float 的 element 需要
int, int, float → 12 (Byte)
也就是說,如果你原本的 Matrix 中是 0 的 element 沒有超過 67%
那反而佔得空間會比較大(也就是 LPH66 的第二點)
事實上,如果把時間的成本算下去的話
非 0 的 element 至少也要在 15% 以下才算划算
(這個純粹個人喜好啦... 沒有實質依據 lol)
耶~賺 p 幣完畢,而且還有扯到 Java 喔 [挺] [毆飛]
----
最後,給原 po 一個小小警告:
不是寫的比較長就會長得不像作業文
更不是在 o 版主(突然)變身好人回 po 你
你就可以大辣辣的在這裡找人幫你寫
(而且才開價 500p... 拜託... NT 500 在 CodeJob 版可能都會被噓)
--
侃侃長論鮮窒礙 首頁:http://www.psmonkey.idv.tw
眾目睽睽無心顫 Blog:http://ps-think.blogspot.com
煢居少聊常人事
殺頭容易告白難 歡迎參觀 Java 版(@ptt.cc)精華區 \囧/
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.193.251
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 4 之 4 篇):