in reply to Combining arrays with grep/unless?

ow, O(N2) time!

If the items in @group1 and @group2 are strings or can be represented by an id, it can be done in O(N) time. 

my %seen;
my @all = grep !$seen{$_}++, @group1, @group2;

[download]

Update:

If the items in @group1 and @group2 can be compared, it can be done in O(N log2 N) time (although order is lost). 

my @all;
my @group1_s = sort compare_func @group1;
my @group2_s = sort compare_func @group2;
while (@group1_s && @group2_s) {
   my $cmp = compare_func($group1_s[0], $group2_s[0]);
   if    ($cmp < 0) { push(@all, shift(@group1_s)); }
   elsif ($cmp > 0) { push(@all, shift(@group2_s)); }
   else             { push(@all, scalar(shift(@group1_s), shift(@group
+2_s))); }
}
push(@all, @group1_s, @group2_s);

[download]

Replies are listed 'Best First'.
Re^2: Combining arrays with grep/unless?
by polettix (Vicar) on Feb 10, 2007 at 00:13 UTC
    The first approach isn't O(N) because of the lookup in the hash. Update: for the impatients that don't want to look further in the subthread, this comment ended up to be incorrect.

    Flavio
    perl -ple'$_=reverse' <<<ti.xittelop@oivalf

    Don't fool yourself.
[reply]

      True, and the OP's isn't really O(N2) either. Both should factor in the length of the string. Both should factor the growth of the array/hash. Mine should also factor in bucket collisions when talking about worst case.

      So, the OP's is O(N2 * L * O(Growth(N))) and mine is O(N * L * O(Growth(N))). I chose to ignore the common (and thus irrelevant) factor, even if accuracy suffered a little.

[reply]
        I think that you're still missing the lookup into the hash, which isn't a constant time operation and can't be factored out because the OP doesn't have it. Since the best you can do with such a lookup is O(log(N)), IMHO the complexity in your case is at least O(N * log(N)).

        Flavio
        perl -ple'$_=reverse' <<<ti.xittelop@oivalf

        Don't fool yourself.
[reply]

In Section Seekers of Perl Wisdom