Schrift
[thread]7347[/thread]

in_array() - Funktion bauen (Seite 3)

Leser: 1


<< |< 1 2 3 >| >> 26 Einträge, 3 Seiten
pq
 2005-10-13 23:28
#58783 #58783
User since
2003-08-04
12209 Artikel
Admin1
[Homepage]
user image
ich habs eben auch ausprobiert, das ist aber sicher nicht im sinne des moduls.
sorry, da habe ich mich dann wohl vertan.
mich wundert es aber ehrlich gesagt, auch wenn ich statt 45000 nur 5000
als vergleich nehme. ist grep evtl. auf skalaren kontext optimiert?

edit: ich hab was entdeckt
Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
my $f = 50;
use Benchmark;
use strict;
use List::Util qw(first);
my @x = (0..$ARGV[0]||1000);
Benchmark::timethese(-2, {
Grep => sub{my $y  = grep {$_ == $f} @x},
Util => sub {my $y = first {$_ == $f} @x} });
' 100
Benchmark:
running
Grep, Util
for at least 2 CPU seconds
...

     Grep:  2 wallclock secs ( 2.00 usr +  0.00 sys =  2.00 CPU) @ 46457.50/s (n=92915)

     Util:  2 wallclock secs ( 2.00 usr +  0.14 sys =  2.14 CPU) @ 76733.18/s (n=164209)

also wenn ich eine subref übergebe statt eines stirngs, ist Util schneller.
wenn ich @x noch größer mache, wird es entsprechend noch schneller...\n\n

<!--EDIT|pq|1129232849-->
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
Cremator
 2005-10-14 01:39
#58784 #58784
User since
2003-11-26
97 Artikel
BenutzerIn
[default_avatar]
Wenn sehr niedrige Zahlen (wie die 50 bei Dir) in sortierten Listen gesucht werden muessen ist Util erstmal schneller. Muss ja, weil first dann nur 50 Elemente durchsucht und grep eben alles.

Wenn die Liste unsortiert ist oder sehr hohe Werte am Ende einer sortierten Liste gesucht werden sollen relativiert sich das.

Bei mir ist es so, das bei der sortierten Liste mit 10k Elementen beide ungefaehr gleichschnell werden, wenn man so um die 3000er Marke rum sucht, danach ist grep dann schneller.

Bei einer unsortierten Liste kann Util schneller sein, muss aber nicht und ist es meistens auch nicht. Test dazu:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
use Benchmark;
use strict;
use List::Util qw(first);
my @x = ();
for(0..200) {
push @x, int(rand(1000));
}
Benchmark::timethese(-2, {
Grep => sub{my $y = grep {$_ == 300} @x},
Util => sub {my $y = first {$_ == 300} @x} });

Benchmark: running Grep, Util for at least 2 CPU seconds...
Grep: 2 wallclock secs ( 2.05 usr + 0.00 sys = 2.05 CPU) @ 24864.13/s (n=50872)
Util: 2 wallclock secs ( 2.13 usr + 0.00 sys = 2.13 CPU) @ 7761.41/s (n=16493)


Erhoehe ich die Listenlaenge bleibt das Verhaeltnis von ca. 1:3 gleich, wenn die gesuchte Zahl (300) nicht enthalten ist und die ganze Liste durchsucht werden muss. Je weiter vorne die Zahl in der Liste auftaucht umso schneller ist Util natuerlich.

Also laeuft das ganze auf eine Art Lottospiel hinaus. Wenn das gesuchte Element in der Liste enthalten ist, haengt es davon ab wie die Liste beschaffen ist und wie weit vorne das Element steht. Ist das Gesuchte nicht enthalten ist grep immer schneller.

Edit: Typos und Code-Tag.\n\n

<!--EDIT|Cremator|1129239910-->
pq
 2005-10-14 02:23
#58785 #58785
User since
2003-08-04
12209 Artikel
Admin1
[Homepage]
user image
also mein rechner tickt da anders:
list:util.pl:
Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
use strict;
use warnings;
my @x = (0..$ARGV[0]||1000);
my $f = $ARGV[1] || 500;
use Benchmark;
use List::Util qw(first);
Benchmark::timethese(-1, {
       Grep => sub{my $y  = grep {$_ == $f} @x},
       Util => sub {my $y = first {$_ == $f} @x}
   }
);

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
> perl list_util.pl 1000 1   
Benchmark: running Grep, Util for at least 1 CPU seconds...
     Grep:  1 wallclock secs ( 1.06 usr +  0.00 sys =  1.06 CPU) @ 4830.19/s (n=5120)
     Util:  1 wallclock secs ( 0.94 usr +  0.14 sys =  1.08 CPU) @ 176987.04/s (n=191146)
