Schrift
Wiki:Tipp zum Debugging: use Data::Dumper; local $Data::Dumper::Useqq = 1; print Dumper \@var;
[thread]5846[/thread]

differenz zwischen zwei arrays



<< |< 1 2 3 >| >> 24 Einträge, 3 Seiten
Gast Gast
 2003-10-22 16:36
#66657 #66657
hallo,

wie kann ich am schnellsten die differenz von zwei arrays ermitteln?

z.B.

array1 = qw(hallo du wie geht das);
array2 = qw(hallo du);

ergebniss ist ein drittes array:

array3 = qw(wie geht das);

mfg: andi
betterworld
 2003-10-22 16:47
#66658 #66658
User since
2003-08-21
2613 Artikel
ModeratorIn

user image
Ich wuerde das vielleicht so machen:
Code: (dl )
1
2
3
4
5
6
use strict;
my @ar1=qw/hallo du wie geht das/;
my @ar2=qw/hallo du/;
my %ar2; @ar2{@ar2}=();
my @ar3 = grep {! exists $ar2{$_}} @ar1;
print "$_\n" for @ar3;

Ausgabe:
wie
geht
das

Wenn Du den Coder erklaert bekommen moechtest, frag nach.
Crian
 2003-10-22 16:54
#66659 #66659
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
Hmmm, und was machst Du bei Eingangsarrays

@a1 = qw(1 1 1 2 3 4 4 4);
@a2 = qw(1 1 2 2 3 3 4 4);

?

Da wär dann auch die Frage, wie denn die Differenz definiert ist.

Aber bei

@b1 = qw/eins eins zwei/;
@b2 = qw/eins zwei/;

