按长度均匀排序Ruby数组中的数组项

Question

在Ruby语言中，如何对数组进行排序以便使其内部元素（也是数组）按照长度大小排列，但不仅仅是按照长度升序或降序排序。

我想要将数组元素分布均匀，使得包含大量对象的项目与较小的数组相互交织。

例如，我有一个数组，其中每个元素都是一个包含注释中显示的对象数量的数组。为了清晰起见，我将它们分成了几个块，并计算出它们的总大小（见下面的动机说明）。

[
  # chunk 1, inner total length 5
  [{...}], # 2
  [{...}], # 1
  [{...}], # 1
  [{...}], # 1
  # chunk 2, inner total length 11
  [{...}], # 2
  [{...}], # 2
  [{...}], # 3
  [{...}], # 4
  # chunk 3, inner total length 9
  [{...}], # 3
  [{...}], # 3
  [{...}], # 1
  [{...}], # 2
  # chunk 4, inner total length 15
  [{...}], # 4
  [{...}], # 3
  [{...}], # 4
  [{...}], # 4
]

我希望能够调整数组的排列方式，使其看起来更像下面这样。注意：此示例按大小顺序排列（1..4），但这并非必要。我只想将它们分成块，以便内部数组的累积长度是可比较的。

[
  # chunk 1, inner total length 10
  [{...}], # 1
  [{...}], # 2
  [{...}], # 3
  [{...}], # 4
  # chunk 2, inner total length 10
  [{...}], # 1
  [{...}], # 2
  [{...}], # 3
  [{...}], # 4
  # chunk 3, inner total length 10
  [{...}], # 1
  [{...}], # 2
  [{...}], # 3
  [{...}], # 4
  # chunk 4, inner total length 10
  [{...}], # 1
  [{...}], # 2
  [{...}], # 3
  [{...}], # 4
]

我的动机是为了将外部数组切片，以便我可以并行处理内部数组。我不希望其中一个并行进程获取一些小块的切片，而另一个进程获取一些非常大的块的切片。

注意：我知道我有4个并行进程，这可能有助于如何安排数组中的块。谢谢！

- mfink

---

非常有趣的问题，尽管我担心并行处理每个分布式块所获得的任何收益都会被分发所需的初始排序算法所抵消。 - engineersmnky

那么对于无法均匀排序的数据怎么办？比如说我有四个长度分别为1、2、4和4的数组，它们无法被均匀地分组。 - Glyoko

此外，根据您的参数（并且根据我上面的评论，假设解决方案存在），这个问题是NP完全问题。考虑一下您想将一个大数据集组织成仅两个块的情况。砰，你就遇到了分区问题。也就是说，对于某些输入，计算可能需要很长时间。 - Glyoko

@engineersmnky，这是一个很好的观点。这些项目的处理已经非常昂贵，这让我考虑前期排序的成本。 - mfink

作为建议，启发式方法可能更好。您可以将所有数组解块并按数组长度排序。然后迭代块，将具有 index % 4 == 0 的项分配给第一个进程，将 index % 4 == 1 的项分配给第二个进程，将 index % 4 == 2 的项分配给第三个进程，将 index % 4 == 3 的项分配给第四个进程。这不会提供完美的解决方案，但大致上是正确的。它的好处是更简单，初始排序速度更快。 - Glyoko

你也可以通过设置四个工作进程来避免预先分块，然后由主进程发出每个工作进程的任务；当一个工作进程完成任务时，它会得到下一个可用的任务。这意味着一些工作进程可能会执行几个大型任务，而其他一些工作进程则会执行更多的小型任务，并且最终它们是相当平均的（差异在一个任务长度内）。当输入的作业长度不可预测时，这也适用。例如，parallel gem 可以自动为您完成此操作。 - Amadan

Answer 1

这不是一个 "完美" 的解决方案，但这里有一个不太耗费计算资源/复杂的方法：

1. 求出所有内部数组的长度之和：

total_count = original_list.map(&:count).inject(:+)

确定每个并行进程要放置多少项（在您的情况下，4个进程）：

chunk_size = total_count / 4

现在，这是更难的部分：算法。我将保持简单，并逐个遍历数组中的每个项，并进行"分块", 直到达到chunk_size。

current_chunk_size = 0

original_list.chunk_while do |inner_array|
  current_chunk_size += inner_array.count
  current_chunk_size = 0 if current_chunk_size >= chunk_size
  current_chunk_size > 0