> perl list_util.pl 1000 500
Benchmark: running Grep, Util for at least 1 CPU seconds...
     Grep:  1 wallclock secs ( 1.07 usr +  0.00 sys =  1.07 CPU) @ 4785.05/s (n=5120)
     Util:  1 wallclock secs ( 1.05 usr +  0.01 sys =  1.06 CPU) @ 11269.81/s (n=11946)
> perl list_util.pl 1000 1000
Benchmark: running Grep, Util for at least 1 CPU seconds...
     Grep:  1 wallclock secs ( 1.06 usr +  0.00 sys =  1.06 CPU) @ 4830.19/s (n=5120)
     Util:  1 wallclock secs ( 1.06 usr +  0.01 sys =  1.07 CPU) @ 5910.28/s (n=6324)
> perl list_util.pl 1000 1001
Benchmark: running Grep, Util for at least 1 CPU seconds...
     Grep:  1 wallclock secs ( 1.12 usr +  0.00 sys =  1.12 CPU) @ 4799.11/s (n=5375)
     Util:  2 wallclock secs ( 1.07 usr +  0.01 sys =  1.08 CPU) @ 5855.56/s (n=6324)

List::Util ist bei mir immer schneller.
(edit: auch bei unsortierten listen wie in deinem beispiel mit deinen werten
ist hier List::Util immer schneller)
aber das ist anscheinend plattform-abhängig.
ich habe perl 5.8.6, Linux 2.6.4-52-default.
wie nun die liste und der gesuchte wert beschaffen sind, ist natürlich
eine frage der statistik.
kommt der wert auf jeden fall vor, kann man im allgemeinen davon ausgehen,
der gesuchte wert ist im schnitt in der mitte der liste.
sind die werte anders verteilt und/oder unsortiert, kommt das eben immer speziell auf die verteilung an.
wird es kompliziert, ist man mit dieser lösung vermutlich sowieso auf
dem holzweg, und man sollte über eine indizierung nachdenken =)\n\n

<!--EDIT|pq|1129242586-->
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
Cremator
 2005-10-14 02:43
#58786 #58786
User since
2003-11-26
97 Artikel
BenutzerIn
[default_avatar]
Jo, koennte wirklich an der Plattform liegen. Habe auf ActiveState Perl 5.8.2 / Win2000 getestet.

So, spaet genug. Werde spaeter nochmal drueberschauen.
ptk
 2005-10-14 04:49
#58787 #58787
User since
2003-11-28
3645 Artikel
ModeratorIn
[default_avatar]
ActivePerl hat doch Threading eingeschaltet, oder? Auf meiner Debian-Kiste mit einem threaded perl ist first() (nur bei der langsamsten Variante) langsamer:
Code: (dl )
1
2
3
4
~/work/perl-bench/grep-vs-first.pl 1000 1000
Benchmark: running Grep, Util for at least 1 CPU seconds...
Grep: 1 wallclock secs ( 1.08 usr + 0.00 sys = 1.08 CPU) @ 1382.41/s (n=1493)
Util: 1 wallclock secs ( 1.10 usr + 0.00 sys = 1.10 CPU) @ 813.64/s (n=895)

first() bei einem nicht-threaded perl verhält sich deutlich besser (FreeBSD mit perl5.8.7, langsamere Maschine):
Code: (dl )
1
2
3
4
perl5.8.7 ~/work/perl-bench/grep-vs-first.pl 1000 1000
Benchmark: running Grep, Util for at least 1 CPU seconds...
Grep: 2 wallclock secs ( 1.05 usr + 0.00 sys = 1.05 CPU) @ 1358.70/s (n=1433)
Util: 1 wallclock secs ( 1.07 usr + 0.01 sys = 1.08 CPU) @ 1876.41/s (n=2023)


Threads sind ja vor perl6 sowieso verboten :-)\n\n

<!--EDIT|ptk|1129251094-->
pq
 2005-10-14 12:15
#58788 #58788
User since
2003-08-04
12209 Artikel
Admin1
[Homepage]
user image
hmm.
This is perl, v5.8.4 built for x86_64-linux-thread-multi
list_util.pl 1000 1000
Benchmark:    
running        
Grep, Util    
for at least 1 CPU seconds
...
     Grep:  1 wallclock secs ( 1.13 usr +  0.00 sys =  1.13 CPU) @ 8649.56/s (n=9774)
     Util:  2 wallclock secs ( 1.08 usr +  0.00 sys =  1.08 CPU) @ 4525.00/s (n=4887)

bei 500 sind die beiden gleich schnell.\n\n

<!--EDIT|pq|1129277766-->
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
<< |< 1 2 3 >| >> 26 Einträge, 3 Seiten



View all threads created 2005-10-13 15:58.