Ruby - 数组交集（有重复项）
Ruby - array intersection (with duplicates)
我有array(1 and 2)。我怎样才能从他们那里得到 array3？
array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
array3 = [2,2,2,3,4,8]
array1 & array2 returns [2,3,4,8]，但我需要保留重复项。
array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
a1, a2 = array1.dup, array2.dup # we’ll mutate them
loop.with_object([]) do |_, memo|
break memo if a1.empty? || a2.empty?
e = a2.delete_at(a2.index(a1.shift)) rescue nil
memo << e if e
end
#⇒ [2,2,2,3,4,8]
array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
获取样本数组中每个元素的频率：
a1_freq=Hash.new(0); a2_freq=Hash.new(0); dup_items=[];
array1.each {|a| a1_freq[a]+=1 }
array2.each {|b| a2_freq[b]+=1 }
最后比较元素是否存在于另一个数组中。如果是，则对两个样本数组中找到的公共元素进行最小计数。
a1_freq.each {|k,v| a2_freq[k] ? dup_items+=[k]*[v,a2_freq[k]].min : nil}
#dup_items=> [2, 2, 2, 3, 4, 8]
这有点冗长，但假设您指的是值在同一位置的位置：
def combine(array1, array2)
longer_array = array1.length > array2.length ? array1 : array2
intersection = []
count = 0
longer_array.each do |item|
if array1 == longer_array
looped_array = array2
else
looped_array = array1
end
if item == looped_array[count]
intersection.push(item)
end
count +=1
end
print intersection
end
array_1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array_2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
combine(array_1, array_2)
我只是想指出，我不知道您是如何到达数组 3 的，因为所有三个数组的索引位置 3 都不同：
array_1[3] = 2
array_2[3] = 3
array_3[3] = 3
(array1 & array2).flat_map { |n| [n]*[array1.count(n), array2.count(n)].min }
#=> [2,2,2,3,4,8]
步骤：
a = array1 & array2
#=> [2, 3, 4, 8]
a（2）的第一个元素被传递给块并赋值给块变量：
n = 2
并进行分块计算：
[2]*[array1.count(2), array2.count(2)].min
#=> [2]*[4,3].min
#=> [2]*3
#=> [2,2,2]
所以 2 映射到 [2,2,2]。 a 的其余三个元素的计算类似。因为我正在使用 flat_map，这个 returns [2,2,2,3,4,8].
您是否记不起 Enumerable#flat_map differs from Enumerable#map？假设我使用了 map 而不是 flat_map。然后
a.map { |n| [n]*[array1.count(n), array2.count(n)].min }
#=> [[2, 2, 2], [3], [4], [8]]
flat_map 只是在每个数组前面放一个 splat：
[*[2, 2, 2], *[3], *[4], *[8]]
#=> [2, 2, 2, 3, 4, 8]
如果数组 array1 和 array2 很大并且效率是一个问题，我们可以做一些 O(N) 的预处理：
def cnt(arr)
arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
end
cnt1 = cnt(array1)
#=> {2=>4, 3=>2, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1}
cnt2 = cnt(array2)
#=> {2=>3, 3=>1, 4=>4, 8=>2, 0=>3}
(array1 & array2).flat_map { |n| [n]*[cnt1[n], cnt2[n]].min }
#=> [2,2,2,3,4,8]
我将尝试以这种方式达到预期结果：
array1, array2 = [array1, array2].sort_by(&:size)
arr_copy = array2.dup
array1.each.with_object([]) do |el, arr|
index = arr_copy.find_index(el)
arr << arr_copy.slice!(index) if index
end
# => [2, 2, 2, 3, 4, 8]
这很有趣； Cary 的 flat_map 解决方案特别聪明。这是在 each_with_object:
的帮助下使用常规旧 map 的另一种单线
array1.each_with_object(array2.dup).map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact
#=> [2,2,2,3,4,8]
这里的大部分复杂性涉及用于为 map 提供足够信息以完成任务的在线体操：
#
# we want to duplicate array2 since we'll be
# mutating it to track duplicates
# \ array1 array2
# \ value copy
# \ \ /
array1.each_with_object(array2.dup).map{|v,t| ... }
# | /
# Enumerator for array1 Iterate over
# with a copy of array2 Enumerator with map
我们可以使用 each_with_object 为 array1 提供一个枚举器，它也使我们的方法链可以访问 array2 的副本。然后 Map 可以遍历 each_with_object 枚举器（它引用 array1），将每个值加载到局部变量 v 并将我们的 array2 复制到局部变量 t。从那里：
# map the value IF...
# / it exists in and we were able to
# / our array2 copy remove it from our copy
# / | |
map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact
# | \ \ |
# array1 \ \ dump nils
# value array2 \
# copy load index position into temporary variable l
我们遍历 array1 的每个值并搜索该值是否存在于 array2 中（通过 t）。如果它存在，我们从 array2 的副本中删除该值的第一次出现，并将该值 map 添加到我们的结果数组中。
请注意 t.slice!(t.index(v)) 之前的 t.index(v) 检查用作短路保护，以防值不存在于我们的数组 2 副本 t 中。我们还使用了一个内联技巧，将索引值分配给局部变量 l 此处：(l = t.index v) 因此我们可以在后续的布尔检查中引用 l：t.slice!(l)。
最后，因为只要 array2 中不存在 array1 值，此方法就会映射 nil 值，所以我们 compact 删除 nils 的结果。
对于那些好奇的人，这里有一些迄今为止提出的解决方案的基准测试。首先，这里是对示例数组执行 100,000 次操作的时钟速度：
Cary: 1.050000 0.010000 1.060000 ( 1.061217)
Cary+: 1.580000 0.010000 1.590000 ( 1.603645)
Cam: 0.550000 0.010000 0.560000 ( 0.552062)
Mudasobwa: 2.540000 0.050000 2.590000 ( 2.610395)
Sergii: 0.660000 0.000000 0.660000 ( 0.665408)
Sahil: 1.750000 0.010000 1.760000 ( 1.769624)
#Tommy: 0.290000 0.000000 0.290000 ( 0.290114)
如果我们扩展测试数组以容纳 10000 个具有高交集度的整数...
array1 = array2 = []
10000.times{ array1 << rand(10) }
10000.times{ array2 << rand(10) }
循环100次，简单循环解决方案（Sahil）开始脱颖而出。 Cary 的解决方案也很有效，尤其是在预处理方面：
user system total real
Cary: 1.590000 0.020000 1.610000 ( 1.615798)
Cary+: 0.870000 0.010000 0.880000 ( 0.879331)
Cam: 6.680000 0.090000 6.770000 ( 6.838829)
Mudasobwa: 6.740000 0.080000 6.820000 ( 6.898394)
Sergii: 6.760000 0.100000 6.860000 ( 6.962025)
Sahil: 0.740000 0.030000 0.770000 ( 0.785975)
#Tommy: 0.430000 0.010000 0.440000 ( 0.446482)
对于大小为 1/10 且具有 1000 个整数和 低交集度 的数组，但是...
array1 = array2 = []
1000.times{ array1 << rand(10000) }
1000.times{ array2 << rand(10000) }
当我们循环 10 次时，flat_map 解决方案变平...除非我们使用预处理 (Cary+)：
user system total real
Cary: 135.400000 0.700000 136.100000 (137.123393)
Cary+: 0.270000 0.010000 0.280000 ( 0.268255)
Cam: 0.670000 0.000000 0.670000 ( 0.676438)
Mudasobwa: 0.670000 0.010000 0.680000 ( 0.684088)
Sergii: 0.660000 0.010000 0.670000 ( 0.673881)
Sahil: 1.970000 2.130000 4.100000 ( 4.121759)
#Tommy: 0.050000 0.000000 0.050000 ( 0.045970)
这是基准测试的要点：https://gist.github.com/camerican/139463b4bd9e0fd89424377931042ce4
看起来你所拥有的并不是真正的数组，它们是 multisets 或 bags.
编程中有一个通用规则：如果选择正确的数据表示，算法就会变得更简单。
因此，如果您使用多重集而不是数组，您的问题将变得微不足道，因为您要查找的实际上只是两个多重集的交集。
不幸的是，核心库或标准库中没有多重集实现，但网络上有几个多重集 gem。例如，有 multimap gem, which also includes a multiset. Unfortunately, it needs a little bit of love and care, since it uses a C extension that only works until YARV 2.2. There is also the multiset gem. You can also find some multiset implementations on Stack Overflow or Code Review.SE.
require 'multiset'
multiset1 = Multiset.new(array1)
#=> #<Multiset:#4 2, #2 3, #1 4, #1 5, #1 6, #1 7, #1 8, #1 9>
multiset2 = Multiset.new(array2)
#=> #<Multiset:#3 2, #1 3, #4 4, #2 8, #3 0>
multiset3 = multiset1 & multiset2
#=> #<Multiset:#3 2, #1 3, #1 4, #1 8>
就个人而言，我不太喜欢 inspect 输出，但我们可以看到发生了什么并且结果是正确的：multiset3 包含 3 × 2 , 1 × 3, 1 × 4, 1 × 8.
如果你真的需要 Array 的结果，你可以使用 Multiset#to_a:
multiset3.to_a
#=> [2, 2, 2, 3, 4, 8]
multiset3.to_a == array3
#=> true
我有array(1 and 2)。我怎样才能从他们那里得到 array3？
array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
array3 = [2,2,2,3,4,8]
array1 & array2 returns [2,3,4,8]，但我需要保留重复项。
array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
a1, a2 = array1.dup, array2.dup # we’ll mutate them
loop.with_object([]) do |_, memo|
break memo if a1.empty? || a2.empty?
e = a2.delete_at(a2.index(a1.shift)) rescue nil
memo << e if e
end
#⇒ [2,2,2,3,4,8]
array1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
获取样本数组中每个元素的频率：
a1_freq=Hash.new(0); a2_freq=Hash.new(0); dup_items=[];
array1.each {|a| a1_freq[a]+=1 }
array2.each {|b| a2_freq[b]+=1 }
最后比较元素是否存在于另一个数组中。如果是，则对两个样本数组中找到的公共元素进行最小计数。
a1_freq.each {|k,v| a2_freq[k] ? dup_items+=[k]*[v,a2_freq[k]].min : nil}
#dup_items=> [2, 2, 2, 3, 4, 8]
这有点冗长，但假设您指的是值在同一位置的位置：
def combine(array1, array2)
longer_array = array1.length > array2.length ? array1 : array2
intersection = []
count = 0
longer_array.each do |item|
if array1 == longer_array
looped_array = array2
else
looped_array = array1
end
if item == looped_array[count]
intersection.push(item)
end
count +=1
end
print intersection
end
array_1 = [2,2,2,2,3,3,4,5,6,7,8,9]
array_2 = [2,2,2,3,4,4,4,4,8,8,0,0,0]
combine(array_1, array_2)
我只是想指出，我不知道您是如何到达数组 3 的，因为所有三个数组的索引位置 3 都不同：
array_1[3] = 2
array_2[3] = 3
array_3[3] = 3
(array1 & array2).flat_map { |n| [n]*[array1.count(n), array2.count(n)].min }
#=> [2,2,2,3,4,8]
步骤：
a = array1 & array2
#=> [2, 3, 4, 8]
a（2）的第一个元素被传递给块并赋值给块变量：
n = 2
并进行分块计算：
[2]*[array1.count(2), array2.count(2)].min
#=> [2]*[4,3].min
#=> [2]*3
#=> [2,2,2]
所以 2 映射到 [2,2,2]。 a 的其余三个元素的计算类似。因为我正在使用 flat_map，这个 returns [2,2,2,3,4,8].
您是否记不起 Enumerable#flat_map differs from Enumerable#map？假设我使用了 map 而不是 flat_map。然后
a.map { |n| [n]*[array1.count(n), array2.count(n)].min }
#=> [[2, 2, 2], [3], [4], [8]]
flat_map 只是在每个数组前面放一个 splat：
[*[2, 2, 2], *[3], *[4], *[8]]
#=> [2, 2, 2, 3, 4, 8]
如果数组 array1 和 array2 很大并且效率是一个问题，我们可以做一些 O(N) 的预处理：
def cnt(arr)
arr.each_with_object(Hash.new(0)) { |e,h| h[e] += 1 }
end
cnt1 = cnt(array1)
#=> {2=>4, 3=>2, 4=>1, 5=>1, 6=>1, 7=>1, 8=>1, 9=>1}
cnt2 = cnt(array2)
#=> {2=>3, 3=>1, 4=>4, 8=>2, 0=>3}
(array1 & array2).flat_map { |n| [n]*[cnt1[n], cnt2[n]].min }
#=> [2,2,2,3,4,8]
我将尝试以这种方式达到预期结果：
array1, array2 = [array1, array2].sort_by(&:size)
arr_copy = array2.dup
array1.each.with_object([]) do |el, arr|
index = arr_copy.find_index(el)
arr << arr_copy.slice!(index) if index
end
# => [2, 2, 2, 3, 4, 8]
这很有趣； Cary 的 flat_map 解决方案特别聪明。这是在 each_with_object:
map 的另一种单线
array1.each_with_object(array2.dup).map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact
#=> [2,2,2,3,4,8]
这里的大部分复杂性涉及用于为 map 提供足够信息以完成任务的在线体操：
#
# we want to duplicate array2 since we'll be
# mutating it to track duplicates
# \ array1 array2
# \ value copy
# \ \ /
array1.each_with_object(array2.dup).map{|v,t| ... }
# | /
# Enumerator for array1 Iterate over
# with a copy of array2 Enumerator with map
我们可以使用 each_with_object 为 array1 提供一个枚举器，它也使我们的方法链可以访问 array2 的副本。然后 Map 可以遍历 each_with_object 枚举器（它引用 array1），将每个值加载到局部变量 v 并将我们的 array2 复制到局部变量 t。从那里：
# map the value IF...
# / it exists in and we were able to
# / our array2 copy remove it from our copy
# / | |
map{|v,t| v if (l = t.index v) && t.slice!(l) }.compact
# | \ \ |
# array1 \ \ dump nils
# value array2 \
# copy load index position into temporary variable l
我们遍历 array1 的每个值并搜索该值是否存在于 array2 中（通过 t）。如果它存在，我们从 array2 的副本中删除该值的第一次出现，并将该值 map 添加到我们的结果数组中。
请注意 t.slice!(t.index(v)) 之前的 t.index(v) 检查用作短路保护，以防值不存在于我们的数组 2 副本 t 中。我们还使用了一个内联技巧，将索引值分配给局部变量 l 此处：(l = t.index v) 因此我们可以在后续的布尔检查中引用 l：t.slice!(l)。
最后，因为只要 array2 中不存在 array1 值，此方法就会映射 nil 值，所以我们 compact 删除 nils 的结果。
对于那些好奇的人，这里有一些迄今为止提出的解决方案的基准测试。首先，这里是对示例数组执行 100,000 次操作的时钟速度：
Cary: 1.050000 0.010000 1.060000 ( 1.061217)
Cary+: 1.580000 0.010000 1.590000 ( 1.603645)
Cam: 0.550000 0.010000 0.560000 ( 0.552062)
Mudasobwa: 2.540000 0.050000 2.590000 ( 2.610395)
Sergii: 0.660000 0.000000 0.660000 ( 0.665408)
Sahil: 1.750000 0.010000 1.760000 ( 1.769624)
#Tommy: 0.290000 0.000000 0.290000 ( 0.290114)
如果我们扩展测试数组以容纳 10000 个具有高交集度的整数...
array1 = array2 = []
10000.times{ array1 << rand(10) }
10000.times{ array2 << rand(10) }
循环100次，简单循环解决方案（Sahil）开始脱颖而出。 Cary 的解决方案也很有效，尤其是在预处理方面：
user system total real
Cary: 1.590000 0.020000 1.610000 ( 1.615798)
Cary+: 0.870000 0.010000 0.880000 ( 0.879331)
Cam: 6.680000 0.090000 6.770000 ( 6.838829)
Mudasobwa: 6.740000 0.080000 6.820000 ( 6.898394)
Sergii: 6.760000 0.100000 6.860000 ( 6.962025)
Sahil: 0.740000 0.030000 0.770000 ( 0.785975)
#Tommy: 0.430000 0.010000 0.440000 ( 0.446482)
对于大小为 1/10 且具有 1000 个整数和 低交集度 的数组，但是...
array1 = array2 = []
1000.times{ array1 << rand(10000) }
1000.times{ array2 << rand(10000) }
当我们循环 10 次时，flat_map 解决方案变平...除非我们使用预处理 (Cary+)：
user system total real
Cary: 135.400000 0.700000 136.100000 (137.123393)
Cary+: 0.270000 0.010000 0.280000 ( 0.268255)
Cam: 0.670000 0.000000 0.670000 ( 0.676438)
Mudasobwa: 0.670000 0.010000 0.680000 ( 0.684088)
Sergii: 0.660000 0.010000 0.670000 ( 0.673881)
Sahil: 1.970000 2.130000 4.100000 ( 4.121759)
#Tommy: 0.050000 0.000000 0.050000 ( 0.045970)
这是基准测试的要点：https://gist.github.com/camerican/139463b4bd9e0fd89424377931042ce4
看起来你所拥有的并不是真正的数组，它们是 multisets 或 bags.
编程中有一个通用规则：如果选择正确的数据表示，算法就会变得更简单。
因此，如果您使用多重集而不是数组，您的问题将变得微不足道，因为您要查找的实际上只是两个多重集的交集。
不幸的是，核心库或标准库中没有多重集实现，但网络上有几个多重集 gem。例如，有 multimap gem, which also includes a multiset. Unfortunately, it needs a little bit of love and care, since it uses a C extension that only works until YARV 2.2. There is also the multiset gem. You can also find some multiset implementations on Stack Overflow or Code Review.SE.
require 'multiset'
multiset1 = Multiset.new(array1)
#=> #<Multiset:#4 2, #2 3, #1 4, #1 5, #1 6, #1 7, #1 8, #1 9>
multiset2 = Multiset.new(array2)
#=> #<Multiset:#3 2, #1 3, #4 4, #2 8, #3 0>
multiset3 = multiset1 & multiset2
#=> #<Multiset:#3 2, #1 3, #1 4, #1 8>
就个人而言，我不太喜欢 inspect 输出，但我们可以看到发生了什么并且结果是正确的：multiset3 包含 3 × 2 , 1 × 3, 1 × 4, 1 × 8.
如果你真的需要 Array 的结果，你可以使用 Multiset#to_a:
multiset3.to_a
#=> [2, 2, 2, 3, 4, 8]
multiset3.to_a == array3
#=> true