[plug] Perl: Intersection of two arrays?

Trevor Phillips T.Phillips at murdoch.edu.au
Wed Jun 25 12:01:30 WST 2003


On Tuesday 24 June 2003 17:46, Simon Newton wrote:
> Use a hash instead of the nested for loop:
> http://www.perldoc.com/perl5.6/pod/perlfaq4.html#How-do-I-compute-the-diffe
>rence-of-two-arrays---How-do-I-compute-the-intersection-of-two-arrays-

I was trying to avoid hashes, since they have their own overhead. ^_^

Interestingly, I benchmarked using nested greps, nested foreach's (with jump 
out on match), nested foreach's (with jump out and element removal) and the 
recommended hash count method. The nested foreach came out the fastest, 
followed by the Hash test and one of the Nested grep tests (it's faster 
depending which array is nested internally, based on size). 

Unsuprisingly, the Foreach with the element removal was the slowest. The idea 
was, once you match an element in the inner array, removing that elements 
will reduce the number of checks - but the overhead on rebuilding the array 
is way too large to make it efficient.

These tests were with a set of 8 elements vs a set of 14 elements. Increasing 
the 14 element set to 25 increased the lead Foreach had over the others. Hash 
and Grep were still comparable.

Reversing the data sets, Foreach became the slowest - to be faster, the larger 
array needs to be inside.

As the number of elements grows, the Hash method becomes the most efficient.

Although I'm dealing with relatively small sets of data, I might just go with 
the Hash method - at least it's a consistent performance hit, even if other 
methods are faster under certain circumstances...

-- 
. Trevor Phillips             -           http://jurai.murdoch.edu.au/ . 
: Web Technical Administrator     -          T.Phillips at murdoch.edu.au : 
| IT Services                        -              Murdoch University | 
 >--------------------------------------------------------------------<
| On nights such as this, evil deeds are done. And good deeds, of     /
| course. But mostly evil, on the whole.                             /
 \      -- (Terry Pratchett, Wyrd Sisters)                          /



More information about the plug mailing list