Re: Finding an intersection of two sets, lean and mean

Uhh ... you do realize that you just implemented a very rudimentary hash table in Perl using ... wait for it ... hashes! Except, you don't handle collisions. What's wrong with:

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

  my %hash;
  @hash{@$list1} = undef;

  my @intersection = grep { exists $hash{$_} } @$list2;

  return @intersection
}
[download]

Update: Fixed mistake in my code (map -> grep) Compare mine to yours and I think you'll notice a difference.

My criteria for good software:

Does it work?
Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Comment on Re: Finding an intersection of two sets, lean and mean Download Code

Replies are listed 'Best First'.
Re^2: Finding an intersection of two sets, lean and mean by Sinister (Friar) on Jun 29, 2005 at 14:31 UTC
Allas, this doesn't work... I tried this in my test-set and the result is that @intersection = @$list2, which is _not_ true. I can't seem to figure out why this happens yet. Your example should be perfectly legal. I know. It is only much slower	[reply]
Re^3: Finding an intersection of two sets, lean and mean by Sinister (Friar) on Jun 29, 2005 at 14:52 UTC
Found it! Perhaps you meant 'grep' instead of 'map' ?? ;-> This gives a different result set then mine (larger in every case), but this could be a problem with my code... It is faster, untill the sets become a teeny weeny bit bigger (eg: +5M lines)	[reply]
Re^4: Finding an intersection of two sets, lean and mean by dragonchild (Archbishop) on Jun 29, 2005 at 15:00 UTC
Yes, grep is the correct operator, not map. See - I did bork my code. :-) As for the +5M lines thing - that becomes a function of your available RAM. Your string solution will hit the same limit, but at around 20-30M (if 5M is your limit with hashes). Note, your code to build the hash string will bomb faster than your code to iterate through it because you use foreach instead of while to iterate through the list. This creates a copy of the list you're foreach'ing through whereas while does not. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re^3: Finding an intersection of two sets, lean and mean by dragonchild (Archbishop) on Jun 29, 2005 at 14:36 UTC
if you;re going to tell me that my code is wrong, show me why. That way, I can either fix my code or demonstrate how you misused it (or both). Don't just say "Uh, your code suxx0rs" and walk away. That's not how OSS works. My criteria for good software: Does it work? Can someone else come in, make a change, and be reasonably certain no bugs were introduced?	[reply]
Re^4: Finding an intersection of two sets, lean and mean by Sinister (Friar) on Jun 29, 2005 at 14:42 UTC
Oh, I am sorry you spilled your drink while reading the first line of my reply and never got passed that same line. Let me quote myself: > I can't seem to figure out why this happens yet. > Your example should be perfectly legal. I know.	[reply]
Re^5: Finding an intersection of two sets, lean and mean by dragonchild (Archbishop) on Jun 29, 2005 at 14:57 UTC


go ahead... be a heretic
	PerlMonks