Perl中比较字符串数组的最佳方法是什么？

Question

我正在尝试比较多个包含目录文件列表的字符串数组。目标是确定每个目录中存在哪些文件以及哪些文件不存在。请考虑以下内容：

List1    List2    List3    List4
a        a        e        f
b        b        d        g
c        f        a        h

结果应该是：

列表1：

        List1    List2    List3    List4
 a      yes      yes      yes      no
 b      yes      yes      no       no
 c      yes      no       no       no

清单2：

        List1    List2    List3    List4
 a      yes      yes      yes      no
 b      yes      yes      no       no
 f      no       yes      no       yes

我可以遍历所有数组并遍历每个条目，遍历所有其他数组并执行grep：

 for my $curfile (@currentdirfiles) {
   if( grep(/$curfile/, @otherarrsfiles) ) {
        // Set 'yes'
   } else {
        // set 'no'
   }
 }

我的唯一担忧是最终会得到一个0^2n级别的数量级。我可能无法解决这个问题，因为我最终还是需要循环遍历所有的数组。可能grep函数可以有所改进，但我不确定。

您有什么想法吗？

- EDJ

Answer 1

对于大量的字符串查找，通常需要使用哈希。以下是一种实现方式：

use strict;
use warnings;

# Define the lists:
my @lists = (
  [qw(a b c)], # List 1
  [qw(a b f)], # List 2
  [qw(e d a)], # List 3
  [qw(f g h)], # List 4
);

# For each file, determine which lists it is in:
my %included;

for my $n (0 .. $#lists) {
  for my $file (@{ $lists[$n] }) {
    $included{$file}[$n] = 1;
  } # end for each $file in this list
} # end for each list number $n

# Print out the results:
my $fileWidth = 8;

for my $n (0 .. $#lists) {

  # Print the header rows:
  printf "\nList %d:\n", $n+1;

  print ' ' x $fileWidth;
  printf "%-8s", "List $_" for 1 .. @lists;
  print "\n";

  # Print a line for each file:
  for my $file (@{ $lists[$n] }) {
    printf "%-${fileWidth}s", $file;

    printf "%-8s", ($_ ? 'yes' : 'no') for @{ $included{$file} }[0 .. $#lists];
    print "\n";
  } # end for each $file in this list
} # end for each list number $n

- cjm

---

你对哈希的评论帮了我很多，谢谢。 - EDJ

Answer 2

最清晰的方法是使用perl5i和自动装箱：

use perl5i;
my @list1 = qw(one two three);
my @list2 = qw(one two four);    

my $missing = @list1 -> diff(\@list2);
my $both = @list1 -> intersect(\@list2);

在一个更受限制的设置中，可以使用哈希来作为文件名，以确保其唯一性。

sub in_list {
   my ($one, $two) = @_;
   my (@in, @out);
   my %a = map {$_ => 1} @$one;

   foreach my $f (@$two) {
      if ($a{$f}) {
          push @in, $f;
      }
      else {
          push @out, $f;
      }
   }  
   return (\@in, \@out);
}

my @list1 = qw(one two three);
my @list2 = qw(one two four);    
my ($in, $out) = in_list(\@list1, \@list2);

print "In list 1 and 2:\n";
print "  $_\n" foreach @$in;

print "In list 2 and not in list 1\n";
print "  $_\n" foreach @$out;

- Alex

Answer 3

为什么不在读取文件时记住每个文件的位置呢？

假设您有一个要从中读取的目录列表@dirlist：

use File::Slurp qw( read_dir );
my %in_dir;
my %dir_files;

foreach my $dir ( @dirlist ) {
    die "No such directory $dir" unless -d $dir;
    foreach my $file ( read_dir($dir) ) {
        $in_dir{$file}{$dir} = 1;
        push @{ $dir_files{$dir} }, $file;
    }
}

现在，$in_dir{filename}将为每个感兴趣的目录定义条目，而$dir_files{directory}将为每个目录列出文件列表...

foreach my $dir ( @dirlist ) {
    print "$dir\n";
    print join("\t", "", @dirlist);
    foreach my $file ( @{ $dir_files{$dir} } ) {
        my @info = ($file);
        foreach my $dir_for_file ( @dirlist ) {
            if ( defined $in_dir{$file}{$dir_for_file} ) {
                push @info, "Yes";
            } else {
                push @info, "No";
            }
        }
        print join("\t", @info), "\n";
    }
}

- unpythonic

---

谢谢，但是列表是以文件的形式发送给我的。我不是从目录中读取的。不过，你说得很好 :) - EDJ

