Как разбить массив на четные куски для параллельной обработки

Question

У меня есть большой массив данных счета, который сортируется по дате счета. Я хотел бы обобщить данные по некоторой функции даты, например: по месяцам, кварталам и т. Д. Поскольку массив очень велик, я хотел бы использовать многопоточность и обрабатывать несколько частей массива параллельно , в разных потоках.

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

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

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

Answer 1

Для вашего случая (и ЛЮБОГО) несколько потоков могут ускорить ваше приложение или не ускорить его. Это зависит от количества факторов.

Это, как говорится, общий шаблон для этого состоит в том, чтобы иметь связку worker threads in a pool.

Псевдо-код должен идти, как это:

while your array is not empty 
    if there is at least one idle worker 
    pick one idle thread and process element 0 from the array 
    Remove element 0 from the array 
    Process the element 
    else wait for a worker thread to be idle 

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

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

Редактировать на основе ваших комментариев:

Если вы действительно хотите избежать синхронизации и считаете, что все потоки, написанные в один и тот же массив, будут работать (некоторые языки могут не позволить это, действительно не уверены), а затем все ваши данные в одном массиве, разбивают массив на N равные куски длины М. Создайте массив результатов с кодами NxM, а затем, когда у вас запущен незанятый рабочий стол, назначьте ему N-й кусок и N-е ведро.

В конце выполнения ваши данные будут рассортированы и смежных