Q:

Improve performance of perl code that finds custom-intersection of two lists

I wrote the following perl code to return an intersection-like list for any two input lists, provided $returnintersection is true. Otherwise, it will return any one common element, and if there is none, will return 0.
By intersection-like, i'm referring to wild card matches - 123* from one list will match 12345 from the other list.
Here is an example of input and corresponding output.
getintersection (
 ['123*', '999', 'V890', '871'],
 ['10001', '8789', '999', '1234', 'V89*'], 
 1 
)
will return
('999', 'V890', '1234')

I'd like to know if i can write it in a way that will perform better ? I'm sure the algorithm ere is not the best one out there. Anything that will help bring its complexity down will be appreciated ! Its performance is crucial as it is a very commonly called routine. (Performance => speed, assuming that either list could contain anywhere between 1 and 3000 elements)
Code -
    sub getintersection {
        my ($l1, $l2, $returnintersection) = @_;
        if (!$l1 || !$l2) {
                return $returnintersection ? undef : 0;
        }
        my ($small, $large);
        if (scalar @$l1 > scalar @$l2 ) {
                ($small, $large) = ($l2, $l1);
        }
        else {
                ($small, $large) = ($l1, $l2);
        }

        my (%lhash, %l_starred, %s_starred, @intersection);
        foreach my $l (@$large) {
                $lhash{$l} = 1;
                if ($l =~ m/^(.+)\*$/) {
                        $l_starred{$1} = 1;
                }
        }
        foreach my $s (@$small) {
                if ($lhash{$s}) {
                        return $s if (!$returnintersection);
                        push @intersection, $s;
                }
                else {
                        foreach my $k (keys %l_starred) {
                                if ($s =~ /^$k/) {
                                        return $s if (!$returnintersection);
                                        push @intersection, $s;
                                }
                        }
                }
                if ($s =~ m/^(.+)\*$/) {
                        $s_starred{$s} = 1;
                }
        }
        foreach my $s (keys %s_starred) {
                foreach my $l (@$large) {
                        if ($l =~ /^$s/) {
                                return $l if (!$returnintersection);
                                push @intersection, $l;
                        }
                }
        }

        return $returnintersection ? @intersection : scalar @intersection;
}

A:

As I read it, your implementation doesn't benefit from distinguishing between a small and a large set. Even so, what really matters is which set has the largest number of starred elements because they can't be dealt with in linear complexity.
First off, take a look at the possible combinations of non-matches: 
Set 1       | Set 2
Normal      | None
Starred     | None
None        | Normal
None        | Starred

Then the possible combinations of matches:
Normal      | Normal
Starred     | Normal
Normal      | Starred
Starred     | Starred

It is obvious that anything that can be matched using hash lookups should be done first because the complexity is linear, so first part of the algorithm should be:
for all elements in set1
    if element is normal, put in %normal_1_lookup
    otherwise put in @star_1
for all elements in set2
    if element is normal, put in %normal_2_lookup
    otherwise put in @star_2

for intersection of %normal_1_lookup, %normal_2_lookup
    put element in result
    delete element from %normal_1_lookup and %normal_2_lookup

You can optimize this by folding the last loop that calculates the intersection into the second loop that calculates %normal_2_lookup, but I'm writing it like this to make it more readable.
Now all the light lifting is out of the way, the elements that already matched have been deleted and you don't have to iterate anything to know which elements are stars and which aren't.
for all elements is @star_1
    for all elements in %normal_2_lookup
        if star_1 element matches normal_2 element
            put normal_2 element in result set
            delete normal_2 element from %normal_2_lookup

Now repeat switching the two sets.
Finally you can add a matching of @star_1 against @star_2, but I am unsure if that is intended.
This should cut down the complexity to o(s_1 * n_2 + s_2 * n_1) (add s_1 * s_2 if you want to match star elemnts from both sets) in stead of what seems to be o(n_1 * n_2).
If you want to optimize even further, you could use Tries on all the elements in one of the sets to do the matching.

