Ruby 数组值的可能组合 - 性能
Ruby possible combination of array values - performance
我需要根据条件快速确定数组中元素的可能 uniq 组合。
它们具有以下结构：
[[id,parent_id]]
我对较小的数组没有问题。如果所有 parent_ids 都是唯一的。示例：
a = (1..6).to_a.map{ |a| [a,a] }
=> [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6]]
a.combination(3).size # => 20
立即回答。
如果我有重复出现的 ID parent_ids，我仍然可以使用组合并遍历所有组合。
a = (1..7).to_a.map{ |a| [a,a] };a[6] = [7,6]
=> [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 6]]
a.combination(3).size # => 35
valid_combos = a.combination(3).to_a.select { |c| c.map(&:last).uniq.size == c.size }.size # => 30
这在小型阵列上仍然很快。但是，如果数组有 33 个条目，其中 1 个重复出现 parent_id，我将不得不检查 1166803110 组合。这很慢。当然可以。
欢迎任何有关如何快速有效地解决此问题的想法或提示。
我喜欢数组的组合方法class。但我也会使用哈希或集合。
也可能有这样的数组：
a = [[1, 1], [2, 1], [3, 1], [4, 2], [5, 2], [6, 2], [7, 3], [8, 3]]
a.combination(3).size #=> 56
但只有 18 个 "valid"。
感谢任何帮助。
编辑：
有效输入没有重复出现parent_ids:
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]
每个 4 个组合的有效输出（5 个 uniq 组合）：
[[[1, 1], [2, 2], [3, 3], [4, 4]], [[1, 1], [2, 2], [3, 3], [5, 5]], [[1, 1], [2, 2], [4, 4], [5, 5]], [[1, 1], [3, 3], [4, 4], [5, 5]], [[2, 2], [3, 3], [4, 4], [5, 5]]]
重复出现有效输入 1 parent_ids:
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,5]]
每个 4 个组合的有效输出（9 个 uniq 组合）：
[[[1, 1], [2, 2], [3, 3], [4, 4]], [[1, 1], [2, 2], [3, 3], [5, 5]], [[1, 1], [2, 2], [3, 3], [6, 5]], [[1, 1], [2, 2], [4, 4], [5, 5]], [[1, 1], [2, 2], [4, 4], [6, 5]], [[1, 1], [3, 3], [4, 4], [5, 5]], [[1, 1], [3, 3], [4, 4], [6, 5]], [[2, 2], [3, 3], [4, 4], [5, 5]], [[2, 2], [3, 3], [4, 4], [6, 5]]]
这些是无效组合 [5,5] 和 [6,5] 是不允许的：
[[[1, 1], [2, 2], [5, 5], [6, 5]], [[1, 1], [3, 3], [5, 5], [6, 5]], [[1, 1], [4, 4], [5, 5], [6, 5]], [[2, 2], [3, 3], [5, 5], [6, 5]], [[2, 2], [4, 4], [5, 5], [6, 5]], [[3, 3], [4, 4], [5, 5], [6, 5]]]
如果我理解正确，您需要所有可能的 ID 组合，其中 ID 不共享父 ID。我尝试了一些不同的东西，只是为了好玩，不知道性能是否会提高。
x = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,5]]
首先，让我们翻转缩小它。
hash = x.reduce({}) {|hash, pair| (hash[pair.last] ||= []).push pair.first}
#=> {1=>[1], 2=>[2], 3=>[3], 4=>[4], 5=>[5, 6]}
现在我们得到父 ID 的所有可能组合。
parents = hash.keys.combination(4).to_a
#=> [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]
现在我们将每个父 ID 映射到它的子 ID。
children = parents.map do |array|
array.map {|parent| hash[parent]}
end
#=> [[[1], [2], [3], [4]], [[1], [2], [3], [5, 6]], [[1], [2], [4], [5, 6]], [[1], [3], [4], [5, 6]], [[2], [3], [4], [5, 6]]]
此时我们已经深入了解数组了。现在，我们取每个子数组的乘积来得到所有可能的组合，我们甚至不需要对它们进行 uniq。
children.map {|array| array.first.product *array.drop(1)}.flatten(1)
#=> [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 3, 4, 5], [1, 3, 4, 6], [2, 3, 4, 5], [2, 3, 4, 6]]
现在您拥有所有 ID 组合，如果您仍然需要使用 hash table.
相反的方法，可以使用它们来查找父 ID
性能怎么样？我以 运行 this file.
为基准
有 50 个条目，25 个重复，以及 4 个的组合：
3957124
Original: 8.719000 0.110000 8.829000 ( 8.860909)
3957124
Simons: 4.875000 0.094000 4.969000 ( 6.458309)
所以理论上看起来更快。但是，有 125 个条目，25 个重复，以及 4 的组合：
9811174
Original: 22.875000 0.281000 23.156000 ( 23.213483)
9811174
Simons: 20.703000 0.391000 21.094000 ( 21.232167)
这并没有快多少。这是因为对于如此多的组合，Ruby 花费大部分时间进行内存分配（尝试在任务管理器或 top 中查看），在 Ruby 中是 dog-慢。预先分配内存并没有任何有用的方法，所以超过某个点你就处于硬限制。
但这只会发生，因为您强制 Ruby 一次将所有数组项收集在一起。如果您的特定用例允许您单独处理每个组合，则可以避免大部分内存分配。通过对每个子数组 (this file) 调用 yield：
9811174
Simons: 8.485000 0.000000 8.485000 ( 8.476653)
快多了。您还将观察到内存使用量保持不变。 It's still gonna take a while though。然而，如果你有多个核心，你原则上可以并行化，因为一旦你有了哈希，每个组合都可以独立于其他组合进行处理。我会留给你试试:)
您可以按如下方式进行。
代码
def combos(pairs, group_size)
pairs.group_by(&:last).
values.
combination(group_size).
flat_map { |a| a.shift.product(*a) }
end
例子
pairs = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,5]]
combos(pairs, 4)
#=> [[[1, 1], [2, 2], [3, 3], [4, 4]],
# [[1, 1], [2, 2], [3, 3], [5, 5]],
# [[1, 1], [2, 2], [3, 3], [6, 5]],
# [[1, 1], [2, 2], [4, 4], [5, 5]],
# [[1, 1], [2, 2], [4, 4], [6, 5]],
# [[1, 1], [3, 3], [4, 4], [5, 5]],
# [[1, 1], [3, 3], [4, 4], [6, 5]],
# [[2, 2], [3, 3], [4, 4], [5, 5]],
# [[2, 2], [3, 3], [4, 4], [6, 5]]]
combos(pairs, 5)
#=> [[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]],
# [[1, 1], [2, 2], [3, 3], [4, 4], [6, 5]]]
combos(pairs, 1).size #=> 6
combos(pairs, 2).size #=> 14
combos(pairs, 3).size #=> 16
combos(pairs, 4).size #=> 9
combos(pairs, 5).size #=> 2
说明
对于示例中使用的数组pairs，以及
group_size = 4
我们执行以下计算。首先，我们按每对的最后一个元素对对的元素进行分组（即 parent_id）：
h = pairs.group_by(&:last)
#=> {1=>[[1, 1]], 2=>[[2, 2]], 3=>[[3, 3]], 4=>[[4, 4]], 5=>[[5, 5], [6, 5]]}
我们只需要这个散列中的值：
b = h.values
#=> [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]], [[5, 5], [6, 5]]]
我们现在得到 b:
元素的组合
enum = b.combination(group_size)
#=> b.combination(4)
#=> #<Enumerator: [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]],
# [[5, 5], [6, 5]]]:combination(4)>
我们可以通过将其转换为数组来查看此枚举器的 (5) 个元素：
enum.to_a
#=> [[[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]]],
# [[[1, 1]], [[2, 2]], [[3, 3]], [[5, 5], [6, 5]]],
# [[[1, 1]], [[2, 2]], [[4, 4]], [[5, 5], [6, 5]]],
# [[[1, 1]], [[3, 3]], [[4, 4]], [[5, 5], [6, 5]]],
# [[[2, 2]], [[3, 3]], [[4, 4]], [[5, 5], [6, 5]]]]
最后一步是将 enum 的每个元素映射到其元素的乘积（enum 的每个元素都是对数组）。我们使用 Enumerable#flat_map 因此我们不必随后进行任何展平：
enum.flat_map { |a| a.shift.product(*a) }
returns group_size = 4.
示例中给出的数组
让我们更仔细地看看上一条语句中发生了什么：
enum1 = enum.flat_map
#=> #<Enumerator: #<Enumerator: [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]],
# [[5, 5], [6, 5]]]:combination(4)>:flat_map>
您可能想将 enum1 视为 "compound enumerator"。 enum1 的元素通过 Enumerator#each (which will call Array#each) 传递到它的块中，并分配给块变量 a。让我们看一下传递给块的第二个值。
跳过第一个：
a = enum1.next
#=> [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]]]
第二个通过：
a = enum1.next
#=> [[[1, 1]], [[2, 2]], [[3, 3]], [[5, 5], [6, 5]]]
我们取这四个数组的乘积如下：
a[0].product(a[1], a[2], a[3])
#=> [[[1, 1], [2, 2], [3, 3], [5, 5]],
# [[1, 1], [2, 2], [3, 3], [6, 5]]]
我们也可以这样写：
a[0].product(*a[1..-1])
或者，就像我所做的那样：
a.shift.product(*a)
请注意，在最后一个表达式中，*a 的 a 是执行 a.shift 后 a 的剩余部分。
我需要根据条件快速确定数组中元素的可能 uniq 组合。
它们具有以下结构：
[[id,parent_id]]
我对较小的数组没有问题。如果所有 parent_ids 都是唯一的。示例：
a = (1..6).to_a.map{ |a| [a,a] }
=> [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6]]
a.combination(3).size # => 20
立即回答。
如果我有重复出现的 ID parent_ids，我仍然可以使用组合并遍历所有组合。
a = (1..7).to_a.map{ |a| [a,a] };a[6] = [7,6]
=> [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6, 6], [7, 6]]
a.combination(3).size # => 35
valid_combos = a.combination(3).to_a.select { |c| c.map(&:last).uniq.size == c.size }.size # => 30
这在小型阵列上仍然很快。但是，如果数组有 33 个条目，其中 1 个重复出现 parent_id，我将不得不检查 1166803110 组合。这很慢。当然可以。
欢迎任何有关如何快速有效地解决此问题的想法或提示。
我喜欢数组的组合方法class。但我也会使用哈希或集合。
也可能有这样的数组：
a = [[1, 1], [2, 1], [3, 1], [4, 2], [5, 2], [6, 2], [7, 3], [8, 3]]
a.combination(3).size #=> 56
但只有 18 个 "valid"。
感谢任何帮助。
编辑：
有效输入没有重复出现parent_ids:
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]]
每个 4 个组合的有效输出（5 个 uniq 组合）：
[[[1, 1], [2, 2], [3, 3], [4, 4]], [[1, 1], [2, 2], [3, 3], [5, 5]], [[1, 1], [2, 2], [4, 4], [5, 5]], [[1, 1], [3, 3], [4, 4], [5, 5]], [[2, 2], [3, 3], [4, 4], [5, 5]]]
重复出现有效输入 1 parent_ids:
[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,5]]
每个 4 个组合的有效输出（9 个 uniq 组合）：
[[[1, 1], [2, 2], [3, 3], [4, 4]], [[1, 1], [2, 2], [3, 3], [5, 5]], [[1, 1], [2, 2], [3, 3], [6, 5]], [[1, 1], [2, 2], [4, 4], [5, 5]], [[1, 1], [2, 2], [4, 4], [6, 5]], [[1, 1], [3, 3], [4, 4], [5, 5]], [[1, 1], [3, 3], [4, 4], [6, 5]], [[2, 2], [3, 3], [4, 4], [5, 5]], [[2, 2], [3, 3], [4, 4], [6, 5]]]
这些是无效组合 [5,5] 和 [6,5] 是不允许的：
[[[1, 1], [2, 2], [5, 5], [6, 5]], [[1, 1], [3, 3], [5, 5], [6, 5]], [[1, 1], [4, 4], [5, 5], [6, 5]], [[2, 2], [3, 3], [5, 5], [6, 5]], [[2, 2], [4, 4], [5, 5], [6, 5]], [[3, 3], [4, 4], [5, 5], [6, 5]]]
如果我理解正确，您需要所有可能的 ID 组合，其中 ID 不共享父 ID。我尝试了一些不同的东西，只是为了好玩，不知道性能是否会提高。
x = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,5]]
首先，让我们翻转缩小它。
hash = x.reduce({}) {|hash, pair| (hash[pair.last] ||= []).push pair.first}
#=> {1=>[1], 2=>[2], 3=>[3], 4=>[4], 5=>[5, 6]}
现在我们得到父 ID 的所有可能组合。
parents = hash.keys.combination(4).to_a
#=> [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5]]
现在我们将每个父 ID 映射到它的子 ID。
children = parents.map do |array|
array.map {|parent| hash[parent]}
end
#=> [[[1], [2], [3], [4]], [[1], [2], [3], [5, 6]], [[1], [2], [4], [5, 6]], [[1], [3], [4], [5, 6]], [[2], [3], [4], [5, 6]]]
此时我们已经深入了解数组了。现在，我们取每个子数组的乘积来得到所有可能的组合，我们甚至不需要对它们进行 uniq。
children.map {|array| array.first.product *array.drop(1)}.flatten(1)
#=> [[1, 2, 3, 4], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 3, 4, 5], [1, 3, 4, 6], [2, 3, 4, 5], [2, 3, 4, 6]]
现在您拥有所有 ID 组合，如果您仍然需要使用 hash table.
性能怎么样？我以 运行 this file.
为基准有 50 个条目，25 个重复，以及 4 个的组合：
3957124
Original: 8.719000 0.110000 8.829000 ( 8.860909)
3957124
Simons: 4.875000 0.094000 4.969000 ( 6.458309)
所以理论上看起来更快。但是，有 125 个条目，25 个重复，以及 4 的组合：
9811174
Original: 22.875000 0.281000 23.156000 ( 23.213483)
9811174
Simons: 20.703000 0.391000 21.094000 ( 21.232167)
这并没有快多少。这是因为对于如此多的组合，Ruby 花费大部分时间进行内存分配（尝试在任务管理器或 top 中查看），在 Ruby 中是 dog-慢。预先分配内存并没有任何有用的方法，所以超过某个点你就处于硬限制。
但这只会发生，因为您强制 Ruby 一次将所有数组项收集在一起。如果您的特定用例允许您单独处理每个组合，则可以避免大部分内存分配。通过对每个子数组 (this file) 调用 yield：
9811174
Simons: 8.485000 0.000000 8.485000 ( 8.476653)
快多了。您还将观察到内存使用量保持不变。 It's still gonna take a while though。然而，如果你有多个核心，你原则上可以并行化，因为一旦你有了哈希，每个组合都可以独立于其他组合进行处理。我会留给你试试:)
您可以按如下方式进行。
代码
def combos(pairs, group_size)
pairs.group_by(&:last).
values.
combination(group_size).
flat_map { |a| a.shift.product(*a) }
end
例子
pairs = [[1, 1], [2, 2], [3, 3], [4, 4], [5, 5], [6,5]]
combos(pairs, 4)
#=> [[[1, 1], [2, 2], [3, 3], [4, 4]],
# [[1, 1], [2, 2], [3, 3], [5, 5]],
# [[1, 1], [2, 2], [3, 3], [6, 5]],
# [[1, 1], [2, 2], [4, 4], [5, 5]],
# [[1, 1], [2, 2], [4, 4], [6, 5]],
# [[1, 1], [3, 3], [4, 4], [5, 5]],
# [[1, 1], [3, 3], [4, 4], [6, 5]],
# [[2, 2], [3, 3], [4, 4], [5, 5]],
# [[2, 2], [3, 3], [4, 4], [6, 5]]]
combos(pairs, 5)
#=> [[[1, 1], [2, 2], [3, 3], [4, 4], [5, 5]],
# [[1, 1], [2, 2], [3, 3], [4, 4], [6, 5]]]
combos(pairs, 1).size #=> 6
combos(pairs, 2).size #=> 14
combos(pairs, 3).size #=> 16
combos(pairs, 4).size #=> 9
combos(pairs, 5).size #=> 2
说明
对于示例中使用的数组pairs，以及
group_size = 4
我们执行以下计算。首先，我们按每对的最后一个元素对对的元素进行分组（即 parent_id）：
h = pairs.group_by(&:last)
#=> {1=>[[1, 1]], 2=>[[2, 2]], 3=>[[3, 3]], 4=>[[4, 4]], 5=>[[5, 5], [6, 5]]}
我们只需要这个散列中的值：
b = h.values
#=> [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]], [[5, 5], [6, 5]]]
我们现在得到 b:
enum = b.combination(group_size)
#=> b.combination(4)
#=> #<Enumerator: [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]],
# [[5, 5], [6, 5]]]:combination(4)>
我们可以通过将其转换为数组来查看此枚举器的 (5) 个元素：
enum.to_a
#=> [[[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]]],
# [[[1, 1]], [[2, 2]], [[3, 3]], [[5, 5], [6, 5]]],
# [[[1, 1]], [[2, 2]], [[4, 4]], [[5, 5], [6, 5]]],
# [[[1, 1]], [[3, 3]], [[4, 4]], [[5, 5], [6, 5]]],
# [[[2, 2]], [[3, 3]], [[4, 4]], [[5, 5], [6, 5]]]]
最后一步是将 enum 的每个元素映射到其元素的乘积（enum 的每个元素都是对数组）。我们使用 Enumerable#flat_map 因此我们不必随后进行任何展平：
enum.flat_map { |a| a.shift.product(*a) }
returns group_size = 4.
让我们更仔细地看看上一条语句中发生了什么：
enum1 = enum.flat_map
#=> #<Enumerator: #<Enumerator: [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]],
# [[5, 5], [6, 5]]]:combination(4)>:flat_map>
您可能想将 enum1 视为 "compound enumerator"。 enum1 的元素通过 Enumerator#each (which will call Array#each) 传递到它的块中，并分配给块变量 a。让我们看一下传递给块的第二个值。
跳过第一个：
a = enum1.next
#=> [[[1, 1]], [[2, 2]], [[3, 3]], [[4, 4]]]
第二个通过：
a = enum1.next
#=> [[[1, 1]], [[2, 2]], [[3, 3]], [[5, 5], [6, 5]]]
我们取这四个数组的乘积如下：
a[0].product(a[1], a[2], a[3])
#=> [[[1, 1], [2, 2], [3, 3], [5, 5]],
# [[1, 1], [2, 2], [3, 3], [6, 5]]]
我们也可以这样写：
a[0].product(*a[1..-1])
或者，就像我所做的那样：
a.shift.product(*a)
请注意，在最后一个表达式中，*a 的 a 是执行 a.shift 后 a 的剩余部分。