일부 코드로 인해 문제가 발생합니다. 필자는 끔찍한 프로그래머이므로 염두에 두지 마십시오. 아마도 내 솔루션은별로 웅변 적이 지 않습니다. 메모리가 부족한 이유는 아마도 4GB이며 스크립트가 천천히 채 웁니다.파이썬 메모리 부족 (접미사 트리 사용)
여기에 문제가 있습니다. 디렉토리에 약 3,500 개의 파일이 있습니다. 각 파일은 공백없이 비교적 적은 수의 문자를 가질 수있는 한 줄로 구성됩니다 (가장 작은 파일은 1.3 바이트에서 가장 큰 파일 대 200 바이트입니다). 내가 뭘 하려는지 설정 길이의 시간에 두 파일 사이에 일반적인 하위 문자열을 찾을 수 있습니다 (그것의 13 문자 아래의 코드에서). 나는 모든 파일 중에서 공통 부분 문자열을 찾고있는 것이 아니기 때문에 한 번에 두 개를 수행합니다. 그러나 모든 파일을 비교할 때까지 두 개를 조합하는 것이 좋습니다. 즉, 파일 사이에 설정된 길이의 모든 공통 부분 문자열이며 모든 부분에 공통된 부분 문자열이 아닙니다.
C 구현 (over here)을 래핑하는 접미어 트리 모듈을 사용합니다. 먼저 디렉토리의 모든 파일 목록을 만든 다음 두 조합을 조합하여 모든 조합을 다룹니다. 한 번에 두 파일을 접미어 트리로 전달한 다음 공통 부분 문자열 인 시퀀스를 찾습니다.
그러나 실제로 천천히 왜 메모리가 부족한지는 모르겠습니다. 코드에서 수정할 수 있기를 바래서 어떻게 든 사용하지 않는 메모리를 정리할 수 있었으면 좋겠습니까? 물론 3,500 개의 파일을 처리하는 데 오랜 시간이 걸리지 만, 4GB의 메모리를 점진적으로 채우지 않고도 수행 할 수 있기를 바랍니다. 어떤 도움이라도 대단히 감사하겠습니다!
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 코드의 메모리 누수를 확인한 후 이것이 내 전문 지식의 범위를 벗어나면 훨씬 느린 접근 방식을 사용하게되었습니다. 누구도이 영역에 대해 잘 알고 있다면 Python 용 C 접미사 트리 바인딩이 매우 가치 있다고 생각하므로 메모리 누수 또는 할당 해제 함수를 수정하기 위해 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")