sollte "eins" ausgegeben werden... wird aber wohl kaum werden bei Deinem Code ;-(
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
betterworld
 2003-10-22 17:17
#66660 #66660
User since
2003-08-21
2613 Artikel
ModeratorIn

user image
OK. Wie gesagt die Frage, wie man Differenz definiert. Nach Deiner Def. programmiert man vielleicht so:
Code: (dl )
1
2
3
4
5
6
7
use strict;
my @ar1=qw/1 2 2 3 3 3 4 4 4 4/;
my @ar2=qw/1 2 3 4/;
my %ar2;
$ar2{$_} ++ for @ar2;
my @ar3 = grep {not($ar2{$_} and $ar2{$_}--)} @ar1;
print "$_\n" for @ar3;


Nach einigen Edits sind jetzt alle Bugs raus. Vertraegt sich nur nicht mit use warnings;\n\n

<!--EDIT|betterworld|1066833820-->
andi
 2003-10-22 18:09
#66661 #66661
User since
2003-10-22
2 Artikel
BenutzerIn
[default_avatar]
danke funktioniert super!

eine erklärung währe wirklich nicht schlecht!
Crian
 2003-10-22 18:18
#66662 #66662
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
Dein Programm gibt 1 2 3 4 aus, was IMHO falsch ist.

Die Differenz würd ich als 2 3 3 4 4 4 sehen.

Für

my @ar1=qw/eins eins zwei/;
my @ar2=qw/eins zwei/;


Gibt er sogar "eins zwei" aus, richtig wäre "eins"!

Da liegt noch allerlei im Argen :-(
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
Crian
 2003-10-22 18:34
#66663 #66663
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
Ich hab einen Gegenvorschlag:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
use strict;
use warnings;
use diagnostics;

use Data::Dumper;

sub array_differenz ($$);

main();
exit;

sub main {
    my @a1 = qw/1 2 2 3 3 3 4 4 4 4/;
    my @a2 = qw/1 2 3 4/;
    my @a  = array_differenz(\@a1, \@a2);
    print "Ergebnis a:\n", Dumper \@a;

    my @b1 = qw/eins eins zwei/;
    my @b2 = qw/eins zwei/;
    my @b  = array_differenz(\@b1, \@b2);
    print "Ergebnis b:\n", Dumper \@b;
}

sub array_differenz ($$) {
    my $a1 = shift; # Array-Referenz
    my $a2 = shift; # Array-Referenz

    my @a1m2 = @$a1; # Array 1 minus Array 2;

    for my $element (@$a2) {
        for my $index (0..$#a1m2) {
            if ($element eq $a1m2[$index]) {
                splice @a1m2, $index, 1;
                last;
            }
        }
    }

    my @a2m1 = @$a2; # Array 2 minus Array 1;

    for my $element (@$a1) {
        for my $index (0..$#a2m1) {
            if ($element eq $a2m1[$index]) {
                splice @a2m1, $index, 1;
                last;
            }
        }
    }

    print "Array 1:\n", Dumper $a1;
    print "Array 2:\n", Dumper $a2;
    print "Array 1 minus Array 2:\n", Dumper \@a1m2;
    print "Array 2 minus Array 1:\n", Dumper \@a2m1;

    return (@a1m2, @a2m1);
}


mit dem Ergebnis

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
Array 1:
$VAR1 = [
         '1',
         '2',
         '2',
         '3',
         '3',
         '3',
         '4',
         '4',
         '4',
         '4'
       ];
Array 2:
$VAR1 = [
         '1',
         '2',
         '3',
         '4'
       ];
Array 1 minus Array 2:
$VAR1 = [
         '2',
         '3',
         '3',
         '4',
         '4',
         '4'
       ];
Array 2 minus Array 1:
$VAR1 = [];
Ergebnis a:
$VAR1 = [
         '2',
         '3',
         '3',
         '4',
         '4',
         '4'
       ];
Array 1:
$VAR1 = [
         'eins',
         'eins',
         'zwei'
       ];
Array 2:
$VAR1 = [
         'eins',
         'zwei'
       ];
Array 1 minus Array 2:
$VAR1 = [
         'eins'
       ];
Array 2 minus Array 1:
$VAR1 = [];
Ergebnis b:
$VAR1 = [
         'eins'
       ];


Edit: Als Definition der Arraydifferenz lege ich dabei zugrunde:
Quote
Die Differenz zweier Arrays A und B ist gleich der Vereinigung von A ohne B mit B ohne A.
\n\n

<!--EDIT|Crian|1066833372-->
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
betterworld
 2003-10-22 18:37
#66664 #66664
User since
2003-08-21
2613 Artikel
ModeratorIn

user image
[quote=andi,22.10.2003, 16:09]eine erklärung währe wirklich nicht schlecht![/quote]
hab ich befuerchtet ;)

> my %hsh2;

Wir legen einen Hash an, dem ich jetzt (im Ggs zu oeben) mal einen anderen Namen gebe, damit es keine Verwechslungen gibt.

> $hsh2{$_} ++ for @ar2;

In dieser for-Schleife wird fuer jedes Element von @ar2 ein Key im Hash angelegt. Und zwar wird @ar2 durchgelaufen und fuer jedes Element der entsprechende Value vom Hash inkrementiert. Der Value am Ende gibt jeweils die Anzahl an, wie oft der Key in @ar2 vorkommt.
Diese Art der Speicherung ist sinnvoller fuer diesen Zweck, da uns genau das interessiert: Wie oft kommt ein bestimmter String vor.

> my @ar3 = grep {not($hsh2{$_} and $hsh2{$_}--)} @ar1;

Mit grep koennen wir einen Teilarray aus @ar3 herausholen. In geschweiften Klammern steht die Bedingung, ob der Wert genommen wird oder nicht. Und zwar ist die Bedingung, ob der Wert als Key im Hash auftaucht und einen Value ungleich Null hat (denn dann ist $hsh2{$_} wahr) (Edit: dann genau NICHT). Und wenn dies erfuellt ist, wird nebenbei noch der Value dekrementiert. Es kann also passieren, dass er spaeter dann Null ist.\n\n

<!--EDIT|betterworld|1066834074-->
Crian
 2003-10-22 18:42
#66665 #66665
User since
2003-08-04
5866 Artikel
ModeratorIn
[Homepage]
user image
[quote=andi,22.10.2003, 16:09]danke funktioniert super!

eine erklärung währe wirklich nicht schlecht![/quote]
betterworlds Lösung taugt nur etwas für Mengen, also für Arrays, wo keine Elemente doppelt vorkommen. Und selbst da ist sein Verfahren unsymmetrisch, d.h. in meinen Augen falsch.
Im verwendeten Beispiel geht es gerade gut, weil die zweite Menge eine Teilmenge der ersten Menge ist.

Meine Lösung ist simpel: In der sub werden zwei Arrays gebildet: A ohne B und B ohne A, genannt @a1m2 und @a2m1. Dies geschieht am Beispiel von @a1m2 dadurch, dass ich erstmal alle Elemente von @$a in @a1m2 aufnehme und dann durch alle Elemente von @$2 durchgehe und jedes(!) aus @a1m2 entferne, falls ein solches vorhanden ist.

Zurückgegeben wird dann die Vereinigung der beiden Arrays.
Das Verfahren ist naturgemäß symmetrisch (die Arraydifferenz ist somit kommutativ) und wie man an den Beispielen sehen kann leistet sie genau das gewünschte.
s--Pevna-;s.([a-z]).chr((ord($1)-84)%26+97).gee; s^([A-Z])^chr((ord($1)-52)%26+65)^gee;print;

use strict; use warnings; Link zu meiner Perlseite
betterworld
 2003-10-22 18:44
#66666 #66666
User since
2003-08-21
2613 Artikel
ModeratorIn

user image
[quote=Crian,22.10.2003, 16:18]Dein Programm gibt 1 2 3 4 aus, was IMHO falsch ist.[/quote]
Ich hab den Post einige Male editiert. Das letzte Mal hatte ich das not vergessen und einen Bug wieder eingebaut. Jetzt muesste es gehen.
<< |< 1 2 3 >| >> 24 Einträge, 3 Seiten



View all threads created 2003-10-22 16:36.