標籤：

在機器學習的演算法中， 矩陣運算的效率總是優於for循環嗎？

01-07

我們知道， 矩陣乘法的效率((O(n2), O(n3))區間內)， 優於for循環計算向量乘法(O(n3))， 那麼， 是不是任何矩陣的運算， 都優於for循環呢？

也就是， 我們是否有必要把演算法中的所有for循環， 都改寫成矩陣運算？

如果是， 為什麼？

如果不是， 什麼時候應該使用for循環， 什麼時候應該使用矩陣呢？

自己用任何語言實現矩陣、向量乘法都比不過BLAS庫。BLAS1、BLAS2、BLAS3都是優化過的，效率遠比自己寫for循環高。所以不管用什麼編程語言，都不要自己寫矩陣、向量乘法。

我解釋一下：

BLAS1是向量操作

BLAS2是向量乘矩陣

BLAS3是矩陣乘矩陣

如果你不信邪，你自己用for寫兩個矩陣的乘法，跟BLAS3（矩陣x矩陣的實現）比一下，速度能差很多倍。雖然兩種實現的CPU計算量一樣，但是訪問內存、cache的代價差別巨大。不要說你自己寫for循環了，即使你用BLAS2（矩陣x向量的實現）來做矩陣乘法，還是會比BLAS3慢得多。

總結一下，如果算兩個矩陣的乘法，速度是這樣的：

BLAS3 &> 一重循環BLAS2（矩陣x向量） &> 兩重循環BLAS1（向量x向量） &> 自己寫三重循環。

看到好多回答都在寫各種包，還有扯SIMD的。SIMD是硬體給提供的介面。矩陣乘法優化是從演算法來解決的。

一般矩陣相乘優化所做的就是loop tiling。循環平鋪。就是減少矩陣行列載入內存的次數。一個n x n 的矩陣，乘以一個n個元素的向量，從內存讀取數據時，是將向量和每個矩陣的一行行相乘的，這樣矩陣每一行都被載入cache一次。

如果將n x n的矩陣乘以 n x m的矩陣，前一矩陣的每一行都會被用到m次。如果直接三個for循環套起來，兩個矩陣的數據很多都會被重複載入cache很多次。

這個時候如果你將兩個矩陣都分成零碎的矩陣，比如n x n變成四個 n/2 x n/2的矩陣，那麼內存載入cache的重複次數會改變。

根據不同cpu的cache的不同，矩陣分片的大小都是需要變化的。有個公式，回頭再補上。先睡了。

SIMD，vectorization, SSE 4.2這些東西如果能自己寫，當然是有可能比blas要快的。

事實上，對於那些非常非常小規模（比如不到10的，如果你手寫了一些SIMD的intrinsic的這個限度大致可以放寬到100），簡單手寫一個for還是有希望比BLAS裡面給出來的快的...

因為BLAS庫一般給出來的是C介面，抽象的overhead會稍微有些大，特別小規模時候overhead可能會佔到耗時中不可忽略的一部分。

稍微認真答一下..

如果你的for循環是進行一系列很簡單的操作，有希望轉化成矩陣或者array形式的運算，比如矩陣乘矩陣，比如矩陣或者向量的reduce等，同時你的硬體又是比較常規的硬體，例如x86，ARM，GPU等，那使用類似BLAS的工具是最穩妥的選擇，這類工具比如OpenBlas，Eigen，cuBlas，clBlas等，它們各有所長，挑一個最合適的就好，通常能給你提供不錯的性能表現。但由於他們可能要適配較多不同的硬體，同時也並非所有的代碼都是手工精細調節過的，因此它們的性能也並不是高到了不可超越的地步。

如果你不滿足於它們提供的性能，又或者你的硬體不是很常規導致它們無法支持或者性能稀爛，又或者你的for循環裡面的操作不是那麼容易轉化成矩陣形式，那可能你需要自己來手寫一份代碼，為此你可能需要：

了解你的硬體，明白你的循環如何和它的存儲器系統進行交互。具體來說就是其他答主提到的loop tilling

了解你的硬體，明白它有哪些特殊的指令可以提高你的運算吞吐量。現在比較常見的就是上面提到的SIMD

如果你對性能還不是非常滿意，想進一步提高它的性能，那麼你可能需要：

了解你的硬體，明白它是如何執行這些運算指令的。具體來說就是流水線，超標量等等，你可能需要手寫一些彙編代碼來最大限度地利用硬體上的執行單元，最大限度地減少流水線停頓等。

想最大限度地提高密集運算的性能，最後必然是一個軟硬體深度結合設計的過程，因此最重要的可能就是深入了解你的硬體了。

