From: rpmohn@... (Ross Mohn)
Date: 2000-12-03T06:10:05+09:00
Subject: [ruby-talk:6752] Re: Array Intersect (&) question

matz@zetabits.com (Yukihiro Matsumoto) wrote in <E142FJe-0004bS-
00@ev.netlab.zetabits.co.jp>:
>Using a hash makes it pretty fast, but it does not preserve the
>original order.  If no one requests order preservation, I will use
>hashes in &, |, and uniq.  What's your opinion?

1) I certainly would prefer the speed. I never assume that my array is in 
order, but I'm sure there are some apps that need this. Perhaps an 
intersect and an ordered_intersect?

2) The problem with this hash recipe is that if there are dups in an array, 
it will always return that dup as an intersect. Code describes this problem 
better:

  a1 = %w# x y z #      -> ["x", "y", "z"]
  a2 = %w# 1 1 y #      -> ["1", "1", "y"]
  a1 & a2               -> ["y"]
  a1.hashintersect(a2)  -> ["1", "y"]

Clearly, this hash intersect recipe is only good for arrays with unique 
elements.

3) Finally, I believe there is a logic bug in the current intersect 
functionality. I actually would expect that two arrays, both with the same 
dup elements would yield that dup in the intersection:

  a2 = %w# 1 1 y #      -> ["1", "1", "y"]
  a3 = %w# 1 y 1 z #    -> ["1", "y", "1", "z"]
  a2 & a3               -> ["1", "y"]

Whereas I believe the true intersection of a2 & a3 should be
["1", "1", "y"] . Opinions?

-- 
Ross Mohn
rpmohn@panix.com