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