BLAS對dense數據優化的很好，但是對於sparse數據，像大規模CTR預測這樣的任務，我們需要根據任務自己優化矩陣運算。

」踩一下最高票的。他的觀點有待商榷。

BLAS的實現不一定就是最好的。BLAS也是人刷出來的，難道就不能刷出再高的。鄙人(團隊)剛好在某個特定條件下某種設備上做出了比主流BLAS效果高許多的效果。

大部分的主流BLAS的底層實現都不會只有一種方法，它總會實現好幾種方法來應對不同的任務。而這些方法，有些是基於for，有些不是(這裡的for顯然不是指c等裡面的for)。而一些加速特別明顯的往往都不是用for來實現。

不過最高票的回答的的確確說明了一個問題。如果你沒打算花太多時間心思甚至可能失敗的結果的話，直接用BLAS的就好了，你要做的只是選哪個BLAS更合適而已。而自己簡單寫些for循環就想超過BLAS，那也太隨便了吧。

首先要特定場景特定分析，BLAS在不同的設備和任務上表現也不同的。

比如在小矩陣上，n很小的時候，O(n^3)和O(n^http://2.xxx)沒啥子區別，但是實現上，大部分的O(n^3)都很好實現，並且能很好地利用simd，noen這些，所以效率顯然快。而O(n^http://2.xxx)這些，顯然要從其他地方給出代價才能在時間複雜度上佔便宜，這種往往運用在dl的大矩陣運算上。

同時，不同的設備，比如arm的cpu，和pc端的cpu在實現上顯然也要不同。尤其是mali的gpu，你直接拿pc端的BLAS來用，哪怕真讓你用上了，那個效率大部分慘不忍睹，還不如自己在gpu上寫個最簡單的for的kernel函數來得快(很大矩陣的時候又不同啦，好煩)。

所以，樓主，如果你只是簡單問個問題，問完就算，那麼就敷衍地回答你，大部分都BLAS都比for快(廢話)。如果你想花大時間來做優化的話，那麼必須找相關知識或者書籍補充一下先。

如果該計算會成為你的工程的性能瓶頸，就一定不要手寫for，我之前做了一個gps的壓縮，需要求三階的逆矩陣，我直接用matlab展開公式生成java代碼，效率還可以，再說計算量也不大。

如果用blas，一定需要用jcc或者jni之類的，部署就會畢竟麻煩，至少不如純java簡單。

並不是。

矩陣運算也是用for循環實現的，不過通常效率會更高。

以Level2 y=alpha Ax + eta y 為例簡單說明下為什麼BLAS的實現會高效：

1）如果 alpha = 0 ，那麼 y = eta y , 完全不用計算 alpha A x

2）如果 alpha = 1 ，那麼 y= Ax + eta y ， alpha * 不算了

3）如果 eta = 0 ，那麼 y=alpha Ax ，eta y 不用計算了

4）如果 eta = 1 ，那麼 y=alpha Ax + y ，eta * 不算了

同時BLAS的實現，也會考慮使用硬體的指令集（比如ARM NEON）優化運算，緩存的利用等，這些也都是在for循環內完成：

for (i = 0; i+4 &<= m; i+=4) { // 在這裡 SIMD 優化 a += 4; y += 4; } for (k = 0; i &< m; ++i, ++k) { // 處理邊界 }

事實上，你也完全可以自己實現一些BLAS函數比如常用的 gemm gemv(a matrix-vector product using a general matrix)，通常情況下直接使用BLAS的函數介面就好了，可以做些簡單的封裝。

如果對BLAS的計算速度不滿意，也可在BLAS實現的基礎上進行優化，比如移動端深度神經網路優化。

感覺題主問的很模糊...矩陣乘法最原始的實現都是用for 循環的..比如c++的LAPACK...其他的語言比如python, matlab, R都是用c/c++寫的，其中矩陣的運算也都是調用了底層的這些包。這些包已經把矩陣運算優化到極致了，你自己寫的肯定不行啊

矩陣運算底層使用了處理器的SIMD技術，即單指令多數據，一次可以計算多個元素相乘（具體細節沒有了解），而for循環一次只能計算一次乘法。

是有一些理論上 O(n^http://2.xxx) 的矩陣乘法演算法，但是這些演算法常數很大，而且在目前主流硬體上並不太友好，對緩存利用太差，只有極大尺寸的矩陣可能才能帶來性能優勢，而且可能有數值穩定性的問題，所以現在的 BLAS 一般也都是用 O(n^3) 的演算法實現的，只不過優化程度很高，會利用到向量指令集，有些涉及到廠商自己的優化比方說 MKL 在 intel CPU 上之類的，不是自己手寫的三重循可比的。

https://software.intel.com/en-us/articles/optimize-for-intel-avx-using-intel-math-kernel-librarys-basic-linear-algebra-subprograms-blas-with-dgemm-routine

https://pdfs.semanticscholar.org/a5d5/170a216969bfc3ed63b9cfce9297ff6a9790.pdf

不過剛查了下，16 年也有人聲稱自己實現了在小規模矩陣（1000 x 1000）上實際性能更優的 Strassen 演算法：

http://dl.acm.org/citation.cfm?id=3014983

不過不管怎麼說，自己寫三重 for 循環肯定是最慢的。

親，其實你的問題是有個嚴重的誤區，O()這種時間複雜度是在同環境下才可行，比如說如果只是在單線程、僅用c，並且編程代碼規範的情況下，那麼O(n)肯定快於O(n^2)的，同等的時間複雜度也是一樣。但是不同環境下就沒有可比性了，單從語言上說Python的for和C的for執行效率是不一樣的，也就是說代碼的執行效率和演算法的時間複雜度是兩個維度的概念。更不要提多線程並行計算的應用了，你僅僅寫個for，只是單線程再跑，而openblas這種加速是所有線程都在跑，還有內存、cache、數據對齊、單指令多數據等等各個軟硬體方面的優化，都不是你單寫for可以比擬的。

另外如果你只有百十來次的計算，其實用上訴的優化方法都看不出效果，因為差別太小了，但是如果上大規模計算，那麼你的優化就算只有一點點，也會被指數級的放大。現在的machine learning，尤其是DL方向，計算量都是以billion計，為了對付這種級別的運算，才會引發各個方面的優化。具體的就你自己學習吧。

將矩陣運算放到向量化的角度，來比較向量化和for循環。

從Andrew Ng最近在Coursera上開的深度學習課程中，專門有一節講述了Vectorization的重要性。Ng的建議是除非必須，否則最好Vectorization。從Ng的描述中，強調了numpy的並行優化。從完成一個目標的總時間來看，將問題向量化的思考時間通常要長於for循環，除非你很擅長向量化。從代碼來看，向量化的代碼更加簡潔，當然在易讀性上可能存在爭議，部分原因是python的broadcasting等存在，容易造成不符合直覺的理解。

個人觀點：在時間允許的前提下，儘可能向量化。既可以寫出更數學的代碼，又可以發揮依賴庫的底層優化(這個難道不是我們真正關心的地方嗎?並行，內存和Cache等)。當然可以寫完for循環後，以一種可能的方式顯式並行(比如OpenMP等)，但是孰優孰劣，結論顯然。

一個字，試。

不過，矩陣運算的確是經過加速的，自己寫的for循環，效率上還是差很多。

例如，opencv中的圖像處理就是用的tbb，ipp加速

其實 矩陣運算也有for 只不過優化的太徹底了

matlab和python的核心運算庫也是用C/C++實現的，除非你針對硬體作優化，比如使用cpu的simd、sse之類的加速器，否則不會更快，而且廠家很可能已經用了cpu加速器。

用matlab的心得:要想程序跑的快，不到萬不得已，別寫for循環，別寫for循環，別寫for循環，重要的事情說三遍。

是的，你自己寫for循環效率肯定比矩陣運算的相關庫要低，因此能夠向量化的一定要向量化。

題主需要意識到的是，複雜度並不等價於運行時間，即使是一樣的複雜度，但運行時間也可能天差地別。矩陣運行都是有底層優化的，簡單的來說很多操作都是並行，不像for循環是典型的串列。一個不完全一樣但原理基本類似的例子是，你用有gpu support的tensorflow和沒有gpu support的版本跑同一個網路，你會發現差距特別大。

總之，不僅僅是矩陣運算的問題，在很多問題中程序員都不要試圖比編譯器或者成熟的第三方庫作者更聰明。自己造輪子在實踐中一般來說是費時費力不討好，當然作為練習倒是一種不錯的方式。

可以的情況下不要自己寫

我曾經因為矩陣維度過大，不能用matlab等自帶的矩陣乘法，就自己用java各種根據矩陣特性寫了個演算法意義下最優的一個，然後跑了52小時計算出來了……

學過演算法的應該知道矩陣分塊的計算複雜度會下降.

數學上，no

CPU對計算的實現，yes

推薦閱讀：

※應該如何理解No Free Lunch Theorems for Optimization?
※Adaboost可不可以使用其他的損失函數？
※怎麼從通俗意義上理解邏輯回歸的損失函數？
※Metropolis Hasting演算法如何推導出Gibbs Sampling？
※模式識別與智能系統專業研究生找工作好找么？

TAG:機器學習 | 深度學習DeepLearning | 數值計算 |