標籤：

用python處理一個1G左右的數據集，運行速度非常慢，怎樣優化？

01-01

研究方向為推薦系統，最近用python在delicious數據集上實現一種簡單的基於標籤的推薦演算法，然後計算recall和precision。在幾M的小型數據集上運行時間還可以（十幾秒左右），但是在較大（幾百兆，1g）的數據集上運行非常慢，我等了4個小時還沒有算出結果。請問一下在不對演算法進行優化的基礎上，採用什麼樣的方法可以提升程序的運行速度？

實驗環境：Ubuntu 13.10, 4G, intel i3-2310M, python 2.75.

這裡面有兩個原因吧：

首先， 是演算法的問題。複雜度不一樣的演算法， 在數據規模大的情況下， 運行速度差別會越來越大。你沒有描述具體演算法， 所以我們也不知道能怎樣提升演算法。不過根據我的經驗， 機器學習演算法慢很正常， 因為計算量非常大。很多步驟如果你參照現成一些方法的話， 基本就已經是已知的在演算法複雜度和代碼複雜度上做了非常好的平衡而且演算法複雜度已經很不錯的方法。 要想再提高的話要麼就要投入大量時間做學術研究，或者大量時間編寫複雜的代碼。

解決方法是你要自己分析你的程序， 確定每一個部分的複雜度大概是多少，找出演算法的瓶頸， 然後花精力優化瓶頸上的演算法。

第二個問題是眾所周知的 python 本身速度慢的問題，python作為完全建立在解釋器上的支持OO支持FP且類型dynamic的語言， 能使用的機器指令優化非常有限，一般認為比native程序慢10-100倍是正常的。

解決方法：一個快速的 work-around 是使用 JIT 編譯器例如 PyPy， 速度可以提高大概幾倍到10倍左右。 另外，使用一個 profile 技術找到運行時間的瓶頸， 可以把瓶頸部分用 C 重寫，即可幾乎達到native速度。

最後， 在這個多核和雲時代， 你應該考慮多核甚至多機器了。 Python 本身又 GIL， 一個進程內不支持計算意義上的多線程， 把你的程序各個部件好好劃分一下， 分解成多進程。 然後用一台機器的多個CPU同時跑， 或者仍給多台機器跑。

用delicious數據集即使是最naive的count（u，t）*（t，i）順加inverse frequency都很慢吧。。。畢竟tag 和item都太多了。。。慢是正常的。。。