Answer 4

现在问题已经修改，这将产生您想要的答案。它在O(n³)时间内工作，这对于该问题是最优的（有n³个输出）。

#!/usr/bin/env perl

use strict;
use warnings;

#List1    List2    List3    List4
#a        a        e        f
#b        b        d        g
#c        f        a        h

my(@lists) = ( { a => 1, b => 1, c => 1 },
               { a => 1, b => 1, f => 1 },
               { e => 1, d => 1, a => 1 },
               { f => 1, g => 1, h => 1 },
             );

my $i = 0;
foreach my $list (@lists)
{
    analyze(++$i, $list, @lists);
}

sub analyze
{
    my($num, $ref, @lists) = @_;
    printf "List %d\n", $num;

    my $pad = "     ";
    foreach my $i (1..4)
    {
        print "$pad   List$i";
        $pad = "";
    }
    print "\n";

    foreach my $file (sort keys %{$ref})
    {
        printf "%-8s", $file;
        foreach my $list (@lists)
        {
            my %dir = %{$list};
            printf "%-8s", (defined $dir{$file}) ? "yes" : "no";
        }
        print "\n";
    }
    print "\n";
}

我得到的输出是：

List 1
        List1   List2   List3   List4
a       yes     yes     yes     no      
b       yes     yes     no      no      
c       yes     no      no      no      

List 2
        List1   List2   List3   List4
a       yes     yes     yes     no      
b       yes     yes     no      no      
f       no      yes     no      yes     

List 3
        List1   List2   List3   List4
a       yes     yes     yes     no      
d       no      no      yes     no      
e       no      no      yes     no      

List 4
        List1   List2   List3   List4
f       no      yes     no      yes     
g       no      no      no      yes     
h       no      no      no      yes     

- Jonathan Leffler

---

“defined” 这个关键字让我感到更加容易接受，而且使用哈希表在搜索数百或数千行（文件）时是最有效率的。谢谢。 - EDJ

Answer 5

我的代码更简单，但输出结果并不完全符合您的要求：

@lst1=('a', 'b', 'c');
@lst2=('a', 'b', 'f');
@lst3=('e', 'd', 'a');
@lst4=('f', 'g', 'h');

%hsh=();

foreach $item (@lst1) {
    $hsh{$item}="list1";
}

foreach $item (@lst2) {
    if (defined($hsh{$item})) {
        $hsh{$item}=$hsh{$item}." list2";
    }
    else {
        $hsh{$item}="list2";
    }
}

foreach $item (@lst3) {
    if (defined($hsh{$item})) {
        $hsh{$item}=$hsh{$item}." list3";
    }
    else {
        $hsh{$item}="list3";
    }
}

foreach $item (@lst4) {
    if (defined($hsh{$item})) {
        $hsh{$item}=$hsh{$item}." list4";
    }
    else {
        $hsh{$item}="list4";
    }
}

foreach $key (sort keys %hsh) {
    printf("%s %s\n", $key, $hsh{$key});
}

给出：

a list1 list2 list3
b list1 list2
c list1
d list3
e list3
f list2 list4
g list4
h list4

- Ali B

Answer 6

抱歉回复晚了，我一直在修改这个问题，因为我不想再得到负面评分（让我感到沮丧）。

这是一个有趣的效率问题。我不知道我的解决方案是否适用于您，但我想分享一下。如果您的数组不经常更改，并且您的数组包含许多重复值，则可能仅在效率上有效。我没有对其进行任何效率检查。

基本上，解决方案是通过将数组值转换为位并在一次操作中对整个数组进行按位比较来删除交叉检查的一个维度。数组值被去重、排序并赋予序列号。然后通过按位或将数组的总序列号存储在单个值中。因此，可以使用一个操作仅检查单个序列号的单个数组，例如：

if ( array & serialno )

需要运行一次以准备数据，然后可以将其保存在缓存或类似位置。然后可以使用此数据，直到您的数据发生更改（例如删除或添加文件/文件夹）。我已经在未定义值上添加了致命退出，这意味着当它发生时必须刷新数据。

祝你好运！

use strict;
use warnings;

