Как добавить элементы из одного массива Perl, которых еще нет в другом массиве?

Question

Дано:

my @mylist1;
push(@mylist1,"A");
push(@mylist1,"B");
push(@mylist1,"C");

my @mylist2;
push(@mylist2,"A");
push(@mylist2,"D");
push(@mylist2,"E");

Какой самый быстрый способ в Perl вставить в mylist2 все элементы, которые есть в mylist1, а не в mylist2 (ABCDE).

Answer 1

Вы можете просто использовать List::MoreUtils модуля uniq:

use List::MoreUtils qw(uniq);

my @mylist1;
push( @mylist1, "A" );
push( @mylist1, "B" );
push( @mylist1, "C" );

my @mylist2;
push( @mylist2, "A" );
push( @mylist2, "D" );
push( @mylist2, "E" );

@mylist2 = uniq( @mylist1, @mylist2 );

printf "%s\n", ( join ',', @mylist2 );    # A,B,C,D,E

Answer 2

my %k;
map { $k{$_} = 1 } @mylist1;
map { $k{$_} = 1 } @mylist2;
@mylist2 = keys %k;

В качестве альтернативы:

my %k;
map { $k{$_} = 1 } @mylist2;
push(@mylist2, grep { !exists $k{$_} } @mylist1);

На самом деле - это может быть неправильно, поскольку они не учитывают наличие дубликатов в любом из исходных списков.

Вы не сказали в своем вопросе, должны ли списки представлять наборы (которые не могут содержать дубликаты) или просто простые списки. То, что вы действительно хотите, @mylist2 = @mylist1 U @mylist2 предполагает, что вы рассматриваете их как наборы.

РЕДАКТИРОВАТЬ: изменение приращения для присвоения - сохраняет чтение значения хеша

Answer 3

[ Первоначальный ответ по состоянию на 2008-11-27 до «С момента вопроса»; анализ с этого момента является новым по состоянию на 2008-11-29 гг. ]

Самый быстрый - не уверен. Это работает, хотя это не красиво:

#!/bin/perl -w
use strict;

my @mylist1;
push(@mylist1,"A");
push(@mylist1,"B");
push(@mylist1,"C");

my @mylist2;
push(@mylist2,"A");
push(@mylist2,"D");
push(@mylist2,"E");

sub value_in
{
    my($value, @array) = @_;
    foreach my $element (@array)
    {
        return 1 if $value eq $element;
    }
    return 0;
}

@mylist2 = (@mylist2, grep { ! value_in($_, @mylist2) } @mylist1);

print sort @mylist2, "\n";

Это позволяет избежать преобразования массивов в хэши, но для больших массивов саб value_in может быть медленным.

Поскольку вопрос был «какой метод самый быстрый», я провел несколько тестов. К моему не слишком большому удивлению, мой метод был самым медленным. К моему удивлению, самый быстрый способ был не из List :: MoreUtils. Вот код теста и результаты - используя измененную версию моего исходного предложения.

#!/bin/perl -w
use strict;
use List::MoreUtils  qw(uniq);
use Benchmark::Timer;

my @mylist1;
push(@mylist1,"A");
push(@mylist1,"B");
push(@mylist1,"C");

my @mylist2;
push(@mylist2,"A");
push(@mylist2,"D");
push(@mylist2,"E");

sub value_in
{
    my($value) = shift @_;
    return grep { $value eq $_ } @_;
}

my @mylist3;
my @mylist4;
my @mylist5;
my @mylist6;

my $t = Benchmark::Timer->new(skip=>1);
my $iterations = 10000;

for my $i (1..$iterations)
{
    $t->start('JLv2');
    @mylist3 = (@mylist2, grep { ! value_in($_, @mylist2) } @mylist1);
    $t->stop('JLv2');
}
print $t->report('JLv2');

for my $i (1..$iterations)
{
    $t->start('LMU');
    @mylist4 = uniq( @mylist1, @mylist2 );
    $t->stop('LMU');
}
print $t->report('LMU');

for my $i (1..$iterations)
{
    @mylist5 = @mylist2;
    $t->start('HV1');
    my %k;
    map { $k{$_} = 1 } @mylist5;
    push(@mylist5, grep { !exists $k{$_} } @mylist1);
    $t->stop('HV1');
}
print $t->report('HV1');

for my $i (1..$iterations)
{
    $t->start('HV2');
    my %k;
    map { $k{$_} = 1 } @mylist1;
    map { $k{$_} = 1 } @mylist2;
    @mylist6 = keys %k;
    $t->stop('HV2');
}
print $t->report('HV2');


print sort(@mylist3), "\n";
print sort(@mylist4), "\n";
print sort(@mylist5), "\n";
print sort(@mylist6), "\n";

Black JL: perl xxx.pl
9999 trials of JLv2 (1.298s total), 129us/trial
9999 trials of LMU (968.176ms total), 96us/trial
9999 trials of HV1 (516.799ms total), 51us/trial
9999 trials of HV2 (768.073ms total), 76us/trial
ABCDE
ABCDE
ABCDE
ABCDE
Black JL:

Это Perl 5.10.0, скомпилированный для 32-разрядного SPARC с множественностью на старинной версии Sun E450, работающей под управлением Solaris 10.

Я считаю, что тестовые настройки справедливы; все они генерируют свой ответ в новом массиве, отдельном от mylist1 и mylist2 (поэтому mylist1 и mylist2 могут быть повторно использованы для следующего теста). Ответ, обозначенный HV1 (хэш-значения 1), имеет начало отсчета времени после присвоения @ mylist5, что я считаю правильным. Однако, когда я выполнил выбор времени с начала до назначения, он все еще был самым быстрым:

Black JL: perl xxx.pl
9999 trials of JLv2 (1.293s total), 129us/trial
9999 trials of LMU (938.504ms total), 93us/trial
9999 trials of HV1 (505.998ms total), 50us/trial
9999 trials of HV2 (756.722ms total), 75us/trial
ABCDE
ABCDE
ABCDE
ABCDE
9999 trials of HV1A (655.582ms total), 65us/trial
Black JL:

Answer 4

Из-за вашего комментария "(ABCDE)" я предполагаю, что вы на самом деле имели в виду поместить в mylist1 те элементы в mylist2, которых нет в mylist1. Если это предположение неверно, вам нужно что-то сказать о том, в каком порядке вы хотите, чтобы все закончилось.

Сначала запишите, какие элементы в mylist1 находятся в хэше, затем поместите все элементы из mylist2, не найденные в хэше, в mylist1.

my %in_mylist1;
@in_mylist1{@mylist1} = ();
push @mylist1, grep ! exists $in_mylist1{$_}, @mylist2;

Answer 5

my(%work);
@work{@mylist1, @mylist2} = undef;
@mylist2 = sort keys %work;