comment on

This will find the intersection of two sets. That, by it self, is nothing new... my problem however is space vs. time. I don't want the trade-off, I want it to be fast and small whereas the CPAN modules providing the means I want are always small && slow OR huge && fast I use this to apply blacklists to address-files. The below snippet is a fully functional program. Play around with $keyLength to see increase in performance (or not)

open(local *BLACKLIST, "<blacklist");
open(local *ADDRESS, "<address");

@blacklist = <BLACKLIST>;
@address = <ADDRESS>;

my $sep = "|";
my $keyLength = 6;

my @blackListed = intersection(\@blacklist, \@address);

print "Found: " . scalar(@blackListed) . "\n";

sub intersection {
  my ( $list1, $list2 ) = @_;

  my %strings;
  my $loop;

  # turn the biggest list into a strings hash.
  # AND loop through the smallest list.
  if ( $#{$list1} > $#{list2} ) {
    %strings = makeStringsHash( \$list1 );
    $loop = \$list2;
  } else {
    %strings = makeStringsHash( \$list2 );
    $loop = \$list1;
  }

  # run through the smallest of lists
  my @intersection = ();

  # for each key remember the last position ( the strings in the hash
  # are sorted, remember? )
  my %lastPos = ();
  foreach my $entry ( @{ $$loop } ) {

    my $key = substr($entry, 0, $keyLength);

    my $pos = $lastPos{$key} || 0;
    my $tmp = index( $strings{$key}, $sep.$entry.$sep, $pos );

    # if we found it in the big-list, add it to the intersection
    if ( $tmp != -1 ) {
      push @intersection, $entry;
      $lastPos{$key} = $tmp;
    }
  }

  return @intersection
}

sub makeStringsHash {
  my ( $list ) = @_;

  my %strings = ();
  $strings{substr($_, 0, $keyLength)} .= $sep . $_ . $sep foreach ( so
+rt @$$list );

  return %strings;
}
[download]

In reply to Finding an intersection of two sets, lean and mean by Sinister

Are you posting in the right place? Check out Where do I post X? to know for sure.
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
Want more info? How to link or How to display code and escape characters are good places to start.


Clear questions and runnable code get the best and fastest answer
	PerlMonks