小男孩‘自慰网亚洲一区二区,亚洲一级在线播放毛片,亚洲中文字幕av每天更新,黄aⅴ永久免费无码,91成人午夜在线精品,色网站免费在线观看,亚洲欧洲wwwww在线观看

搜索
分享

Python處理海量數(shù)據(jù)的實(shí)戰(zhàn)研究

 我的菜譜123 2013-01-24

Python處理海量數(shù)據(jù)的實(shí)戰(zhàn)研究  

2012-07-25 02:01:12|  分類： python轉(zhuǎn)載 |字號 訂閱


最近看了July的一些關(guān)于Java處理海量數(shù)據(jù)的問題研究，深有感觸，鏈接：http://blog.csdn.net/v_july_v/article/details/6685962

感謝July ^_^

他用的是Java的Hash Map等方法做了處理，講解的非常深刻入骨


我也一時興起，想拿Python試試刀，看看Python對于海量數(shù)據(jù)的處理能力如何。無奈在百度和Google輸入“Python 海量數(shù)據(jù)”都無果。可能是國內(nèi)使用python的不多，用python處理海量數(shù)據(jù)的就更少了。不過這澆滅不了我的欲望，哈哈


打算拿July的其中一個問題來試驗(yàn)一下：

[plain] view plaincopy

  1. <strong>海量日志數(shù)據(jù)，提取出某日訪問百度次數(shù)最多的那個IP。</strong>  

July給出的解決方案：

[plain] view plaincopy

  1. 方案1：首先是這一天，并且是訪問百度的日志中的IP取出來，逐個寫入到一個大文件中。注意到IP是32位的，最多有2^32個IP。同樣可以采用映射的方法，比如模1000，把整個大文件映射為1000個小文件，再找出每個小文中出現(xiàn)頻率最大的IP（可以采用hash_map進(jìn)行頻率統(tǒng)計，然后再找出頻率最大的幾個）及相應(yīng)的頻率。然后再在這1000個最大的IP中，找出那個頻率最大的IP，即為所求。  
下手吧！


（一）生成數(shù)據(jù)

我首先構(gòu)造1億個IP，這些IP前兩段都是“10.197”，后兩段為0-255的隨機(jī)數(shù)

把這1億個IP存入一個文本文件中

Python代碼如下：

[python] view plaincopy

  1. __author__ = "Wally Yu (dayu.ebay@gmail.com)"  
  2. __date__ = "$Date: 2012/04/09 $"  
  3.   
  4. def generateRandom(rangeFrom, rangeTo):  
  5.     import random  
  6.     return random.randint(rangeFrom,rangeTo)  
  7.   
  8. def generageMassiveIPAddr(fileLocation,numberOfLines):  
  9.     IP = []  
  10.     file_handler = open(fileLocation, 'a+')  
  11.     for i in range(numberOfLines):  
  12.         IP.append('10.197.' + str(generateRandom(0,255))+'.'+ str(generateRandom(0,255)) + '\n')  
  13.   
  14.     file_handler.writelines(IP)  
  15.     file_handler.close()  
  16.   
  17. if __name__ == '__main__':  
  18.     from time import ctime  
  19.     print ctime()  
  20.     for i in range(10):  
  21.         print '  ' + str(i) + ": " + ctime()  
  22.         generageMassiveIPAddr('d:\\massiveIP.txt', 10000000)  
  23.     print ctime()  

這里插一下，我的軟件硬件環(huán)境：

硬件：

- ThinkPad T420（CPU: i7， 內(nèi)存16G）

軟件：

-OS： WinXP32位 （只認(rèn)出3.6G內(nèi)存）

- Python：2.7


從Python的print日志中基本可以看出，生成一千萬條IP地址大概需要1分鐘，生成1億條記錄需要10分鐘

占據(jù)硬盤空間：1.4G

日志：

