Hi!

You write that you use nested for. That is a very inefficient way to do it. Suppose n is the size of the array, you would need O(n^2) compares. In your case it is ~7000000*7000000, which is very much.

The following algorithm would be much faster O(n) (or ~7000000*3):

1. create a temporary hash
2. add all elements of the first array to that hash; use the array-value as a key and 1 as a value
3. pass through the second array; if the current value is already in the hash, increase its value by 2
4. pass through the hash; if all values are 3, array1 is part of array2

Another idea could be to sort both arrays (the perl sort-function is more efficient than a "nested-for-(bubble-)sort") and then work on the sorted arrays.

HTH, Rata

As soon as you create "buckets" instead of single hashes, the algorithm also works for multiple elements per key:

my @left = qw(1 2 3 1 1);
my %left;
for my $l (@left) {
    my $key = $l; # maybe you want some more complicated key than the 
+item itself
    $left{ $key } ||= [];
    push @{ $left{ $key } }, $l;
};

for my $r (@right) {
    my $key = $r; # maybe you want some more complicated key than the 
+item itself
    if (@{ $left{ $key }}) {
        my $found = shift @{ $left{ $key }};
        print "For $key, I found the pair ($found, $r).\n";
    } elsif (exists $left{ $key }) {
        print "For $key, there is at one item on the right side left o
+ver: $r.\n";
    } else {
        print "For $key, there is no item on the left side at all: $r.
+\n";
    };
};

# Now lets see if we have any values on the left side that did not pai
+r:
for my $l (keys %left) {
    my @leftover = @{ $left{ $l } };
    for (@leftover) {
        print "For $l, there was no corresponding element on the right
+ side ($_)\n";
    };
};
[download]

I haven't checked that code, but the approach is one I've used lots and lots when reconciling lists :)

The only thing I'll add to the "use a hash" advice, is don't read the data into two arrays first. You'll likely to run out of memory because of the duplication.

Far better to build a hash directly from the smaller set as you read it in. And the read the second set one-by-one and test it against the hash. For datasets of this size, that likely to save you a large amount of memory, and quite a bit of time.

#!/usr/bin/perl

use strict;
use warnings;

my (@array1, @array2);
my %seen;

# Fabricate some array
use List::Util qw(shuffle);
@array2 = shuffle (0..1000000);
@array1 = @array2[0..950000];


# Scan our first array
foreach my $key (@array1) {
        $seen{$key} = 0;
}

# Search our second array
foreach my $key (@array2) {
        # Check if valid key    Yes, count it   No, warn
        defined($seen{$key}) ?  $seen{$key}++   : warn qq{Key '$key' f
+ound, but not searching for it.\n};
}

# Determine the item count
foreach my $item (keys %seen) {
        my $count = $seen{$item};

        if ($count == 1) {
                # Only once, as intended
        }
        elsif ($count == 0) {
                # Missing, report
                print qq{Item '$item' not found in search array.\n};
        }
        else {
                # Multiple items, report
                print qq{Item '$item' found multiple ($count) times in
+ search array.\n};
        }
}
[download]

my @array1 = ...;
my @array2 = ...;
my %hash = map {$_ => 1} @array1;
foreach my $e (@array2) {
    next unless exists $hash{$e};
    die "Failure" if --$hash{$e} < 0;
}
die "Failure" if grep $_, values %hash;
print "Success";
[download]

my @array1 = ...;
my @array2 = ...;
my %hash;
@hash{@array1} = ();
delete @hash{@array2};
die "Failure" if %hash;
print "Success";
[download]

I concur with cdarke. Anytime I need to check for duplicates I always think "hash". That's not the only good use of hashes, of course. But it always seems that it is one of the areas that hashes really shine...especially for simplicity and optimized speed when you don't want to spend a lot of time trying to eek out every last microsecond of performance.

ack Albuquerque, NM

@ rkrieger - You are a Genius. The code worked liked a lightning. It was able to process 4,00,000 elements in 2 seconds...Thats indeed Almighty

Thanks a bunch once again.

Sorting algorithm couldn't help much as it took more than 20 minutes and I had to finally exit the script execution.

Perl and Perl monks are indeed making my sorting concepts strong. :)