※ 引述《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