我遇到了一些代碼有點麻煩。請記住,我是一個可怕的程序員,所以我的解決方案可能不是很有說服力(可能是我內存不足的原因 - 我有4千兆字節,腳本緩慢地填滿了它)。Python內存不足(使用後綴樹)
這是問題所在。我在一個目錄中有大約3,500個文件。每個文件由一行代碼組成,這些代碼行可以包含相對較少或很多字符,且不含空格(最小的文件是200字節,最大的是1.3 MB)。我想要做的是在這些文件之間找到兩個設置長度的共同子字符串(在下面的代碼中是13個字符)。我一次只做兩個,因爲我沒有在所有這些文件中尋找一個共同的子串,而是兩個組合,直到所有文件進行比較。即,文件之間設置長度的任何常見子字符串,而不是所有這些文件共有的子字符串。
我使用後綴樹模塊來封裝C實現(over here)。首先我列出目錄中的所有文件,然後查找兩個組合,以便涵蓋所有組合,我一次將兩個文件傳遞到後綴樹,然後查找常見子串的序列。
但是,我真的不知道它爲什麼會慢慢地耗盡內存。我希望我們可以對代碼進行修改,以便以某種方式清除未使用內容的內存?顯然有3,500個文件需要很長時間才能處理,但我希望可以在不增量填充4千兆字節的內存的情況下完成。任何幫助將不勝感激!這是到目前爲止,我已經得到了代碼:
from suffix_tree import GeneralisedSuffixTree
from itertools import combinations
import glob, hashlib, os
alist = open('tmp.adjlist', 'w')
def read_f(f):
f = open(f, "r")
s = str(f.readlines())
f.close()
return s
def read_gs(a,b):
s1 = read_f(a)
s2 = read_f(b)
print str(a) + ":" + str(hashlib.md5(s1).hexdigest()) + " --- " + str(b) + ":" + str(hashlib.md5(s2).hexdigest())
return [s1,s2]
def build_tree(s):
hlist = []
stree = GeneralisedSuffixTree(s)
for shared in stree.sharedSubstrings(13):
for seq,start,stop in shared:
hlist.append(hashlib.md5(stree.sequences[seq]).hexdigest())
hlist = list(set(hlist))
for h in hlist:
alist.write(str(h) + " ")
alist.write('\n')
glist = []
for g in glob.glob("*.g"):
glist.append(g)
for a,b in list(combinations(glist, 2)):
s = read_gs(a,b)
build_tree(s)
alist.close()
os.system("uniq tmp.adjlist network.adjlist && rm tmp.adjlist")
更新#1
下面是更新後的代碼。我添加了Pyrce提出的建議。然而,在jogojapan發現了C代碼中的內存泄漏之後,鑑於它超出了我的專業知識範圍,我最終採用了一種更慢的方法。如果有人對這方面有所瞭解,我會很好奇如何修改C代碼來修復內存泄漏或釋放函數,因爲我認爲Python的C後綴樹綁定非常有價值。可能需要幾天的時間才能通過此腳本運行數據而無需後綴樹,因此我絕對樂於看到任何人是否有創意修補程序!
from itertools import combinations
import glob, hashlib, os
def read_f(f):
with open(f, "r") as openf:
s = str(openf.readlines())
return s
def read_gs(a,b):
s1 = read_f(a)
s2 = read_f(b)
print str(a) + ":" + str(hashlib.md5(s1).hexdigest()) + " --- " + str(b) + ":" + str(hashlib.md5(s2).hexdigest())
return [s1,s2]
def lcs(S1, S2):
M = [[0]*(1+len(S2)) for i in xrange(1+len(S1))]
longest, x_longest = 0, 0
for x in xrange(1,1+len(S1)):
for y in xrange(1,1+len(S2)):
if S1[x-1] == S2[y-1]:
M[x][y] = M[x-1][y-1] + 1
if M[x][y]>longest:
longest = M[x][y]
x_longest = x
else:
M[x][y] = 0
return S1[x_longest-longest: x_longest]
glist = glob.glob("*.g")
for a,b in combinations(glist, 2):
s = read_gs(a,b)
p = lcs(s[0],s[1])
if p != "" and len(p) >= 13:
with open("tmp.adjlist", "a") as openf:
openf.write(hashlib.md5(s[1]).hexdigest() + " " + hashlib.md5(s[0]).hexdigest() + "\n")
os.system("uniq tmp.adjlist network.adjlist && rm tmp.adjlist")