[Israel.pm] How to remove elements according to a filter froman array

[Yossi Itzkovich]

Hi,

Thanks Gabor for the idea. The results were very educating.  Here is the
test code:
-----------------------------------
 use strict;
use Benchmark qw(:all);

doIt (100000, 2);
doIt (100000, 20000);
doIt (300000, 2);
doIt (300000, 20000);

sub doIt
  {
    our ($max,$mod)=@_;
print "max=$max, mod=$mod, resultSize=",$max/$mod,"\n";
my $count=5;
timethis ($count,'my @array=(0 .. $max);');

timethese ($count,
	   {
	    'grep' => 'my @array=(0 .. $max); @array=grep ( {$_ % $mod}
@array);0 and print scalar @array,"\n"',
	    'loop' => 'my @array=(0 .. $max);my $index=0; while ($index
< @array) { unless ($array[$index] % $mod) {splice (@array,$index,1);}
 else { ++$index;}}; 0 and print scalar @array,"\n";',
----------------------------------

The results show that performance depends a lot of how many items from
the array will pass the criteria (== how many splices will be done).
In general, grep is still the winner. In those cases where the
loop+splice is faster, the difference is small (but grep code is much
more simpler).


max=100000, mod=2, resultSize=50000
timethis 5:  1 wallclock secs ( 0.51 usr +  0.01 sys =  0.52 CPU) @
9.62/s (n=5)
Benchmark: timing 5 iterations of grep, loop...
      grep:  1 wallclock secs ( 1.16 usr +  0.00 sys =  1.16 CPU) @
4.31/s (n=5)
      loop: 23 wallclock secs (22.42 usr +  0.02 sys = 22.44 CPU) @
0.22/s (n=5)
max=100000, mod=20000, resultSize=5
timethis 5:  1 wallclock secs ( 0.86 usr +  0.00 sys =  0.86 CPU) @
5.81/s (n=5)
Benchmark: timing 5 iterations of grep, loop...
      grep:  3 wallclock secs ( 2.29 usr +  0.00 sys =  2.29 CPU) @
2.18/s (n=5)
      loop:  2 wallclock secs ( 2.00 usr +  0.00 sys =  2.00 CPU) @
2.50/s (n=5)
max=300000, mod=2, resultSize=150000
timethis 5:  2 wallclock secs ( 1.90 usr +  0.02 sys =  1.92 CPU) @
2.60/s (n=5)
Benchmark: timing 5 iterations of grep, loop...
      grep:  4 wallclock secs ( 4.18 usr +  0.00 sys =  4.18 CPU) @
1.20/s (n=5)
      loop: 217 wallclock secs (205.50 usr +  0.13 sys = 205.63 CPU) @
0.02/s (n=5)
max=300000, mod=20000, resultSize=15
timethis 5:  3 wallclock secs ( 2.99 usr +  0.00 sys =  2.99 CPU) @
1.67/s (n=5)
Benchmark: timing 5 iterations of grep, loop...
      grep:  8 wallclock secs ( 7.82 usr +  0.02 sys =  7.84 CPU) @
0.64/s (n=5)
      loop:  7 wallclock secs ( 6.55 usr +  0.00 sys =  6.55 CPU) @
0.76/s (n=5)


Yossi
--------------------------------------




-----Original Message-----
From: perl-bounces at perl.org.il [mailto:perl-bounces at perl.org.il] On
Behalf Of Gabor Szabo
Sent: Friday, May 25, 2007 8:04 AM
To: Perl in Israel
Subject: Re: [Israel.pm] How to remove elements according to a filter
froman array

I am sorry to be such an @$@%@ but have you actually measured that
you have a problem with speed at the point of deleting the elements?
How big is that array anyway?

Maybe the whole operation takes 0.01% of the total run time?

On the other hand if the array is really so big, maybe you reached the
limit
of your memory when you have it twice in there (when using grep)?
Then maybe you don't have to hold all this information in memory all the
time?

Now that you have the suggestions from others I would be really glad to
see
some benchmarks you publish on the relative speed of
grep vs loop and splice.

Gabor

On 5/24/07, Yossi Itzkovich <Yossi.Itzkovich at ecitele.com> wrote:
> Hi,
>
> Assuming I have a big array, and I want to remove elemnts according to
a
> criteria, how do I do it ?
> Please note, I am not asking about getting a new list of elements that
> passed the filter (like grep does), but removing the items from the
> original list.  For a big array (and assuming that arrays are
> implemented with linked list (is it ?)), then removing items from the
> original list might be much faster.
>
>
> Yossi

-- 
Gabor Szabo
http://www.szabgab.com/
Perl Training in Israel  http://www.pti.co.il/
_______________________________________________
Perl mailing list
Perl at perl.org.il
http://perl.org.il/mailman/listinfo/perl