end

如果您喜欢，可以使用像 slice_after 这样的方法来实现类似的逻辑。

对于您的原始示例，使用此算法：

[
  # chunk 1, inner total length 5
  [{...}], # 2
  [{...}], # 1
  [{...}], # 1
  [{...}], # 1
  # chunk 2, inner total length 11
  [{...}], # 2
  [{...}], # 2
  [{...}], # 3
  [{...}], # 4
  # chunk 3, inner total length 9
  [{...}], # 3
  [{...}], # 3
  [{...}], # 1
  [{...}], # 2
  # chunk 4, inner total length 15
  [{...}], # 4
  [{...}], # 3
  [{...}], # 4
  [{...}], # 4
]

返回结果为：

[
  # chunk 1, inner total length 12
  [{...}], # 2
  [{...}], # 1
  [{...}], # 1
  [{...}], # 1
  [{...}], # 2
  [{...}], # 2
  [{...}], # 3

  # chunk 2, inner total length 10
  [{...}], # 4
  [{...}], # 3
  [{...}], # 3

  # chunk 3, inner total length 10
  [{...}], # 1
  [{...}], # 2
  [{...}], # 4
  [{...}], # 3

  # chunk 4, inner total length 8
  [{...}], # 4
  [{...}], # 4
]

...非常接近。

- Tom Lord

---

谢谢，我喜欢这种方法，会试一下。差不多就可以了 :) - mfink

汤姆，我在跟随你的计算时遇到了麻烦。首先，original_list.chunk_while 不应该是 original_list.flatten(1).chunk_while 吗？你可能想要对我的答案中的示例运行你的代码。 - Cary Swoveland

@CarySwoveland 您的数据假定输入可能被深度嵌套，但原始问题（诚然是无效语法，因此有些模糊！）没有说明这一点。您使用了：[[[0,1], [2], [3], [4]], ...]，但我假设它应该是：[[1, 2, 3, 4], ...]。 - Tom Lord

我明白了。恐怕我还是不太明白。如果您能提供一个简单的例子就更好了。请注意，chunk_while返回一个枚举器，所以我认为您需要使用end.to_a。 - Cary Swoveland

Answer 2

我会使用以下算法来实现根据我在评论中提到的目标，获得大致均匀的大小分布：

最初的回答：

unchunked_data = [
  [{...}],
  [{...}],
  [{...}],
  [{...}],
  [{...}],
  [{...}],
  [{...}],
  [{...}]
]

sorted_data = unchunked_data.sort_by(&:size)
grouped_data = sorted_data.each_with_index.group_by { |_, index| index % 4 }

grouped_data.each do |process_index, data|
  # each_with_index would put data in an array with its index in sorted_data. Calling map(&:first) removes that index.
  data_without_index = data.map(&:first)
  send_data_to_process(process_index, data_without_index)
end

如果数据与原作者的示例相同，那么这将导致完美的分布。

---

根据评论中的讨论，您可以通过以下方式将所有数据以原始格式但使用此方法分组，存储在单个数组中：

grouped_data.values.flatten(1)

- Glyoko

---

谢谢@Glyoko，我倾向于使用这个解决方案。有一件事是我不想让我的数组必须分组（或嵌套在第三个数组中），你能把它返回到你的unchunked_data的形式吗（一个数组的数组）？此外，我倾向于使用grouped_data.map而不是grouped_data.each，因为我将在该块之外处理它，该块会剥离那些讨厌的索引数字（根据您的each_with_index注释）。 - mfink

根据您的第一条评论，我只是希望最终得到一个按分布顺序排列的数组数组结果（与原始的“unchunked_data”结构相匹配）。对于您的第二条评论和相关内容...我不想要哈希，所以我将使用.map，它将返回[[[]，...]]，但如果有意义的话，我宁愿得到[[],...]。我将使用结果进行类似于each_slice(grouped_data.size / 4)的操作。 - mfink

请注意，这种方法不一定比我的答案给出更均匀的分布；它完全取决于输入...例如，假设原始数组大小为：[1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4]。我的答案将把它们分成：[[1, 1, 1, 2, 2], [2, 2, 3], [3, 3], [3, 4]] - 即总大小为[7, 7, 6, 7]；而这个答案将把它们分成：[[1, 2, 3], [1, 2, 3], [1, 2, 3], [2, 3, 4]] - 即总大小为[6, 6, 6, 9]。我不确定哪种算法最有可能给出最佳分布。 - Tom Lord

