Jak dodać elementy z jednej tablicy Perla, które nie znajdują się już w innej macierzy?

Question

Dane:

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

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

Jaki jest najszybszy sposób w Perl wstawić mylist2 wszystkie elementy, które są w mylist1 a nie już w mylist2 (ABCDE).

Answer 1

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

Alternatywnie:

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

Właściwie - to może być błędne, ponieważ nie stanowią duplikaty czy może istnieć w jednej z oryginalnych list.

Nie odpowiedziałeś na pytanie, czy listy mają przedstawiać zestawy (które nie mogą zawierać duplikatów), czy tylko zwykłe listy. To, że skutecznie chcesz @mylist2 = @mylist1 U @mylist2 sugeruje, że traktujesz je jako zestawy.

EDIT: zmienił przyrost przypisania - zapisuje odczytu wartości hash

Answer 2

[Original odpowiedź jak od 2008-11-27 do „Ponieważ kwestia”; analiza na tej podstawie jest nowa od 2008-11-29.]

Najkrótsza - nie jestem pewien. To działa, choć nie jest całkiem:

#!/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"; 

to uniknąć konwersji tablice język skrótów - ale dla dużych tablic, value_in sub może być powolne.

Ponieważ pytanie brzmiało "Jaka jest najszybsza metoda", wykonałem kilka testów porównawczych. Ku mojemu niezbyt szerokiemu zaskoczeniu, moja metoda była najwolniejsza. Ku mojemu zaskoczeniu najszybsza metoda nie pochodziła z listy :: MoreUtils. Oto kod testowy i wyniki - przy użyciu zmodyfikowanej wersji mojej pierwotnej propozycji.

#!/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: 

To Perl 5.10.0 skompilowany dla 32-bitowej architektury SPARC z wielością na antyczne Sun E450 z systemem Solaris 10.

wierzę, że konfiguracje testowe są sprawiedliwe; wszystkie generują swoją odpowiedź w nowej tablicy, oddzielonej od mylist1 i mylist2 (więc mylist1 i mylist2 mogą być ponownie wykorzystane do następnego testu). Odpowiedź oznaczona jako HV1 (wartości mieszania 1) ma początek taktowania po przypisaniu do @ mylist5, co moim zdaniem jest poprawne. Jednak, gdy zrobiłem taktowanie z początku przed przypisaniem, to wciąż najszybszym:

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 3

powodu twoich „(ABCDE)” uwaga, jestem zakładając, że faktycznie oznaczało nasunąć mylist1 tych elementów w mylist2 które nie są w mylist1. Jeśli to założenie jest niepoprawne, musisz powiedzieć coś o tym, jaką kolejność chcesz zakończyć.

Po pierwsze, zapisz, które elementy znajdują się w mylist1 w haszyszu, a następnie naciśnij wszystkie te elementy w mylist2, które nie znajdują się w haszowaniu mylist1.

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

Answer 4

mógłby po prostu użyć moduł List::MoreUtils na 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 5

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