Сортировка Ruby-массива элементов массива по длине равномерно

Question

В Ruby, как я могу отсортировать массив так, чтобы его элементы (также массивы) были упорядочены по размеру длины, а не просто отсортированы по возрастанию / убыванию по длине.

Я бы хотел, чтобы элементы массива распределялись равномерно, чтобы некоторые элементы содержали большое количество объектов, смешанных с меньшими массивами.

Например, у меня есть этот массив с элементами массива, которые содержат количество объектов, показанных в comment. Я разбил их на куски для ясности и вычислил их общий размер (см. Мотивацию ниже).

[
  # 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 параллельных процесса, которые могут помочь сообщить, как упорядочить чанки в массиве. Спасибо!

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
]

... Довольно близко.

Answer 2

Вот еще одна эвристика. ¹ Я скоро объясню процедуру.Нам дано:

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 в массив resultсодержащие nbr_groups массивы.Это будет сделано путем "зачистки" элементов 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>

Предлагаемая мной эвристика начинается с назначения первого nbr_groupsэлементы от sorted до result, так что первый элемент sorted назначен первому элементу result, второй элемент sorted назначен второму элементу result и т. д.один.Следующие nbr_group элементы sorted аналогично присваиваются result, но на этот раз в обратном порядке: nbr_groups+1 '-й элемент sorted назначается последнему элементу result, nbr_groups+2 'элемент sorted назначен предпоследнему элементу 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-полной, поэтому следует прибегнуть к использованию эвристики для всех, кроме самых маленьких задач.}

Answer 3

Алгоритм, который я бы использовал, чтобы получить примерно равномерное распределение размера, согласно моему комментарию к OP:

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

Если данные такие, как в примере OP, это приводит к идеальному распределению.

---

За обсуждение в комментариях вы можете получить обратно все данные в одном массиве, отформатированные в оригинале, но сгруппированные с помощью этого метода, выполнив:

grouped_data.values.flatten(1)