python - 优化:Python、Perl 和 C 后缀树库

Question

我有大约 3,500 个由单行字符串组成的文件。这些文件的大小各不相同(从大约 200b 到 1mb)。我试图将每个文件与其他文件进行比较，并在两个文件之间找到长度为 20 个字符的公共(public)子序列。需要注意的是，每次比较时子序列只在两个文件之间是通用的，而不是在所有文件中都是通用的。

我在这个问题上遇到过一些困难，但由于我不是专家，所以我最终得到了一些临时解决方案。我使用 itertools.combinations 在 Python 中构建一个列表，最终包含大约 6,239,278 个组合。然后，我一次将两个文件传递给一个 Perl 脚本，该脚本充当用 C 编写的后缀树库的包装器，称为 libstree。 .我试图避免这种类型的解决方案，但 Python 中唯一可比较的 C 后缀树包装器遭受 memory leak 的困扰。 .

所以这是我的问题。我已经计时，在我的机器上，该解决方案在 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";

Answer 1

与其编写 Python 来调用 Perl 来调用 C，我相信您最好放弃 Python 代码并全部用 Perl 编写。

如果您的文件肯定只包含一行，那么您可以通过编写来更简单地读取这些对

my @g = <>;

我相信下面的程序执行的功能与您的 Python 和 Perl 代码组合的功能相同，但我无法测试它，因为我目前无法安装 libstree。

但正如 ikegami 指出的那样，计算并存储每对文件的最长公共(public)子序列，然后再将它们分类会好得多。我不会继续编写代码，因为我不知道您需要什么信息 - 无论是仅子序列长度，还是您还需要字符和/或子序列的位置。

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;
}