subtract one array from another

Anonymous Monk has asked for the wisdom of the Perl Monks concerning the following question:

Replies are listed 'Best First'.
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;` [download] 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. }` [download] But this implementation is very inefficient. -nuffin zz zZ Z Z #!perl	[reply] [d/l] [select]
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);` [download] 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` [download] 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....	[reply] [d/l] [select]
Re: Re: subtract one array from another by antifun (Sexton) on Oct 17, 2002 at 13:49 UTC
The `$#array` syntax is vaguely deprecated, IIRC... `for my $search (0..scalar @array1)` [download] But since the `..` operator takes scalar context, you can just say `for my $search (0..@array1)` [download] (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	[reply] [d/l] [select]
Re: Re: Re: subtract one array from another by zigdon (Deacon) on Oct 17, 2002 at 13:55 UTC
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 '` [download] -- Dan	[reply] [d/l]
Re: Re: Re: subtract one array from another by demerphq (Chancellor) on Oct 17, 2002 at 16:07 UTC
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....	[reply]
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	[reply]
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;` [download] Or perhaps more simply `foreach my $i (0 .. $#array1) { $array1[$i] == $_ and delete $array1[$i] foreach @array2; } my @filtered = grep defined, @array1;` [download] HTH `_________ broquaint`	[reply] [d/l] [select]
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")	[reply]
Re: subtract one array from another by BrowserUk (Patriarch) 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` [download] Cor! Like yer ring! ... HALO dammit! ... 'Ave it yer way! Hal-lo, Mister la-de-da. ... Like yer ring!	[reply] [d/l]
Re: Re: subtract one array from another by jsprat (Curate) on Oct 17, 2002 at 18:35 UTC
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% -- [download]	[reply] [d/l] [select]
Re: Re: Re: subtract one array from another by BrowserUk (Patriarch) on Oct 17, 2002 at 23:18 UTC
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; }` [download] 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; }` [download] 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!	[reply] [d/l] [select]
Re: subtract one array from another by zigdon (Deacon) on Oct 17, 2002 at 12:14 UTC
I believe you're seeking splice. -- Dan	[reply]
Re^2: subtract one array from another by Aristotle (Chancellor) on Oct 17, 2002 at 14:22 UTC
Unfortunately, splice is itself an O(n) "loop", so by using it in a nested loop, you are writing an O(n³) 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.	[reply]
Re: Re^2: subtract one array from another by zigdon (Deacon) on Oct 17, 2002 at 15:34 UTC
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	[reply]
Re^4: subtract one array from another by Aristotle (Chancellor) on Oct 18, 2002 at 03:36 UTC
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{$_}; }` [download] 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{$_}; }` [download] but it is a little silly since the delete will only do anything if the entry exists in the hash anyway. Chad.	[reply] [d/l] [select]
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);` [download] nandeya	[reply] [d/l]