Какой лучший способ сравнить массивы строк в Perl

Question

Я пытаюсь сравнить несколько массивов строк, содержащих списки файлов каталогов. Цель состоит в том, чтобы определить, какие файлы существуют в каждом каталоге и какие файлы не существуют. Рассмотрим:

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

Результат должен быть:

List1:

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

List2:

        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, но я не уверен.

Есть мысли?

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

Answer 2

Почему бы просто не запомнить, где находится каждый файл, когда вы читаете их.

Допустим, у вас есть список каталогов для чтения в @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";
    }
}

Answer 3

Самый простой способ - использовать 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;

Answer 4

Извините за поздний ответ, я полировал это некоторое время, потому что я не хотел еще один отрицательный результат (выводит меня из себя).

Это интересная проблема эффективности. Я не знаю, сработает ли мое решение для вас, но я подумала, что поделюсь им в любом случае. Вероятно, это эффективно, только если ваши массивы не меняются слишком часто, и если ваши массивы содержат много повторяющихся значений. Я не проводил никаких проверок эффективности.

По сути, решение состоит в том, чтобы удалить одно измерение перекрестной проверки, превратив значения массива в биты и выполнив побитовое сравнение всего массива за один раз. Значения массива дедуплицируются, сортируются и получают серийный номер. Массивы итоговых серийных номеров затем сохраняются в одном значении побитовым или. Таким образом, один массив может быть проверен на наличие одного серийного номера только с одной операцией, например ::10000

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

Answer 5

Я бы создал хеш, используя записи каталога в качестве ключей, содержащих хеши (фактически наборы) каждого листинга, в котором он был найден.Итерируйте по каждому листингу, для каждой новой записи добавьте его во внешний хеш с одним набором (или хешем), содержащим идентификатор листинга, в котором он был впервые обнаружен.Для любой записи, найденной в хэше, просто добавьте текущий идентификатор листинга в набор значений / хэш.

Оттуда вы можете просто выполнить постобработку отсортированных ключей хеша и создать строки вашей результирующей таблицы.

Лично я считаю 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 должен быть довольно простым, просто используя хеши вместо словарей и наборов.

(Кстати, этот пример будет работать с произвольным числом списков, представляемых в качестве аргументов и выводимых в виде столбцов. Очевидно, после дюжиныстолбцы, вывод которых будет довольно громоздким для печати или отображения, но это было легко обобщить).

Answer 6

Мой код проще, но вывод не совсем то, что вы хотите:

@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

Answer 7

Теперь, когда вопрос был изменен, вы получите нужный ответ.Он работает за время 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