[python] view plaincopy

  1. Mon Apr 09 16:52:28 2012  
  2.   0: Mon Apr 09 16:52:28 2012  
  3.   1: Mon Apr 09 16:53:28 2012  
  4.   2: Mon Apr 09 16:54:29 2012  
  5.   3: Mon Apr 09 16:55:30 2012  
  6.   4: Mon Apr 09 16:56:32 2012  
  7.   5: Mon Apr 09 16:57:33 2012  
  8.   6: Mon Apr 09 16:58:36 2012  
  9.   7: Mon Apr 09 16:59:36 2012  
  10.   8: Mon Apr 09 17:00:36 2012  
  11.   9: Mon Apr 09 17:01:35 2012  
  12. Mon Apr 09 17:02:36 2012  

（二）處理思路

假設(shè)現(xiàn)在可用內(nèi)存僅為128M，而每行IP經(jīng)計算需要14Byte

因?yàn)閿?shù)據(jù)太大，把1億條數(shù)據(jù)載入內(nèi)存，再做排序會導(dǎo)致內(nèi)存溢出。July的思想：“以大化小，分而治之”非常合適，我轉(zhuǎn)化后的操作思路：

1. 每行IP需要14B空間，那么128M內(nèi)存最多可以處理 128M / 14B = 9142857個IP

把每36571429個IP拆成一個小文件保存起來，每個小文件的大小小于等于128M，共將生成11個文件

2. 對每個小文件用Hash Table處理，Python有自己非常高效的Hash Table：Dictionary！

具體處理如下：

1）. 構(gòu)建名為“Result”的Dictionary，“key”為IP地址，“value”為該IP地址出現(xiàn)的次數(shù)，用來記錄11個文件每一個的最多出現(xiàn)的IP

2）. 構(gòu)建名為“IP”的Dictionary，“key”為IP地址，“value”為該IP地址出現(xiàn)的次數(shù)，用來記錄每一個小文件的所有IP地址

3）. 讀入每一條IP地址到“IP” Dictionary，如果該IP地址出現(xiàn)過，把相應(yīng)的value的值加1；如果該IP地址沒有出現(xiàn)過，則key=IP地址，value=1

4）. 對“IP” Dictionary進(jìn)行內(nèi)排序，返回最大的IP地址（如果有若干個最大值是一樣的，就都返回）

5）. 將返回值存入“Result” Dictionary

6）. 對“Result”進(jìn)行內(nèi)排序，返回最大的IP地址（如果有若干個最大值是一樣的，就都返回）


（三）實(shí)現(xiàn)

1）拆分成小文件

代碼如下：

[python] view plaincopy

  1. __author__ = "Wally Yu (dayu.ebay@gmail.com)"  
  2. __date__ = "$Date: 2012/04/10 $"  
  3.   
  4. from time import ctime  
  5. def splitFile(fileLocation, targetFoler):  
  6.     file_handler = open(fileLocation, 'r')  
  7.     block_size = 9142857  
  8.     line = file_handler.readline()  
  9.     temp = []  
  10.     countFile = 1  
  11.     while line:  
  12.         for i in range(block_size):  
  13.             if i == (block_size-1):  
  14.                 # write block to small files  
  15.                 file_writer = open(targetFoler + "\\file_"+str(countFile)+".txt", 'a+')  
  16.                 file_writer.writelines(temp)  
  17.                 file_writer.close()  
  18.                 temp = []  
  19.                 print "  file " + str(countFile) + " generated at: " + str(ctime())  
  20.                 countFile = countFile + 1  
  21.             else:  
  22.                 temp.append(file_handler.readline())  
  23.       
  24.     file_handler.close()  
  25.   
  26. if __name__ == '__main__':  
  27.     print "Start At: " + str(ctime())  
  28.     splitFile("d:\\massiveIP.txt", "d:\\massiveData")  

運(yùn)行后的log如下：