題主，讓我來給你一些實用建議吧!

  1. 考慮拿C或C++重寫.
  2. 考慮並行搞，找個hadoop集群，寫成mapreduce程序跑 放在hadoop上跑，更多數據都不怕.
  3. 考慮升級機器，多搞點內存，然後東西盡量放在內存里搞.
  4. 考慮程序優化.
  • 你得看看你程序慢在什麼地方，可以按照以下步驟：
    1. 首先，確信你真的需要把全部數據過一遍，如果可以通過一些糙快猛方式過濾掉無用數據，這樣最好了. （比如有些明顯無用的東西可以直接通過grep過濾掉，grep這種程序寫的一般比你寫的python程序要快好多好多好多好多）
    2. top一下，看CPU跑滿了嗎？
    3. 單線程單進程實現？你能不能搞成多進程的？然後top看每個核都跑滿了嗎？
    4. 沒跑滿的話，那你你要努力充分利用你的CPU，要讓CPU跑滿！看看程序，沒跑滿是因為IO嗎？是的話IO能搞成非同步的么？或IO次數太多？能不能減少IO次數？甚至只搞一次IO，比如你那1G的東西，能不能一次全搞到內存里，然後所有東西在內存里處理（這樣的話貌似寫成C的更方便一點）
    5. 如果每個核心都跑滿了，那就看看你的計算都花在什麼地方，可以用hotshot等工具測一把. 可以粗略比較一下在 1/16 數據、1/8數據、1/4數據、1/2數據的情況下，hotshot的結果，看你的函數花的時間是怎麼漲的.找出花時間最多的一個或幾個東西（所謂瓶頸），有針對性的優化，可以事半功倍.
    6. 找到問題所在之後，尋求解決方案. 如果是python帶的數據結構不不合適，能不能用numpy之類的東西解決，能不能用一些資料庫解決（比如需要多個進程一起往一個大字典里寫，可以考慮全往一個redis里寫）.能不能有的地方用cython包裝一個C實現.
    7. 如果是演算法不夠好，能不能優化演算法. （這就說來話長了）
  • 試試一些奇怪的東西，比如PyPy.

    • 單機情況下，總結起來，就是：首先減少輸入數據，然後不要浪費機器資源，要讓所有CPU核心跑滿（多進程 減少/不等待IO），內存只要還夠用的話，就可勁用！然後找程序最慢的地方，針對其做各種優化.如果有多機，弄到hadoop里搞，數據再多也不怕不怕啦！

    首先你應該確認一下你的演算法複雜度，比如數據翻倍後運行時間增加多少？

    python 數組遍歷特別慢，可以結合 cython加速

    1. 增量學習而非全量學習。

    2.少用集成演算法或複雜度高的演算法，當然可能會一定程度上降低模型準確性。

    3.降維，萬年不破得真理。

    4.抽樣，適當的抽樣方法不會降低準確性，但會明顯提升效率。

    5.用其他底層語言改寫，例如c，Python 的優勢不是計算效率高，而是開發效率高。

    6.演算法並行改造。當然不是所有的演算法都適合改造。

    7.硬體提升，包括cpu，內存等，具體你需要先分析下硬體瓶頸。

    8.演算法耗時具體看是哪個流程，例如是交叉檢驗還是預處理，具體需要改造耗時流程。這個是非常有效的。

    numpy是比較慢，矩陣運算量大可以試一下Matlab。另外可以profile一下你的程序，看看哪個環節運算時間比較長。

    1.嘗試用C寫

    2.嘗試多線程

    3.嘗試隊列化任務，建立多個緩衝池

    在你可見的演算法層面上優化是一個方面，其實Python對大文件讀取也有瓶頸。做了上面這些事情（可能除了第一個外），再去想辦法研究你自己核心的演算法複雜度問題。

    一般來說最省力且最容易大幅度提升的反而是優化演算法/使用profile優化實現。

    其次是使用pypy/cython。

    再其次使用numpy。

    最後是改用其他語言。

    profile + cython

    不要用python的循環，寫成矩陣形式調用科學計算庫，例如numpy，或者直接用c實現關鍵演算法

    C

    -------------------------------

    如果你當前演算法時間複雜度是o(n^2)，也即是說

    1M數據 ---&> 10秒

    1G數據 ---&> 數據增加1000倍 ---&> 處理時間增加 1000 * 1000 = 1,000,000 倍 ---&> 10百萬秒 == 2777.7小時 == 115.7天

    如果你能夠把演算法時間複雜度降到o(nlogn)，則

    1M數據 ---&> 10秒

    1G數據 ---&> 數據增加1000倍 ---&> 處理時間增加 1000×log(1000) = 3000 倍 ---&> 30000秒 ---&> 8.333小時

    如果你能夠把演算法時間複雜度降到o(n)，則

    1M數據 ---&> 10秒

    1G數據 ---&> 數據增加1000倍 ---&> 處理時間增加 1000倍 ---&> 10000秒 ---&>2.8小時

    在演算法時間複雜度確定的前提下，除非你能夠把1M數據的解析時間降低一到兩個數量級（降到1秒～0.1秒），否則對1G數據的處理時間就必然是以小時為單位的，甚至是天，或者年。。。

    ----------------------------------------------

    用C代替Python來跑核心演算法大概能提高演算法效率1到1.5個數量級（10～50倍）

    再一次強調：如果你的演算法時間複雜度是o(n^2)或者更糟，那神仙也救不了你。。。

    i3-2310M？實驗環境居然是在入門級筆記本上，你們實驗室（公司）到底是有多困難？

    之前參加JD的比賽，遇見了這個問題。

    先說一下電腦配置: Win10, i73630QM, 28G, 1TB 5400.

    賽題是通過對3月內用戶對商品的操作行為數據，預測未來5天用戶的購買情況。最大的數據來源於3個月的行為操作數據，大概4G左右的數據量。我們是用python2.7進行操作的，全程都是python完成。

    一開始沒有注意這個問題，用python寫循環去處理數據，統計相應的特徵指標。需要循環4000萬次，而且循環越來越慢，內存佔用越來越大，當時循環一次需要1周時間，有點崩潰。後來減少了python循環的使用，多使用了python自帶的函數進行處理，速讀就快起來了。

    總結一下：

    1.數據量大的時候，不要循環操作。python提供了很多處理數據的包，pandas, numpy這些包中的函數速讀快而且內存佔用少。merge，groupby, count, 這些函數要用起來啊。

    2.可以預先在資料庫里對數據進行處理，像我們遇到的這個數據量，在mysql里運用SQL進行特徵提取，效率比python要快。

    處理完數據後，運用python跑模型的時候，選好模型python的效率還是可以接受的。希望對於只會用python的數據分析同學有幫助啊。

    可以考慮使用一些分散式的框架或者平台，mahout, spark, http://easyrequest.io

    4g內存，裝個linux，別裝x，開機內存佔用幾十兆。然後把tmp掛載到tmpfs上，數據放上面，佔用1g。速度絕對快

    話說4個小時根本就ok啦。除非是做產品或者有stupid的演算法問題，感覺一天能跑完的程序根本沒有優化的必要。Deep Learning的演算法跑一個禮拜也在接受範圍, anyway, 優化主要是1）演算法, 2) 內存, 3) 多核。

    是的，一定記得使用multi-process！

    正好看到這個 numfocus/python-benchmarks 路 GitHub

    假定數據 1M ---&> 1G 數據量提升1024倍

    O(n) ---&> (1024*n)/n = 1024 倍

    O(logn) ---&> (log(1024*n))/(logn) = (10/logn+1) 倍

    O(nlogn) ---&> (1024*n)(log(1024*n)) / (nlogn) = 1024*(10/logn+1) 倍

    O(n^2) ---&> (1024*n)^2 / n^2 = 1024^2 倍

    O(n^3) ---&> (1024*n)^3 / n^3 = 1024^3 倍

    O(n^k) ---&> (1024*n)^k / n^k = 1024^k 倍

    另外，由於空間複雜度也上去了，

    可能編出來的代碼對cache和分支預測不友好，後果你懂的。

    推薦閱讀：

    ※數據挖掘與機器學習是什麼關係？
    ※機器學習中隨機梯度演算法要用到負黎曼梯度，如何理解黎曼流形，黎曼梯度？
    ※具體哪裡會用到泛函分析和測度論？
    ※如何評價丘成桐團隊關於GAN的論文?
    ※為什麼非科班這麼難進數據挖掘這一行？

    TAG:Python | 數據挖掘 | 機器學習 | 推薦系統 | 計算機科學 |