Beefy Boxes and Bandwidth Generously Provided by pair Networks Frank
"be consistent"
 
PerlMonks  

subtract one array from another

by Anonymous Monk
on Oct 17, 2002 at 11:59 UTC ( #205991=perlquestion: print w/ replies, xml ) Need Help??
Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Dear Monks, I have two arrays that look like this:

@array1= 1 83 90 120 140 300

@array2= 83 140

I want to delete all the values in array2 out of array1 so array 1 looks like this:

@array1= 1 90 120 300

I have tried using for loops to iterate through the arrays:

for (my $search =0; $search<scalar @array1; $search++) { for ($search2 =0; $search2<scalar @array2; $search2++) { if($array1[$search] eq $array[$search2]) { this is where I want to do something that deletes the appr +opriate value from array1 } else { carry on as usual, no deletions }
I tried using undef to delete, and I know unshift/shift/pop/push only work at the start and end of arrays.

Any suggestions, Thanks

Comment on subtract one array from another
Download Code
Re: subtract one array from another
by rdfield (Priest) on Oct 17, 2002 at 12:03 UTC
    Have you read perlfaq4? There's a whole section on the basics of manipulating arrays.

    rdfield

Re: subtract one array from another
by ybiC (Prior) on Oct 17, 2002 at 12:09 UTC
    The "Save 2 files' diff as 3rd file" thread documents a quite similar question, brother Anonymonk, and assorted good answers.
        cheers,
        Don
        striving toward Perl Adept
        (it's pronounced "why-bick")
Re: subtract one array from another
by nothingmuch (Priest) on Oct 17, 2002 at 12:13 UTC
    Probably one of the fastest and most reliable ways would be to do the following:

    # create a hash representing @array2 my %hash; $hash{$_} = undef foreach (@array2); # grep only leaves what evaluates to true. # if an element of array1 is not in array2, it is # left in place @array1 = grep { not exists $hash{$_} } @array1;

    To perform your original approach, you would probably want to use the command splice, like so:

    if($array1[$search] eq $array[$search2]){ splice(@array1,$search,1); # remove 1 element from index $search i +n @array1 $search--; # the next element is already at $search. decrement so +when it's incremented we'll have the same value. }


    But this implementation is very inefficient.

    -nuffin
    zz zZ Z Z #!perl
Re: subtract one array from another
by zigdon (Deacon) on Oct 17, 2002 at 12:14 UTC
    I believe you're seeking splice.

    -- Dan

      Unfortunately, splice is itself an O(n) "loop", so by using it in a nested loop, you are writing an O(n3) algorithm. Even for a 20 and 5 element array, respectively, it's going to take several hundred operations - not exactly the best approach. Using a hash is better - it will run in linear time.

      Makeshifts last the longest.

        I did not know that at all! thanks! perhaps the documentation should mention this someplace? Or does it already - I was not able to find any reference.

        -- Dan

Re: subtract one array from another
by broquaint (Abbot) on Oct 17, 2002 at 12:19 UTC
    <WARNING>Overkill ahead</WARNING>
    use Quantum::Superpositions; my @array1 = qw( 1 83 90 120 140 300 ); my @array2 = qw( 83 140 ); my @filtered = grep all(@array2) != $_, @array1;
    Or perhaps more simply
    foreach my $i (0 .. $#array1) { $array1[$i] == $_ and delete $array1[$i] foreach @array2; } my @filtered = grep defined, @array1;

    HTH

    _________
    broquaint

Re: subtract one array from another
by demerphq (Chancellor) on Oct 17, 2002 at 12:25 UTC
    This is a FAQ. Please research using perldoc -q and use super search before asking a question...

    my %hash; $hash{$_}=1 foreach @array_1; @array_2=grep($hash{$_},@array_2);
    When you do read the FAQ's you will find a number of variants of the above along with suggestions about how to do this with various constraints.

    Also, perl is not restricted to C's overworked and confusing for() syntax. Your for loops above would be much simpler (and would involve less typing, and be less susceptable to fence pst errors) if done as follows

    #for (my $search =0; $search<scalar @array1; $search++) # blech, this +isnt C you know for my $search (0.. $#array1) # ahhh thats m +uch better
    HTH

    Sorry to repeat other peoples responses, I failed to press "submit" and then went on to other things.... :-)

    --- demerphq
    my friends call me, usually because I'm late....

      The $#array syntax is vaguely deprecated, IIRC...
      for my $search (0..scalar @array1)
      But since the .. operator takes scalar context, you can just say
      for my $search (0..@array1)

      (Update: the "vague deprecation" was from one of the Apocalypses. So it's safe for the indefinite future, I suppose. cf. Apocalypse 2)


      ---
      "I hate it when I think myself into a corner."
      Matt Mitchell
        Don't you need a -1 there someplace?
        perl -le ' @a = qw/a b c d/; print scalar @a; print $#a; __DATA__ output: 4 3 '

        -- Dan

        Yes I seem to remember hearing that... But then Juerd corrected me. I do not believe that it will in fact be going away.

        And of course as the someone else mentioned that should be @array1-1

        :-)

        --- demerphq
        my friends call me, usually because I'm late....

Re: subtract one array from another
by gnu@perl (Pilgrim) on Oct 17, 2002 at 15:10 UTC
    You could also use hashes for this:
    my %hash1 = ( 1 => '1', 83 => '1', 90 => '1', 120 => '1', 140 => '1', 300 => '1' ); my @array = ('83', '140'); for (@array){ delete $hash1{$_}; }
    Now keys(%hash1) only contains the entries you want. you could do more checking or other processing in your loop if you wanted. You could even be 'safer' like this:
    for (@array){ delete $hash1{$_} if exists $hash1{$_}; }
    but it is a little silly since the delete will only do anything if the entry exists in the hash anyway.

    Chad.

Re: subtract one array from another
by BrowserUk (Pope) on Oct 17, 2002 at 17:29 UTC

    Not really an answer for this OP I think, but rather than building a hash to detect matches (which for large arrays could be expensive), why not use a string?

    Would this be a Cheap idiom? Update:Obviously not!:( See below.) Good for golf maybe>

    #! perl -sw use strict; my @array1= qw(1 83 90 120 140 300); my @array2= qw(83 140); my @array3 = grep{ local $"="\c1"; -1==index( "\c1@array2\c1", "\c1$_\ +c1") } @array1; print "@array3\n"; __END__ c:\test>205991 1 90 120 300

    Cor! Like yer ring! ... HALO dammit! ... 'Ave it yer way! Hal-lo, Mister la-de-da. ... Like yer ring!
      I've used the same idiom, BrowserUK.

      One minor nit, however - use a temp variable, and stringify the array before the grep. Stringifying @array2 for each element of @array1 is probably more expensive than building a hash.

      Update: Unless I missed something on my benchmark, the faq is the fastest - by far! I didn't expect it, but I should have ;-)

      I varied the size of the array and the faq consistently came out on top. The larger @array2 got, the better the faq performed.

      #!/usr/bin/perl use strict; use warnings; use Benchmark qw/cmpthese/; use vars qw/@array1 @array2/; sub perlfaq { # lifted from nothingmuch's post above my %hash; $hash{$_} = undef foreach (@array2); @array1 = grep { not exists $hash{$_} } @array1; } sub buk { grep{ local $"="\c1"; -1==index( "\c1@array2\c1", "\c1$_\c1") } @a +rray1; } sub improved { local $" = "\c1"; my $temp = "\c1@array2\c1"; grep { -1==index($temp, "\c1$_\c1") } @array1; } push @array1, int (rand 100) for (1 .. 1000); push @array2, int (rand 100) for (1 .. 100); cmpthese (1_000, { perlfaq => \&perlfaq, buk => \&buk, improved => \&improved, }) __END__ Benchmark: timing 1000 iterations of buk, improved, perlfaq... buk: 58 wallclock secs (50.99 usr + 0.01 sys = 51.00 CPU) @ 19 +.61/s (n=1 000) improved: 4 wallclock secs ( 3.98 usr + 0.00 sys = 3.98 CPU) @ 25 +1.51/s (n= 1000) perlfaq: 1 wallclock secs ( 0.88 usr + 0.00 sys = 0.88 CPU) @ 11 +35.07/s (n =1000) Rate buk improved perlfaq buk 19.6/s -- -92% -98% improved 252/s 1183% -- -78% perlfaq 1135/s 5689% 351% --

        Nice one jsprat++!

        I spent the last hour playing with your benchmark trying to redeem something from whatever brainfart it was that caused me to post without benchmarking first. I failed.

        I tried varying the size of the array and the size of the elements and the only time I saw any benefit from the non-hash version was when the size of array * size of elements pushed the boundaries of my installed memory. The hash takes a fair amount more memory than the composite string, so the non-hash version survives a while longer at the pathelogical extremes.

        I managed a marginal improvement to your improved version by doing away with interpolation all together vis.

        sub improved { my $c = ord(1); my $temp = join $c, @array2; @array1 = grep { -1==index($temp, $c . $_ . $c ) } @array1; }

        I also saw an equally marginal improvement (~2%) in the faq version by using slice assignment rather than a for loop, but I'm pretty sure that this has been noted elsewhere.

        sub perlfaq { my %hash; @hash{@array2} = ((undef) x @array2); @array1 = grep { not exists $hash{$_} } @array1; }

        Either is at best a micro-optomisation. When I thought about the fact that index has to search the whole string every time, it's fairly obvious that the hash will win.


        Cor! Like yer ring! ... HALO dammit! ... 'Ave it yer way! Hal-lo, Mister la-de-da. ... Like yer ring!
Re: subtract one array from another
by nandeya (Monk) on Oct 17, 2002 at 18:59 UTC
    #! perl -w use strict; my @array1= qw(1 83 90 120 140 300); my @array2= qw(83 140); my %hash1=map{$_ =>1} @array2; my @array3=grep(!defined $hash1{$_}, @array1); print "$_\n" foreach (@array3);


    nandeya

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://205991]
Approved by ybiC
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others pondering the Monastery: (10)
As of 2014-04-18 06:00 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    April first is:







    Results (462 votes), past polls