Schrift
Wiki:Tipp zum Debugging: use Data::Dumper; local $Data::Dumper::Useqq = 1; print Dumper \@var;
Start · Board · Anwendungen/Programme/Skripte in Perl · Allgemeines zu Perl
[thread]8313[/thread]

permutation (Seite 3)

Leser: 3


<< |< 1 2 3 4 >| >> 32 Einträge, 4 Seiten
docsnyder
 2006-09-13 17:55
#69644 #69644
User since
2005-09-08
300 Artikel
BenutzerIn
[Homepage] [default_avatar]
@Thorium

Versuche mal, in
Code: (dl )
for (my $i = 1; $i <= 2 ** $count; ++$i) {

das
Code: (dl )
2 ** $count

durch eine Variable besetzt, deren Wert Du "vor" der Schleife setzt. Dann wird das Ergebnis nicht bei jedem Schleifendurchlauf neu berechnet.

Würde mich jedenfalls mal interessieren, ob das im Benchmark spürbar ist.

Gruß, Doc
esskar
 2006-09-13 19:29
#69645 #69645
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
[quote=Dubu,12.09.2006, 13:35]Und es scheint auch etwas schneller zu sein[/quote]
cool - macht auch mal spass sich ne tolle lösung schenken zu lassen. :-)
renee
 2006-09-13 20:02
#69646 #69646
User since
2003-08-04
14371 Artikel
ModeratorIn
[Homepage] [default_avatar]
[quote=Thorium,13.09.2006, 15:09]Hier, ich hab auch noch einen Vorschlag; auch wenn ich im Benchmark damit Canchenlos bin ;):

Code (perl): (dl )
1
2
3
4
5
6

sub fbhp {
    [...]
    my @status;
    my $count = $#elements;
    push @status, 0 for (0..$count); 
   [...]



[...][/quote]
Etwas Zeit kannst Du sparen, indem Du aus
Code: (dl )
1
2
3
    my @status;
    my $count = $#elements;
    push @status, 0 for (0..$count);


Code: (dl )
my @status = (0) x scalar(@elements)
machst:

Code: (dl )
1
2
3
4
5
C:\community>perl bench.pl

          Rate thorium   renee
thorium 1131/s      --    -57%
renee   2656/s    135%      --


bench.pl
Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#!/usr/bin/perl

use Benchmark qw(:all);
use strict;
use warnings;

my @elements = (1) x 1000;

cmpthese( 10000, {
   'renee'   => sub {my @status = (0) x scalar(@elements)},
   'thorium' => sub {my @status;
                     my $count = $#elements;
                     push @status, 0 for (0..$count); }
});
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/
topeg
 2006-09-13 21:46
#69647 #69647
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Nun will ich auch eine Variante zum besten geben:
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
sub binhyphen3
{
  my ($str,$sep) = @_;
  my @lst=();
  my @ret=();
  map{push(@lst,$_); push(@lst,''); }split(/$sep/,$str);
  pop(@lst);
  my $lang=@lst;
  my $i=1;
  while($i<$lang)
  {
   for($i=1; $i<$lang; $i+=2)
   {
    if($lst[$i] eq '')
    {
     $lst[$i]=$sep;
     last;
    }
    $lst[$i]='';
   }
   push(@ret,join('',@lst));
  }
  return @ret;
}

Obwohl nicht rekusiv, ist es doch recht schnell. (nur ungefähr halb so schnell wie die schnellste rekursive Variante.)
Im Grunde handelt es sich hierbei um einen binären Zähler. :-)


Edit: "ich" ergänzt. :-)\n\n

<!--EDIT|topeg|1158170143-->
Thorium
 2006-09-14 01:19
#69648 #69648
User since
2003-08-04
232 Artikel
BenutzerIn
[Homepage] [default_avatar]
[quote=docsnyder,13.09.2006, 15:55]eine Variable besetzt, deren Wert Du "vor" der Schleife setzt. Dann wird das Ergebnis nicht bei jedem Schleifendurchlauf neu berechnet.[/quote]
Das habe ich unter anderem schon gemacht - und es brachte ca 100 Ausführungen pro Sekunde mehr - aber immernoch Welten von Version2 entfernt ;).
Ausserdem ist die 2. Variante auch bei sehr kurzen und sehr langen Ketten schneller - Variante 1 ist bei Ketten über ca 15 Elemente unbrauchbar (braucht länger als 20 sek).
Ich muss sagen, dass ich von der rekursiven Variante von Dubu ziemlich beeindruckt bin - darauf wär ich so nicht gekommen...

Allgemeine Frage:
Kann es sein, dass Operationen die mit dem Vergrössern von Arrays zu tun haben verdammt langsam sind? Vielleicht wär es intelligent, die grösse von Arrays vor solchen Schleifen auf die volle Grösse zu skallieren.
Wenn ich nämlich den Aufbau und die Rückgabe des @ret-Arrays weglasse, schlägt meine Variante Dubus um das ca. 10 Fache (auch wenn das ein unfairer vergleich ist ;) )\n\n

<!--EDIT|Thorium|1158182522-->
Per|li|nist der; -en, -en <zu ↑...ist>: a) Anhänger, Vertreter der radikalen Perlinisten die Perl als die einzig wahre Sprache ansehen; b) Mitglied einer perlinistischen Community.
esskar
 2006-09-14 03:50
#69649 #69649
User since
2003-08-04
7321 Artikel
ModeratorIn

user image
es gibt es 2^x versch. strings. wobei x die anzahl der bindestriche

du könntest das array schon auf diese größe sizen und dann via $ret[$x++] füllen.
topeg
 2006-09-14 08:37