[plain] view plaincopy

  1. Start At: Tue Apr 10 10:56:25 2012  
  2.   file 1 generated at: Tue Apr 10 10:56:37 2012  
  3.   file 2 generated at: Tue Apr 10 10:56:47 2012  
  4.   file 3 generated at: Tue Apr 10 10:57:00 2012  
  5.   file 4 generated at: Tue Apr 10 10:57:14 2012  
  6.   file 5 generated at: Tue Apr 10 10:57:26 2012  
  7.   file 6 generated at: Tue Apr 10 10:57:42 2012  
  8.   file 7 generated at: Tue Apr 10 10:57:53 2012  
  9.   file 8 generated at: Tue Apr 10 10:58:04 2012  
  10.   file 9 generated at: Tue Apr 10 10:58:16 2012  
  11.   file 10 generated at: Tue Apr 10 10:58:27 2012  
  12.   file 11 generated at: Tue Apr 10 10:58:38 2012  

可見拆分一個文件需要費(fèi)時10-15秒，拆分文件總共耗時2分14秒


2）. 找出出現(xiàn)次數(shù)最大的IP：

代碼如下：

[python] view plaincopy

  1. __author__ = "Wally Yu (dayu.ebay@gmail.com)"  
  2. __date__ = "$Date: 2012/04/10 $"  
  3.   
  4. import os  
  5. from time import ctime  
  6.   
  7. def findIP(targetFolder):  
  8.     Result = {}  
  9.     IP = {}  
  10.     for root, dirs, files in os.walk(targetFolder):  
  11.         for f in files:  
  12.             # read small files  
  13.             file_handler = open(os.path.join(targetFolder, f), 'r')  
  14.             lines = file_handler.readlines()  
  15.             file_handler.close()  
  16.             # get IP in file, store to IP Dictionary  
  17.             for line in lines:  
  18.                 if line in IP:  
  19.                     IP[line] = IP[line] + 1  
  20.                 else:  
  21.                     IP[line] = 1  
  22.             # sort Dictionary  
  23.             IP = sorted(IP.items(), key=lambda d: d[1])  
  24.             # get max item(s), store to Result Dictionary  
  25.             maxItem = IP[-1][1]  
  26.             print '  File ' + str(f) + ":"  
  27.             print "    maxItem: " + str(IP[-1])  
  28.             tempTuple = IP.pop()  
  29.             while tempTuple[1] == maxItem:  
  30.                 if tempTuple[0] in Result:  
  31.                     Result[tempTuple[0]] = Result[tempTuple[0]] + 1  
  32.                 else:  
  33.                     Result[tempTuple[0]] = tempTuple[1]  
  34.                 tempTuple = IP.pop()  
  35.             IP = {}  
  36.             print '    Finished: ' + ctime()  
  37.                       
  38.     print sorted(Result.items(), key=lambda d: d[1])  
  39.   
  40. if __name__ == '__main__':  
  41.     print 'Start: ' + ctime()  
  42.     findIP("d:\\massiveData")  
  43.     print 'End: ' + ctime()  

運(yùn)行后的log如下：

