优化: Python、Perl和C后缀树库
我有大约3,500个由单行字符串组成的文件。文件大小不同(从200 b到1mb)。我试图比较每个文件和另一个文件，并在两个文件之间找到一个长度为20个字符的公共子序列。请注意，在每次比较期间，子序列仅在两个文件之间是常见的，而不是在所有文件中都很常见。
我对这个问题有些困惑，因为我不是专家，所以我得到了一个临时的解决方案。我使用itertools.combinations在Python中构建了一个列表，最终得到了大约6,239,278个组合。然后，我将文件一次两个传递给一个Perl脚本，该脚本充当一个后缀树库的包装器，用C编写，名为利布斯特树。我试图避免这种类型的解决方案，但是Python中唯一类似的C后缀树包装器受到了内存泄漏的影响。
所以这是我的问题。我对它进行了计时，在我的机器上，解决方案在25秒内处理了大约500次比较。因此，这意味着，它将需要大约3天的连续处理，以完成任务。然后，我必须再做一次，看看25个字符，而不是20个字符。请注意，我已经走出了我的舒适区域，不是一个很好的程序员，所以我肯定有一个更优雅的方法来做到这一点。我想我应该在这里请求它，并生成我的代码，看看是否有人对我如何更快地完成这项任务有任何建议。
Python代码：
from itertools import combinations
import glob, subprocess
glist = glob.glob("Data/*.g")
i = 0
for a,b in combinations(glist, 2):
i += 1
p = subprocess.Popen(["perl", "suffix_tree.pl", a, b, "20"], shell=False, stdout=subprocess.PIPE)
p = p.stdout.read()
a = a.split("/")
b = b.split("/")
a = a[1].split(".")
b = b[1].split(".")
print str(i) + ":" + str(a[0]) + " --- " + str(b[0])
if p != "" and len(p) == 20:
with open("tmp.list", "a") as openf:
openf.write(a[0] + " " + b[0] + "\n")Perl代码：
use strict;
use Tree::Suffix;
open FILE, "<$ARGV[0]";
my $a = do { local $/; <FILE> };
open FILE, "<$ARGV[1]";
my $b = do { local $/; <FILE> };
my @g = ($a,$b);
my $st = Tree::Suffix->new(@g);
my ($c) = $st->lcs($ARGV[2],-1);
print "$c";回答 1
Stack Overflow用户
发布于 2012-07-21 16:42:34
与编写Python来调用Perl调用C不同，我相信您最好放弃Python代码，用Perl编写全部代码。
如果您的文件肯定只包含一行，那么只需编写以下内容，就可以更简单地读取这两对文件。
my @g = <>;我相信下面的程序执行与Python和Perl代码合并后的相同功能，但我无法测试它，因为我目前无法安装libstree。
但是，正如ikegami所指出的那样，为每一对文件计算和存储最长的公共子序列，然后将它们放入类别会好得多。我不会继续对此进行编码，因为我不知道您需要什么信息--是否只是子序列长度，或者是否需要字符和/或子序列的位置。
use strict;
use warnings;
use Math::Combinatorics;
use Tree::Suffix;
my @glist = glob "Data/*.g";
my $iterator = Math::Combinatorics->new(count => 2, data => \@glist);
open my $fh, '>', 'tmp.list' or die $!;
my $n = 0;
while (my @pair = $iterator->next_combination) {
$n++;
@ARGV = @pair;
my @g = <>;
my $tree = Tree::Suffix->new(@g);
my $lcs = $tree->lcs;
@pair = map m|/(.+?)\.|, @pair;
print "$n: $pair[0] --- $pair[1]\n";
print $fh, "@pair\n" if $lcs and length $lcs >= 20;
}https://stackoverflow.com/questions/11589525
复制相似问题
腾讯云开发者