@mfink 在这种情况下，您可以执行类似于grouped_data.values.flatten(1)的操作。@TomLord 这是正确的。问题实际上是NP完全问题，因此我们两个答案都只是“最佳猜测”。根据数据，其中一个可能比另一个更好。 - Glyoko

我最终选择了这个解决方案，因为它倾向于使我正在处理的数据集更加均匀分布。而且总体上可读性更好。我想删除“&：first”清理步骤，但我会把它留到另一天。谢谢！ - mfink

Answer 3

这里是另一个启发式算法。¹我将简要解释一下过程。我们已知：

arr = [[[0,1],         [2],        [3],           [4]],
       [[5,6],         [7,8],      [9,10,11],     [12,13,14,15]],
       [[16,17,18],    [19,20,21], [22],          [23,24]],
       [[25,26,27,28], [29,30,31], [32,33,34,35], [36,37,38,39]]
      ]

nbr_groups = 4

首先将一级数组展开并按大小排序。

sorted = arr.flatten(1).sort_by(&:size)
  #=> [[2], [3], [4], [22], [0, 1], [5, 6], [7, 8], [23, 24], [9, 10, 11],
  #    [16, 17, 18], [19, 20, 21], [29, 30, 31], [12, 13, 14, 15],
  #    [25, 26, 27, 28], [32, 33, 34, 35], [36, 37, 38, 39]] 

我们需要将sorted的元素分组到一个包含nbr_groups个数组的result数组中。这将通过将sorted的元素“扫描”到result中来完成。扫描由nbr_groups个正向赋值和相同数量的反向赋值交替进行。

现在创建一个枚举器。

a = nbr_groups.times.to_a
  #=> [0, 1, 2, 3] 
idx = [*a, *a.reverse].cycle
  #=> #<Enumerator: [0, 1, 2, 3, 3, 2, 1, 0]:cycle>

我建议的启发式方法是，首先将sorted的前nbr_groups个元素分配给result，使得sorted的第一个元素分配给result的第一个元素，sorted的第二个元素分配给result的第二个元素，以此类推。接下来，sorted的下一个nbr_group个元素也按照相同的方式分配给result，但这次是反向分配：即sorted的第nbr_groups+1个元素分配给result的最后一个元素，sorted的第nbr_groups+2个元素分配给result的倒数第二个元素，以此类推。这些交替的分配一直持续到所有sorted的元素都被分配完毕。

result = sorted.each_with_object(Array.new(nbr_groups) { [] }) do |a,arr| 
  arr[idx.next] << a
end
  #=> [[[2], [23, 24], [9, 10, 11], [36, 37, 38, 39]],
  #    [[3], [7, 8], [16, 17, 18], [32, 33, 34, 35]],
  #    [[4], [5, 6], [19, 20, 21], [25, 26, 27, 28]],
  #    [[22], [0, 1], [29, 30, 31], [12, 13, 14, 15]]]

现在让我们来看看这些任务是如何平均分配的：

result.map { |a| a.sum(&:size) }
  #=> [10, 10, 10, 10] 

这个结果让我感到很开心。当然，result 的所有元素大小相同纯属巧合。^{1.正如@glyoko在评论中指出的那样，该问题是NP完全问题，因此除了最小的问题外，必须使用启发式方法。}

- Cary Swoveland

---

非常整洁，但我不确定我理解“扫描”如何帮助。只使用idx = a.cycle似乎同样有效。 - Glyoko

@Glyko，假设 sorted = [[0], [1,2], [3,4,5], [6,7,8,9]] 和 nbr_groups = 2。通过扫描，result #=> [[[0], [6,7,8,9]], [[1,2], [3,4,5]]，result.map { |a| a.sum(&:size) } #=> [5,5]。使用 idx.cycle，result #=> [[[0], [3,4,5]], [[1,2], [6,7,8,9]]，result.map { |a| a.sum(&:size) } #=> [4,6]。使用 idx.cycle，result.map { |a| a.sum(&:size) } 倾向于非递增，并且如果 sorted % nbr_groups #=> 0，则会是非递增的。 - Cary Swoveland

好的，这很有道理。每隔一次反向进行可以使分布均匀化。 - Glyoko