[plain] view plaincopy

  1. Start: Thu Apr 12 10:20:01 2012  
  2.   File file_1.txt:  
  3.     maxItem: ('10.197.223.85\n', 190)  
  4.     Finished: Thu Apr 12 10:20:23 2012  
  5.   File file_10.txt:  
  6.     maxItem: ('10.197.44.215\n', 194)  
  7.     Finished: Thu Apr 12 10:20:37 2012  
  8.   File file_11.txt:  
  9.     maxItem: ('10.197.251.171\n', 181)  
  10.     Finished: Thu Apr 12 10:20:48 2012  
  11.   File file_2.txt:  
  12.     maxItem: ('10.197.181.190\n', 191)  
  13.     Finished: Thu Apr 12 10:21:00 2012  
  14.   File file_3.txt:  
  15.     maxItem: ('10.197.135.27\n', 193)  
  16.     Finished: Thu Apr 12 10:21:14 2012  
  17.   File file_4.txt:  
  18.     maxItem: ('10.197.208.113\n', 192)  
  19.     Finished: Thu Apr 12 10:21:24 2012  
  20.   File file_5.txt:  
  21.     maxItem: ('10.197.120.160\n', 190)  
  22.     Finished: Thu Apr 12 10:21:34 2012  
  23.   File file_6.txt:  
  24.     maxItem: ('10.197.69.155\n', 193)  
  25.     Finished: Thu Apr 12 10:21:44 2012  
  26.   File file_7.txt:  
  27.     maxItem: ('10.197.88.144\n', 192)  
  28.     Finished: Thu Apr 12 10:21:55 2012  
  29.   File file_8.txt:  
  30.     maxItem: ('10.197.103.234\n', 193)  
  31.     Finished: Thu Apr 12 10:22:08 2012  
  32.   File file_9.txt:  
  33.     maxItem: ('10.197.117.46\n', 192)  
  34.     Finished: Thu Apr 12 10:22:20 2012  
  35. [('10.197.251.171\n', 181), ('10.197.120.160\n', 190), ('10.197.223.85\n', 190), ('10.197.181.190\n', 191), ('10.197.117.46\n', 192), ('10.197.208.113\n', 192), ('10.197.88.144\n', 192), ('10.197.147.29\n', 193), ('10.197.68.183\n', 193), ('10.197.69.155\n', 193), ('10.197.103.234\n', 193), ('10.197.135.27\n', 193), ('10.197.44.215\n', 194)]  
  36. End: Thu Apr 12 10:22:21 2012  

由此可見，最大的IP地址為：“10.197.44.215”，共出現(xiàn)194次！

而Python的計算時間為2分20秒，非?？?img doc360img-src='http://image58.360doc.com/DownloadImg/2013/01/2414/29811983_1.gif' alt="大笑" src="http://image58.360doc.com/DownloadImg/2013/01/2414/29811983_1.gif" style="border-top-style: none; border-right-style: none; border-bottom-style: none; border-left-style: none; border-width: initial;">


（四）引申測試

以上是在假設(shè)內(nèi)存僅為128M下的計算時間，為了測試Python真正的執(zhí)行效率，打算再寫一算法，將所有1.4G的數(shù)據(jù)一次性導(dǎo)入內(nèi)存，并作內(nèi)排序，看看它的執(zhí)行效率

代碼如下：

[python] view plaincopy

  1. __author__ = "Wally Yu (dayu.ebay@gmail.com)"  
  2. __date__ = "$Date: 2012/04/10 $"  
  3.   
  4. import os  
  5. from time import ctime  
  6.   
  7. def findIPAtOnce(targetFile):  
  8.     print "Started At: " + ctime()  
  9.     Result = {}  
  10.     file_handler = open(targetFile, 'r')  
  11.     lines = file_handler.readlines()  
  12.     file_handler.close()  
  13.     print "File Read Finished At: " + ctime()  
  14.   
  15.     for line in lines:  
  16.         if line in Result:  
  17.             Result[line] = Result[line] + 1  
  18.         else:  
  19.             Result[line] = 1  
  20.     print "Write to Dic Finished At: " + ctime()  
  21.   
  22.     Result = sorted(Result.items(), key=lambda d: d[1])  
  23.     print "Sorting Finished At: " + ctime()  
  24.   
  25.     print 'Result:'  
  26.     for i in range(10):  
  27.         print '  ' + str(Result.pop())  
  28.   
  29. if __name__ == '__main__':  
  30.     findIPAtOnce("d:\\massiveIP.txt")  

最后得到了Memory Error：

