Параллельная генерация мощности в Эрланге? - PullRequest
Новая
       63

Параллельная генерация мощности в Эрланге?

2 голосов
/ 01 ноября 2011

Существует множество примеров реализаций генерации набора мощности набора в Java, Python и других, но я до сих пор не могу понять, как работает настоящий алгоритм.

Какие шаги предпринимаются алгоритмом для генерации набора мощности P (S) из набора S?

(Например, набор мощности {1,2,3,4}: {{}, {1}, {2}, {1,2}, {3}, {1,3}, { 2,3}, {1,2,3}, {4}, {1,4}, {2,4}, {1,2,4}, {3,4}, {1,3,4} , {2,3,4}, {1,2,3,4}}.)

UPD: я нашел это объяснение, но все же я не понимаю его. Я пытаюсь понять алгоритм генерации набора мощности, потому что я хотел бы написать его параллельную реализацию - следующая последовательная реализация Erlang имеет огромный стек и не может сосчитать более 30-ти элементов на машине с 8 ГБ Оперативная память: 

powerset(Lst) ->
    N = length(Lst),
    Max = trunc(math:pow(2,N)),
    [[lists:nth(Pos+1,Lst) || Pos <- lists:seq(0,N-1), I band (1 bsl Pos) =/= 0] || I <- lists:seq(0,Max-1)].

UPD2:

Этот фрагмент возвращает все подмножества набора [a, b, c], кроме [a, b, c]: 

generate_all_subsets([],Full_list,Result) ->
    Result;
generate_all_subsets([Element|Rest_of_list],Full_list,Result) ->
    Filtered_list = [X || X <- Full_list, X =/= Element],
    ?DBG("*Current accumulated result: ~w ~n", [Result]),
    Result2 = generate_subsets(Element,Filtered_list,[],[]),
    ?DBG("Generated new result: ~w ~n", [Result2]),
    New_result = lists:append(Result,Result2),
    ?DBG("Got new accumulated result: ~w ~n", [New_result]),
    generate_all_subsets(Rest_of_list,Full_list,New_result).



generate_subsets(Main_element,[],Accumulated_list,Result) ->
    Result;
generate_subsets(Main_element,[Element|Rest_of_set],Accumulated_list,Result) ->
    ?DBG("*Generating a subset for ~w ~n", [Main_element]),
    New_accumulated_list = lists:flatten([Element|Accumulated_list]),
    New_result = [New_accumulated_list|Result],
    ?DBG("Added ~w to the result: ~w ~n", [New_accumulated_list,New_result]),
    generate_subsets(Main_element,Rest_of_set,New_accumulated_list,New_result).

Я не уверен, что этот фрагмент верен.

1 Ответ

1 голос
/ 02 ноября 2011

Вот довольно простая версия, которая работает намного лучше, чем версия из rosettacode: 

generate([]) -> [[]];
generate([H|T]) -> PT = generate(T),
  [ [H|X] || X <- PT ] ++ PT.

если вы хотите еще большей производительности, вы можете попробовать это: 

generate([]) -> [[]];
generate([H|T]) -> PT = generate(T),
  generate(H, PT, PT).

generate(_, [], Acc) -> Acc;
generate(X, [H|T], Acc) -> generate(X, T, [[X|H]|Acc]).

Но, в любом случае, я сомневаюсь, что вы сможете построить набор из 30 элементов. По моим подсчетам он может потреблять более 16 ГБ. В моей второй версии может быть некоторое повторное использование хвостов списков, но это не поможет. Я думаю, что вы даже можете потерпеть неудачу в более крупной проблеме, если будете реализовывать ее как параллельный алгоритм, потому что будет копирование сообщений.

...