Finding Elements in One Array but Not Another (Perl Cookbook, 2nd Edition)

## 4.8. Finding Elements in One Array but Not Another

### 4.8.1. Problem

You want to find elements that are in one array but not another.

### 4.8.2. Solution

You want to find elements in `@A` that aren't in `@B`. Build a hash of the keys of `@B` to use as a lookup table. Then check each element in `@A` to see whether it is in `@B`.

### 4.8.2.1. Straightforward implementation

>     # assume @A and @B are already loaded
>     %seen = ( );                    # lookup table to test membership of B
>     @aonly = ( );                   # answer

>     # build lookup table
>     foreach $item (@B) { $seen{$item} = 1 }

>     # find only elements in @A and not in @B
>     foreach $item (@A) {
>         unless ($seen{$item}) {
>             # it's not in %seen, so add to @aonly
>             push(@aonly, $item);
>         }
>     }

### 4.8.2.2. More idiomatic version

>     my %seen;     # lookup table
>     my @aonly;    # answer

>     # build lookup table
>     @seen{@B} = ( );

>     foreach $item (@A) {
>         push(@aonly, $item) unless exists $seen{$item};
>     }

### 4.8.2.3. Loopless version

>     my @A = ...;
>     my @B = ...;

>     my %seen;
>     @seen {@A} = ( );
>     delete @seen {@B};

>     my @aonly = keys %seen;

### 4.8.3. Discussion

As with nearly any problem in Perl that asks whether a scalar is in one list or another, this one uses a hash. First, process `@B` so that the `%seen` hash records each element from `@B` by setting its value to 1. Then process `@A` one element at a time, checking whether that particular element had been in `@B` by consulting the `%seen` hash.

The given code retains duplicate elements in `@A`. This can be fixed easily by adding the elements of `@A` to `%seen` as they are processed:

>     foreach $item (@A) {
>         push(@aonly, $item) unless $seen{$item};
>         $seen{$item} = 1;                       # mark as seen
>     }

The first two solutions differ mainly in how they build the hash. The first iterates through `@B`. The second uses a hash slice to initialize the hash. A hash slice is easiest illustrated by this example:

>     $hash{"key1"} = 1;
>     $hash{"key2"} = 2;

which is equivalent to:

>     @hash{"key1", "key2"} = (1,2);

The list in the curly braces holds the keys; the list on the right holds the values. We initialize `%seen` in the first solution by looping over each element in `@B` and setting the appropriate value of `%seen` to 1. In the second, we simply say:

>     @seen{@B} = ( );

This uses items in `@B` as keys for `%seen`, setting each corresponding value to `undef`, because there are fewer values on the right than places to put them. This works out here because we check for existence of the key, not logical truth or `defined` ness of the value. If we needed true values, a slice could still shorten our code:

>     @seen{@B} = (1) x @B;

In the third solution, we make use of this property even further and avoid explicit loops altogether. (Not that avoiding loops should be construed as being particularly virtuous; we're just showing you that there's more than one way to do it.) The slice assignment makes any element that was in `@A` a key, and the slice deletion removes from the hash any keys that were elements of `@B`, leaving those that were only in `@A`.

A fairly common situation where this might arise is when you have two files and would like to know which lines from the second file either were or weren't in the first. Here's a simple solution based on this recipe:

>     open(OLD, $path1)        || die "can't open $path1: $!";
>     @seen{ <OLD> } = ( );
>     open(NEW, $path2)        || die "can't open $path2: $!";
>     while (<NEW>) {
>         print if exists $seen{$_};
>     }

This shows the lines in the second file that were already seen in the first one. Use `unless` instead of `if` to show the lines in the second file that were not in the first.

Imagine two files, the first containing the lines:

>     red
>     yellow
>     green
>     blue

and the second containing:

>     green
>     orange
>     purple
>     black
>     yellow

The output using `if` would be:

>     green
>     yellow

and the output using `unless` would be:

>     orange
>     purple
>     black

You could even do this from the command line; given a suitable cat(1) program, it's easy:

>     % perl -e '@s{`cat OLD`}=( ); exists $s{$_} && print for `cat NEW''
>     % perl -e '@s{`cat OLD`}=( ); exists $s{$_} || print for `cat NEW''

You'd find that you just emulated these calls to the Unix `fgrep`(1) program:

>     % fgrep -Ff  OLD NEW
>     % fgrep -vFf OLD NEW

### 4.8.4. See Also

Hash slices are explained in perldata(1) and the "Variables" section of Chapter 2 of Programming Perl; Chapter 5; we use hashes in a similar fashion in Recipe 4.7 and Recipe 4.9

Copyright © 2003 O'Reilly & Associates. All rights reserved.