[plain] view plaincopy

  1. Traceback (most recent call last):  
  2.   File "C:/Documents and Settings/wally-yu/Desktop/findIPAtOnce.py", line 30, in <module>  
  3.     findIPAtOnce("d:\\massiveIP.txt")  
  4.   File "C:/Documents and Settings/wally-yu/Desktop/findIPAtOnce.py", line 11, in findIPAtOnce  
  5.     lines = file_handler.readlines()  
  6. MemoryError  

哈哈哈！

為了測試Python的處理速度，重新生成一個小一點(diǎn)的Txt文件，重新運(yùn)行g(shù)enerageMassiveIPAddr函數(shù)，生成一千萬個IP地址

[python] view plaincopy

  1. if __name__ == '__main__':  
  2.     from time import ctime  
  3.     print ctime()  
  4.     for i in range(1):  
  5.         print '  ' + str(i) + ": " + ctime()  
  6.         generageMassiveIPAddr('d:\\massiveIP_small.txt', 10000000)  
  7.     print ctime()  

生成后的Txt占據(jù)144M的空間

再次運(yùn)行

[plain] view plaincopy

  1. if __name__ == '__main__':  
  2.     findIPAtOnce("d:\\massiveIP_small.txt")  

得到Log如下：

[plain] view plaincopy

  1. Started At: Thu Apr 12 11:03:35 2012  
  2. File Read Finished At: Thu Apr 12 11:03:41 2012  
  3. Write to Dic Finished At: Thu Apr 12 11:03:44 2012  
  4. Sorting Finished At: Thu Apr 12 11:03:45 2012  
  5. Result:  
  6.   ('10.197.222.105\n', 215)  
  7.   ('10.197.68.118\n', 210)  
  8.   ('10.197.229.152\n', 206)  
  9.   ('10.197.22.46\n', 202)  
  10.   ('10.197.98.83\n', 201)  
  11.   ('10.197.53.43\n', 201)  
  12.   ('10.197.169.65\n', 200)  
  13.   ('10.197.225.22\n', 200)  
  14.   ('10.197.146.78\n', 200)  
  15.   ('10.197.57.101\n', 200)  

可見時間消耗如下：

文件數(shù)據(jù)讀?。?秒

寫入Dictionary：3秒

排序：1秒

總共耗時不過10秒，而且大多時間都是I/O的開銷?。?！


（五）小節(jié)

由以上種種可見Python對于海量數(shù)據(jù)處理的高效率，也為Python的同行處理海量數(shù)據(jù)提供了一些思路

有興趣的朋友可以拿其他語言做同樣的測試，共同進(jìn)步


（六）修改

注：

1. 以上完成于2012年4月10日，本節(jié)及以下完成于2012年4月18日

2. 六、七節(jié)的增加是由于lidguan兄發(fā)現(xiàn)的一個大漏洞而做的修改，非常感謝！具體評論見下：

4樓 lidguan昨天 16:23發(fā)表[回復(fù)] [引用][舉報][刪除]
我有個問題,請不吝賜教:
將一個大文件分割成許多的小文件,但樓主分割方式好像是根據(jù)文件大小來分割,然后分別排序,得出一系列的最大值,最后在最大值中比較,得出一個最后結(jié)果....

但每個ip可能在不同文件中都有記錄,也許這個倒霉的ip是第一個文件的第二名,在第二個文件也是第二名,你用最大值進(jìn)行比較,就會把這個倒霉的ip忽略掉,但其實(shí)這個ip才是真正的最大值..

我不懂python,當(dāng)偽代碼看的....如有不對的地方,請多多原諒

我確實(shí)也是考慮不周，才導(dǎo)致了以上算法的巨大漏洞，今天做如下修改：

思路：

1. 不對大文件進(jìn)行拆分，否則會產(chǎn)生lidguan兄提到的問題

2. 假設(shè)這個一億個IP地址的重復(fù)率比較高，重復(fù)后的IP可以一次性記錄入Python Dictionary （Java Hash Map），那么就直接從大文件中一條一條讀取IP地址，記錄入Dictionary

