Python 内存不足(使用后缀树)

Question

我在处理一些代码时遇到了一些麻烦。请记住，我是一个糟糕的程序员，所以我的解决方案可能不是很有说服力(这可能是我内存不足的原因 - 我有 4 GB，脚本会慢慢填满它)。

问题来了。我在一个目录中有大约 3,500 个文件。每个文件由一行组成，可以包含相对较少或较多的字符且没有空格(最小文件为 200 字节，最大文件为 1.3 兆字节)。我想要做的是在设置长度的时间(在下面的代码中是 13 个字符)找到这些文件之间的公共(public)子字符串。我一次做两个，因为我不是在寻找它们中的公共(public)子字符串，而是在比较所有文件之前寻找两个的组合。即，文件之间设置长度的任何公共(public)子字符串，而不是所有文件共有的子字符串。

我使用了一个包含 C 实现的后缀树模块 (over here)。首先我列出了目录中的所有文件，然后我寻找两个组合以便覆盖所有组合，我一次将两个文件传递到后缀树，然后寻找作为公共(public)子字符串的序列。

但是，我真的不知道为什么它会慢慢耗尽内存。我希望我们可以对代码进行修改，以便它以某种方式清除未使用内容的内存？显然 3,500 个文件需要很长时间才能处理，但我希望可以在不逐渐填充 4 GB 内存的情况下完成。任何帮助将不胜感激!这是我到目前为止的代码:

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 后缀树绑定(bind)非常有值(value)。在没有后缀树的情况下通过这个脚本运行数据可能需要几天时间，所以我非常愿意看看是否有人有创造性的修复!

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")

Answer 1

我有理由相信您使用的后缀树包中存在内存泄漏。

证据 1:在 valgrind 中运行 python，然后运行这个简单的 Python 脚本

from suffix_trees import SuffixTree
t = SuffixTree("mississippi")
t = None

报告此泄漏:

==8800== 1,413 (32 direct, 1,381 indirect) bytes in 1 blocks are definitely lost in loss record 1,265 of 1,374
==8800==    at 0x4A0884D: malloc (vg_replace_malloc.c:263)
==8800==    by 0xBE70AEC: make_helper (suffix_tree.c:193)
==8800==    by 0xBE704B2: SuffixTree_init (python_bindings.c:240)
==8800==    by 0x3F98C9867B: ??? (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98C49A7D: PyObject_Call (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98CD71D6: PyEval_CallObjectWithKeywords (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98C5EB45: ??? (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98C49A7D: PyObject_Call (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98CD93F2: PyEval_EvalFrameEx (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98CDDB2E: PyEval_EvalCodeEx (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98C6D7B5: ??? (in /usr/lib64/libpython2.7.so.1.0)
==8800==    by 0x3F98C49A7D: PyObject_Call (in /usr/lib64/libpython2.7.so.1.0)

证据 2: 当您查看 suffix_tree.c 和 python_bindings.c 中的代码时，您会发现 make_helper() 函数，它为后缀树(使用 malloc)，但代码中的任何地方都没有一个 free。我专门查看了为 python_bindings 中定义的 Python 类型定义的分配和释放函数，但找不到树对象的任何函数。有一个用于节点对象，但它只解除分配对象的 Python 包装器部分，而不是 C 中的底层结构。

证据 3:python_bindings.c 中 Python 对象的数据类型定义附有一条有说服力的注释:

/* FIXME: deallocation of this guy! */
static PyTypeObject SuffixTreeType = {
    PyObject_HEAD_INIT(NULL)
    .tp_name      = "_suffix_tree.SuffixTree",
    /* ... */
    .tp_new       = SuffixTree_new,
};

建议:您可能需要联系包的作者，让他们知道这个问题。根据网页上的信息，他们已经在研究一个问题的解决方案，理想情况下，树本身和它包含的节点对象之间应该存在循环依赖——这是一个相关的问题，可能也是程序运行的原因当前不执行任何重新分配。

由于您的目的可能不需要节点到树的依赖性，因此您也可以通过向 python_bindings.c 中的树对象定义添加释放函数来应用自己的修复。