schneller Abgleich vieler Zeilen (Allgemeines zu Perl)

[thread]6745[/thread]

schneller Abgleich vieler Zeilen

anti

2005-02-28 11:59

User since
2003-11-29
155 Artikel
BenutzerIn
[default_avatar]

Hi Community,

ich habe ein mittelschweres Sortier / Abgleichproblem. Ich möchte 2 Arrays vergleichen: sind die Einträge in beiden Arrays vorhanden ist alles ok, wenn nicht, sollen sie ins zweite Array eingefügt werden. Mein bisheriger Ansatz sieht so aus:

Code (perl): (dl )

print "Schleife2 start";
    foreach (@temp) {
        my ( $qip3, $zip3, $qp3, $zp3, $qt3, $zt3, $qm3, $zm3 ) = split( / /, $_ );
        my $da   = "0";
        #my $temp = $_;
        foreach (@monthly_temp) {
            my ( $qip4, $zip4, $qp4, $zp4, $qt4, $zt4, $qm4, $zm4 ) = split( / /, $_ );
            if ($qip3 eq $qip4 && $zip3 eq $zip4 && $qp3 eq $qp4 && $zp3 eq $zp4 ){$da = "1";}
        }
        if ( $da eq "0" ) {
            chomp($_);
            push( @monthly_temp, "$_" );
        }
    }
    print " ende\n";

Genau hier liegt der Hund auch begraben. Werden die Arrays sehr groß (ca. 10000 Zeilen) dauert dieser Vergleich ziemlich lange und mein Ansatz ist quasi unbrauchbar! Gibt es eine Möglichkeit, diesen Abgleich schneller auszuführen?

Danke, anti\n\n

2005-02-28 12:38

User since
2003-08-04
12208 Artikel
Admin1

pack ein array in einen hash, dann sparst du dir eine von den beiden schleifen.

Always code as if the guy who ends up maintaining your code will be a violent psychopath who knows where you live. -- Damian Conway in "Perl Best Practices"
lesen: Wiki:

Wie frage ich & perlintro Wiki:

brian's Leitfaden für jedes Perl-Problem

esskar

2005-02-28 12:42

User since
2003-08-04
7321 Artikel
ModeratorIn

user image

hab grade keine zeit, aber mein tipp ist:
* sortiere @temp
* lauf über @monthly_temp und suche die in @temp mit binärer suche
* dann hast du nicht mehr O(n^2) sondern nur noch O(n log n)

kann es nicht programmieren; muss zur arbeit!

renee

2005-02-28 13:15

User since
2003-08-04
14371 Artikel
ModeratorIn

Weg 1:

Code: (dl )

1
2

my @array = grep{my $i = $_; !grep{$_ eq $i}@monthly_temp}@temp;
push(@monthly_temp,@array);

Weg 2:

Code: (dl )

my %hash;
@hash{@monthly_temp} = 1;
for(@temp){
   push(@monthly_temp,$_) unless(exists $hash{$_});
}

OTRS-Erweiterungen (http://feature-addons.de/)
Frankfurt Perlmongers (http://frankfurt.pm/)
--

Unterlagen OTRS-Workshop 2012: http://otrs.perl-services.de/workshop.html
Perl-Entwicklung: http://perl-services.de/

anti

2005-02-28 13:28

User since
2003-11-29
155 Artikel
BenutzerIn
[default_avatar]

Danke für die schnellen Antworten, das ganze über Hashes zu realisieren funktioniert wunderbar -> von der Performance ganz zu schweigen (vorher hab ich ca. 90 Sekunden gewartet, nun nicht mal eine! ) .

Mit solchen Konstrukten machen Sortierungen/Ersetzungen ja fast schon Spass :)

Danke, anti

Dubu

2005-02-28 19:15

User since
2003-08-04
2145 Artikel
ModeratorIn + EditorIn

user image

[quote=renee,28.02.2005, 12:15]Weg 1:

Code: (dl )

1
2

my @array = grep{my $i = $_; !grep{$_ eq $i}@monthly_temp}@temp;
push(@monthly_temp,@array);

Weg 2:

Code: (dl )

my %hash;
@hash{@monthly_temp} = 1;
for(@temp){
   push(@monthly_temp,$_) unless(exists $hash{$_});
}

[/quote]
Pah, das geht kuerzer. (Edit: Okay, natuerlich nur, wenn die Reihenfolge im Array nicht wichtig ist, ich geb's zu ...) ;)

Weg 3:

Code: (dl )

1
2
3

my %hash;
@hash{@monthly_temp, @temp} = 1;
@monthly_temp = keys %hash;

\n\n

View all threads created 2005-02-28 11:59.