3. 對Dictionary進(jìn)行排序并輸出


代碼：

[python] view plaincopy

  1. __author__ = "Wally Yu (dayu.ebay@gmail.com)"  
  2. __date__ = "$Date: 2012/04/18 $"  
  3.   
  4. import os  
  5. from time import ctime  
  6.   
  7. def findIPAtOnce(targetFile):  
  8.     print "Started At: " + ctime()  
  9.     Result = {}  
  10.     file_handler = open(targetFile, 'r')  
  11.   
  12.     for line in file_handler:  
  13.         if line in Result:  
  14.             Result[line] = Result[line] + 1  
  15.         else:  
  16.             Result[line] = 1  
  17.     print "Write to Dic Finished At: " + ctime()  
  18.   
  19.     file_handler.close()  
  20.   
  21.     Result = sorted(Result.items(), key=lambda d: d[1])  
  22.     print "Sorting Finished At: " + ctime()  
  23.   
  24.     print 'Result:'  
  25.     for i in range(10):  
  26.         print '  ' + str(Result.pop())  
  27.   
  28. if __name__ == '__main__':  
  29.     findIPAtOnce("d:\\massiveIP.txt")  

Log：

[plain] view plaincopy

  1. >>>   
  2. Started At: Wed Apr 18 13:20:34 2012  
  3. Write to Dic Finished At: Wed Apr 18 13:21:34 2012  
  4. Sorting Finished At: Wed Apr 18 13:21:34 2012  
  5. Result:  
  6.   ('10.197.200.159\n', 1713)  
  7.   ('10.197.143.163\n', 1707)  
  8.   ('10.197.68.193\n', 1693)  
  9.   ('10.197.136.119\n', 1692)  
  10.   ('10.197.71.24\n', 1692)  
  11.   ('10.197.132.242\n', 1690)  
  12.   ('10.197.4.219\n', 1688)  
  13.   ('10.197.113.84\n', 1684)  
  14.   ('10.197.204.142\n', 1681)  
  15.   ('10.197.78.110\n', 1675)  

由此可見，出現(xiàn)最多的IP為“10.197.200.159”，出現(xiàn)次數(shù)1713次！

執(zhí)行時間：

  • 讀取文件并寫入Dictionary：60秒
  • 內(nèi)排序：小于1秒?。?！

經(jīng)過這次的修改，運(yùn)算結(jié)果相信是可靠的


（七）總結(jié)

1. 修改后的代碼是在假設(shè)IP地址的重復(fù)性比較高，可以一次性導(dǎo)入內(nèi)存中操作的前提下展開的；如果重復(fù)性低，或者更大量的數(shù)據(jù)，導(dǎo)致無法一次導(dǎo)入內(nèi)存的話，就需要使用外排序來找出IP地址了

2. 希望大家多多探討，也幸虧lidguan兄的指出，否則險些釀成大錯大笑

3. 最近在討論的純粹的QA是否有必要存在，我也來多嘴幾句，我相信這些代碼如果是經(jīng)過了QA的測試后多多少少會降低風(fēng)險，尤其是此類明顯的邏輯性的錯誤是肯定可以避免的，所以QA人員的重要性不言而喻。說要消滅QA，鄙人覺得是軟件工程思維的一種倒退

    本站是提供個人知識管理的網(wǎng)絡(luò)存儲空間，所有內(nèi)容均由用戶發(fā)布，不代表本站觀點(diǎn)。請注意甄別內(nèi)容中的聯(lián)系方式、誘導(dǎo)購買等信息，謹(jǐn)防詐騙。如發(fā)現(xiàn)有害或侵權(quán)內(nèi)容，請點(diǎn)擊一鍵舉報。
    轉(zhuǎn)藏 分享 獻(xiàn)花（0）

    0條評論

    發(fā)表

    請遵守用戶 評論公約

    類似文章 更多