#69650 #69650
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Das brigt nur bei extrem großen Arrays was, da zwar "$ret[$c++]=$w" ein tacken schneller zu "push(@ret,$w)" ist aber das erzeugen des Arrays mit "@ret=(0)x$length" hinzu kommt. Bei kleineren Arrays (< 5000) überwigt die Zeit die beim vorherigen erzeugen der Elemente verbraucht wird.
Dubu
 2006-09-15 00:34
#69651 #69651
User since
2003-08-04
2145 Artikel
ModeratorIn + EditorIn

user image
[quote=topeg,14.09.2006, 06:37]Das brigt nur bei extrem großen Arrays was, da zwar "$ret[$c++]=$w" ein tacken schneller zu "push(@ret,$w)" ist aber das erzeugen des Arrays mit "@ret=(0)x$length" hinzu kommt.[/quote]
Und wie ist es mit $#ret = $length vorher? Es müssen doch nicht unbedingt Nullen drin sein.
topeg
 2006-09-15 11:22
#69652 #69652
User since
2006-07-10
2611 Artikel
BenutzerIn

user image
Ich habe das mal mit dem Code getestet:
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
#!/usr/bin/perl
use strict;
use warnings;

use Benchmark qw/cmpthese/;

my $lng = shift(@ARGV) || die "Usage: $0 length [-count]\n";
my $cnt = shift(@ARGV) || "-10";

cmpthese ($cnt,
   {
       'Version 1' => sub { push_fast($lng) },
       'Version 2' => sub { cnt_fast1($lng) },
       'Version 3' => sub { cnt_fast1($lng) }
   }
);


sub push_fast
{
 my $l=shift(@_);
 my @arr;
 map{ push(@arr,"TEST") }(0..$l);
}

sub cnt_fast1
{
 my $l=shift(@_);
 my @arr=(0)x$l;
 my $c=0;
 map{ $arr[$c++]="TEST" }(0..$l);
}

sub cnt_fast2
{
 my $l=shift(@_);
 my @arr;
 $#arr = $l;
 my $c=0;
 map{ $arr[$c++]="TEST" }(0..$l);
}

Die Ergebnisse
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
> ./array_fast_test.pl
Usage: ./array_fast_test.pl length [-count]
> ./array_fast_test.pl 100 -10
            Rate Version 2 Version 3 Version 1
Version 2 8548/s        --       -1%      -13%
Version 3 8599/s        1%        --      -12%
Version 1 9780/s       14%       14%        --
> ./array_fast_test.pl 1000 -10
           Rate Version 3 Version 2 Version 1
Version 3 867/s        --       -0%      -13%
Version 2 868/s        0%        --      -13%
Version 1 995/s       15%       15%        --
> ./array_fast_test.pl 10000 -10
            Rate Version 2 Version 3 Version 1
Version 2 53.3/s        --       -0%      -15%
Version 3 53.4/s        0%        --      -15%
Version 1 63.0/s       18%       18%        --
> ./array_fast_test.pl 100000 -10
            Rate Version 2 Version 3 Version 1
Version 2 5.05/s        --       -0%      -20%
Version 3 5.06/s        0%        --      -20%
Version 1 6.34/s       25%       25%        --
> ./array_fast_test.pl 1000000 -10
          s/iter Version 2 Version 3 Version 1
Version 2   2.05        --       -1%      -20%
Version 3   2.03        1%        --      -19%
Version 1   1.64       25%       24%        --

Für sich alleine getestet ist "push" doch am schnellten, immer.
Warum ich vorher anere Ergebnisse hatte kann nur daran liegen, das ich nur die vorherigen Codestücke modifieziert hatte, und es da Konvergenzen gab.
renee
 2006-09-15 11:34
#69653 #69653
User since
2003-08-04
14371 Artikel
ModeratorIn
[Homepage] [default_avatar]
Naja, Du testest unterschiedliche Sachen. Version macht einfach ein push, um eine Vorbelegung des Arrays zu erreichen. In cnt_fast1 machst Du eine Vorbelegung mit 0 und dann überschreibst Du die Werte. Dass das langsamer ist, dürfte wohl klar sein.
map sollte man auch nicht im void-Kontext verwenden.

@Dubu: Eine Vorbelegung ist notwendig, da Thorium eine Abfrage auf == 0 macht. Ohne Vorbelegung würde es warnungen geben!

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
#!/usr/bin/perl
use strict;
use warnings;

use Benchmark qw/cmpthese/;

my $lng = shift(@ARGV) || die "Usage: $0 length [-count]\n";
my $cnt = shift(@ARGV) || "-10";

cmpthese ($cnt,
  {
      'Version 1' => sub { push_map($lng) },
      'Version 2' => sub { cnt_fast1($lng) },
      'Version 3' => sub { push_for($lng) }
  }
);


sub push_map
{
  my $l=shift(@_);
  my @arr;
  map{ push(@arr,"TEST") }(0..$l);
}

sub cnt_fast1
{
  my $l=shift(@_); 
  my @arr=("Test")x$l;
}

sub push_for
{
  my $l=shift(@_);
  my @arr;
  push(@arr,"TEST") for(0..$l);
}


Code: (dl )
1
2
3
4
5
~/entwicklung 54> perl bench.pl 100
            Rate Version 1 Version 3 Version 2
Version 1 4168/s        --      -21%      -53%
Version 3 5274/s       27%        --      -41%
Version 2 8899/s      113%       69%        --


Wie man sieht, ist die () x $length - Version die schneller als das push. Und die for-Schleife ist schneller als das map im void-Kontext
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/
<< |< 1 2 3 4 >| >> 32 Einträge, 4 Seiten



View all threads created 2006-09-11 12:30.