my @list1=('a', 'b', 'c');
my @list2=('a', 'b', 'f');
my @list3=('e', 'd', 'a');
my @list4=('f', 'g', 'h');

# combine arrays
my @total = (@list1, @list2, @list3, @list4);

# dedupe (Thanks Xetius for this code snippet)
my %unique = ();
foreach my $item (@total)
{
    $unique{$item} ++;
}
# Default sort(), don't think it matters
@total = sort keys %unique;

# translate to serial numbers
my %serials = ();
for (my $num = 0; $num <= $#total; $num++)
{
    $serials{$total[$num]} = $num;
}

# convert array values to serial numbers, and combine them
my @tx = ();
for my $entry (@list1) { $tx[0] |= 2**$serials{$entry}; }
for my $entry (@list2) { $tx[1] |= 2**$serials{$entry}; }
for my $entry (@list3) { $tx[2] |= 2**$serials{$entry}; }
for my $entry (@list4) { $tx[3] |= 2**$serials{$entry}; }

&print_all;

sub inList
{
    my ($value, $list) = @_;
    # Undefined serial numbers are not accepted
    if (! defined ($serials{$value}) ) {
            print "$value is not in the predefined list.\n";
            exit;
    }
    return ( 2**$serials{$value} & $tx[$list] );
}

sub yesno
{
    my ($value, $list) = @_;
    return ( &inList($value, $list) ? "yes":"no" );
}
# 
# The following code is for printing purposes only
#
sub print_all
{
    printf "%-6s %-6s %-6s %-6s %-6s\n", "", "List1", "List2", "List3", "List4";
    print "-" x 33, "\n";
    &table_print(@list1);
    &table_print(@list2);
    &table_print(@list3);
    &table_print(@list4);
}

sub table_print
{
    my @list = @_;
    for my $entry (@list) {
        printf "%-6s %-6s %-6s %-6s %-6s\n", $entry,
            &yesno($entry, 0),
            &yesno($entry, 1),
            &yesno($entry, 2),
            &yesno($entry, 3);
    }
    print "-" x 33, "\n";
}

- TLP

Answer 7

我会使用目录条目作为键建立哈希，其中包含每个找到的列表的哈希（实际上是集合）。遍历每个列表，对于每个新条目，将其添加到外部哈希中，并使用单个集合（或哈希）包含它最初出现的列表的标识符。对于在哈希中找到的任何条目，只需将当前列表标识符添加到值的集合/哈希中即可。

从那里，您可以简单地后处理哈希的排序键，并创建您的结果表的行。

个人认为Perl很丑，但以下是Python示例：

#!/usr/bin/env python
import sys
if len(sys.argv) < 2:
    print >> sys.stderr, "Must supply arguments"
    sys.exit(1)
args = sys.argv[1:]

# build hash entries by iterating over each listing
d = dict()
for each_file in args:
    name = each_file
    f = open(each_file, 'r')
    for line in f:
        line = line.strip()
        if line not in d:
            d[line] = set()
        d[line].add(name)
    f.close()

# post process the hash
report_template = "%-20s" + ("  %-10s" * len(args))
print report_template % (("Dir Entries",) + tuple(args))
for k in sorted(d.keys()):
    row = list()
    for col in args:
        row.append("yes") if col in d[k] else row.append("no")
    print report_template % ((k,)+tuple(row))

这段代码应该大部分都可以看懂，就像伪代码一样。 (k,) 和 ("Dir Entries",) 表达式可能看起来有点奇怪；但这是为了强制它们成为元组，这些元组必须使用字符串的 % 运算符解包到格式化字符串中。这些也可以写成例如 tuple([k]+row)（将第一个项目包装在 [] 中使其成为列表，然后将其添加到其他列表中并全部转换为元组）。

除此之外，将其翻译成 Perl 应该非常简单，只需要使用哈希表而不是字典和集合即可。

（顺便说一句，这个示例可以处理任意数量的列表，作为参数提供并输出为列。显然，在十几列之后，输出会变得相当麻烦，难以打印或显示；但这是一个容易推广的例子）。

- Jim Dennis

---

请不要在回答 Perl 问题时发布 Python 代码。大多数情况下，人们无法选择使用哪种编程语言。他们的老板已经为他们做出了决定。 - shawnhcorey

我说过，这是希望作为伪代码来阅读的意图。它恰好也是Python语言实现的事实与此大体无关（除了允许我进行测试这一小事实之外）。 - Jim Dennis