Wie füge ich Elemente aus einem Perl-Array hinzu, die nicht bereits im anderen Array sind?

Question

Gegeben:

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

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

Was in Perl der schnellste Weg, um alle Elemente in mylist2 einzufügen, die in mylist1 sind und nicht bereits in mylist2 (ABCDE).

Answer 1

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

Alternativ:

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

Eigentlich - das könnte falsch sein, weil sie nicht berücksichtigen, ob Duplikate entweder in den ursprünglichen Listen existieren könnten.

Sie haben in Ihrer Frage nicht gesagt, ob die Listen Sätze darstellen sollen (die keine Duplikate enthalten dürfen) oder nur Listen. Dass Sie effektiv @mylist2 = @mylist1 U @mylist2 wollen schlägt vor, dass Sie sie als Sätze behandeln.

EDIT: geändert Zuwachs zuweisen - speichert eine Lese des Hash-Wertes

Answer 2

[Ursprüngliche Antwort wie von 2008-11-27 bis „Da die Frage“; Die Analyse von da an ist neu seit 2008-11-29.]

Am schnellsten - nicht sicher. Dies funktioniert, obwohl es nicht schön ist:

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

Dies vermeidet die Arrays in Hashes Umwandlung - aber für großen Arrays, die value_in Unter langsam sein kann.

Da die Frage war "Was ist die schnellste Methode", habe ich ein Benchmarking durchgeführt. Zu meiner nicht allzu großen Überraschung war meine Methode am langsamsten. Zu meiner Überraschung kam die schnellste Methode nicht von List :: MoreUtils. Hier sind der Testcode und die Ergebnisse - mit einer modifizierten Version meines ursprünglichen Angebots.

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

Dies ist Perl 5.10.0 für 32-Bit-SPARC mit Vielfalt auf einem antiken Sun E450 mit Solaris 10.

Ich glaube zusammengestellt, dass die Testaufbauten fair sind; Sie alle generieren ihre Antwort in einem neuen Array, getrennt von mylist1 und mylist2 (so können mylist1 und mylist2 für den nächsten Test wiederverwendet werden). Die Antwort mit der Bezeichnung HV1 (Hash-Werte 1) beginnt nach der Zuweisung zu @ mylist5, was ich für richtig halte. Allerdings, wenn ich den Zeitpunkt mit dem Start vor der Zuweisung tat, es war immer noch am schnellsten:

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

Aufgrund Ihrer „(ABCDE)“ Kommentar, ich nehme an, Sie eigentlich gemeint Push auf mylist1 diese Elemente in mylist2 das ist nicht in meiner Liste1. Wenn diese Annahme inkorrekt ist, müssen Sie etwas darüber sagen, in welcher Reihenfolge die Dinge enden sollen.

Speichern Sie zunächst, welche Elemente in mylist1 in einem Hash enthalten sind, und drücken Sie dann alle in mylist2, die nicht im Hash gefunden wurden Meine Liste1.

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

Answer 4

Sie könnten nur die List::MoreUtils Moduls verwenden 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;