优化：Python,Perl和C后缀树库

发布时间：2020-12-16 22:00:05 所属栏目：Python 来源：网络整理

导读：我有大约3,500个由单行字符串组成的文件.文件大小不一(从大约200b到1mb).我正在尝试将每个文件与其他文件进行比较,并找到两个文件之间长度为20个字符的公共子序列.请注意,子序列仅在每次比较期间在两个文件之间是通用的,并且在所有文件中不常见. 我已经解决

我有大约3,500个由单行字符串组成的文件.文件大小不一(从大约200b到1mb).我正在尝试将每个文件与其他文件进行比较,并找到两个文件之间长度为20个字符的公共子序列.请注意,子序列仅在每次比较期间在两个文件之间是通用的,并且在所有文件中不常见.

我已经解决了这个问题,因为我不是专家,所以我最终得到了一些临时解决方案.我使用itertools.combinations在Python中构建一个列表,最终得到大约6,239,278个组合.然后我将这两个文件一次传递给一个Perl脚本,该脚本作为一个用C语言编写的后缀树库的包装器,称为libstree.我试图避免使用这种类型的解决方案,但Python中唯一可比的C后缀树包装器遭受了a 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 $/;


最佳答案
而不是编写Python来调用Perl来调用C,我相信你最好放弃Python代码并在Perl中编写它们.
如果您的文件肯定只包含一行,那么您可以通过简单地写更简单地读取对

my @g = <>;

我相信下面的程序执行与Python和Perl代码相同的功能,但我无法测试它,因为我目前无法安装libstree.
但正如池上指出的那样,计算和存储每对文件的最长公共子序列并将其分类后会更好.我不会继续对此进行编码,因为我不知道您需要什么信息 – 它是否仅仅是子序列长度,或者您是否还需要字符和/或子序列的位置.

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,"@pairn" if $lcs and length $lcs >= 20;
}


                        （编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!