Наиболее эффективный способ присвоения списков неправильной длины подпроцессам для обработки

Question

У меня есть несколько объектов (примерно 530,000). Эти объекты случайным образом назначаются набору списков (не на самом деле случайных, но давайте предположим, что это так). Эти списки индексируются последовательно и присваиваются словарю, называемому groups, в соответствии с их индексом. Я знаю общее количество объектов, но я не знаю длины каждого списка раньше времени (который в данном конкретном случае может варьироваться от 1 до 36000).

Далее я должен обработать каждый объект, содержащийся в списках. Чтобы ускорить эту операцию, я использую MPI для отправки их различным процессам. Наивный способ сделать это - просто назначить каждому процессу len(groups)/size (где size содержит количество используемых процессов) списки, назначить любой возможный остаток, заставить его обрабатывать содержащиеся в нем объекты, возвращать результаты и ждать. Это, очевидно, означает, однако, что если один процесс получает, скажем, много очень коротких списков, а другой - все очень длинные списки, то первый процесс большую часть времени будет простаивать, а прирост производительности будет не очень большим.

Какой способ назначения списков был бы наиболее эффективным? Один из подходов, который я мог бы придумать, состоит в том, чтобы попытаться назначить списки таким образом, чтобы сумма длин списков, назначенных каждому процессу, была максимально похожей. Но я не уверен, как лучше всего это реализовать. У кого-нибудь есть предложения?

Answer 1

Один из подходов, который я мог бы придумать, состоит в том, чтобы попытаться назначить списки таким образом, чтобы сумма длин списков, назначенных каждому процессу, была как можно более сходной.

Если предположить, что время обработки точно соответствует сумме длин списков, а производительность вашего процессора однородна, то это именно то, что вам нужно. Это называется проблема планирования мультипроцессора , которая очень близка к проблеме упаковки бункеров , но с постоянным числом бинов, минимизирующим максимальную емкость.

Как правило, это трудная задача для NP, поэтому вы не получите идеального решения. Самый простой разумный подход состоит в том, чтобы жадно выбрать самый большой кусок работы для процессора, которому назначена наименьшая работа.

Это просто реализовать в python (в примерах используется список списков):

greedy = [[] for _ in range(nprocs)]
for group in sorted(groups, key=len, reverse=True):
    smallest_index = np.argmin([sum(map(len, assignment)) for assignment in greedy])
    greedy[smallest_index].append(group)

Если у вас большое количество процессоров, вы можете оптимизировать вычисления smallest_index, используя очередь с приоритетами. Это даст значительно лучшие результаты, чем простое сортированное разбиение, как рекомендует Аттерссон:

(https://gist.github.com/Zulan/cef67fa436acd8edc5e5636482a239f8)

Answer 2

При условии, что более длинный список имеет больший объем памяти, your_list имеет объем памяти, который можно получить с помощью следующего кода:

import sys
sys.getsizeof(your_list)

(Примечание: это зависит от реализации Python. Пожалуйста, прочитайте Сколько байтов на элемент содержится в списке Python (кортеж)? )

Есть несколько способов продолжить. Если ваш исходный «конвейер» списков может быть отсортирован по key=sys.getSizeof, то вы можете нарезать и назначить для обработки N каждый N-й элемент ( Pythonic способ возврата списка каждого n-го элемента в большем списке ).

Пример:

sorted_pipeline = [list1,list2,list3,.......]
sorted_pipeline[0::10] # every 10th item, assign to the first sub-process of 10

Это сбалансирует нагрузки справедливым образом, сохраняя сложность O (NlogN) из-за исходной сортировки и затем постоянную (или линейную, если списки копируются) для назначения списков.

Иллюстрация (по запросу) разделения 10 элементов на 3 группы:

>>> my_list = [0,1,2,3,4,5,6,7,8,9]
>>> my_list[0::3]
[0, 3, 6, 9]
>>> my_list[1::3]
[1, 4, 7]
>>> my_list[2::3]
[2, 5, 8]

И окончательное решение:

assigned_groups = {}
for i in xrange(size):
    assigned_groups[i] = sorted_pipeline[i::size]

Если это невозможно, вы всегда можете сохранить счетчик общего размера очереди, для каждого конвейера подпроцесса, а также вероятность изменения или логику выбора, чтобы учесть это.