Найти самый большой элемент в списке с K процессами, используя Erlang?

Question

Алгоритм легко реализовать с использованием одного процесса, однако как я могу использовать несколько процессов для выполнения работы?

Вот что я сделал до сих пор.

 find_largest([H], _) -> H;
 find_largest([H, Q | T], R) ->
     if H > Q -> find_largest([H | T], [Q | R]);
       true -> find_largest([Q | T], [H | R])
 end.

Спасибо

Answer 1

Учитывая то, как Эрланг представляет списки, вероятно, не стоит пытаться делать параллельно.Разделение списка подразумевает большое копирование (так как они являются связанными списками), как и отправка этих разделов другим процессам.Я ожидаю, что сравнение будет гораздо дешевле, чем копировать все дважды, а затем объединить результаты.

Реализация также не верна, вы можете найти хороший в lists.erl как max / 1

%% max(L) -> returns the maximum element of the list L

-spec max([T,...]) -> T.

max([H|T]) -> max(T, H).

max([H|T], Max) when H > Max -> max(T, H);
max([_|T], Max)              -> max(T, Max);
max([],    Max)              -> Max.

Если по какой-то причине ваши данные уже находятся в отдельных процессах, просто получите списки: max / 1 или каждый из списков и отправьте их в одно место, а затем получите списки: max / 1 из списка результатов,Вы также можете выполнить сравнение по мере получения результатов, чтобы избежать создания этого промежуточного списка.

Answer 2

Однопроцессную версию вашего кода следует заменить на lists:max/1. Полезная функция для распараллеливания кода выглядит следующим образом:

pmap(Fun, List) ->
    Parent = self(),
    P = fun(Elem) ->
            Ref = make_ref(),
            spawn_link(fun() -> Parent ! {Ref, Fun(Elem)} end),
            Ref
        end,
    Refs = [P(Elem) || Elem <- List],
    lists:map(fun(Ref) -> receive {Ref, Elem} -> Elem end end, Refs).

pmap/2 применяется Fun к каждому элементу List параллельно и собирает результаты в порядке ввода. Чтобы использовать pmap с этой проблемой, вам нужно будет сегментировать исходный список в список списков и передать его в pmap. например lists:max(pmap(fun lists:max/1, ListOfLists)). Конечно, процесс сегментирования списков был бы более дорогостоящим, чем простой вызов lists:max/1, поэтому это решение потребовало бы предварительной сегментации списка. Даже тогда, вероятно, что издержки копирования списков перевешивают любые преимущества распараллеливания - особенно на одном узле.

Внутренняя проблема вашей ситуации заключается в том, что вычисление каждой подзадачи является крошечным по сравнению с накладными расходами на управление данными. Задачи, требующие больших вычислительных ресурсов (например, составление списка больших чисел), легче распараллелить.

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