Генерация powerset без стека в Erlang - PullRequest
Новая
       47

Генерация powerset без стека в Erlang

3 голосов
/ 25 декабря 2011

Примечание. Это продолжение моего предыдущего вопроса о блоках питания.

У меня есть хорошее решение Ruby для моего предыдущего вопроса о создании блока питаниянабор без необходимости хранить стек: 

class Array
  def powerset
    return to_enum(:powerset) unless block_given?
    1.upto(self.size) do |n|
      self.combination(n).each{|i| yield i}
    end
  end
end
# demo
['a', 'b', 'c'].powerset{|item| p item} # items are generated one at a time
ps = [1, 2, 3, 4].powerset # no block, so you'll get an enumerator 
10.times.map{ ps.next } # 10.times without a block is also an enumerator

Он делает свою работу и работает хорошо.

Однако я хотел бы попытаться переписать то же решение в Erlang, потому что дляблок {|item| p item} У меня большая часть рабочего кода, уже написанного на Erlang (он делает некоторые вещи с каждым сгенерированным подмножеством).

Хотя у меня есть некоторый опыт работы с Erlang (я прочитал все 2 книги :)), Я довольно смущен примером и комментариями, которые sepp2k любезно дал мне мой предыдущий вопрос о блоках питания.Я не понимаю последнюю строку примера - единственное, что я знаю, - это понимание списка.Я не понимаю, как я могу изменить его, чтобы иметь возможность что-то делать с каждым сгенерированным подмножеством (затем выбросить его и продолжить со следующим подмножеством).

Как я могу переписать это итеративное генерирование мощности Rubyв Эрланге?Или, может быть, приведенный пример Erlang уже почти соответствует потребностям?

1 Ответ

1 голос
/ 29 декабря 2011

Все приведенные примеры имеют O (2 ^ N) сложность памяти, потому что они возвращают весь результат (первый пример).Два последних примера используют регулярную рекурсию, чтобы стек повышался.Ниже код, который является модификацией и компиляцией примеров, будет делать то, что вы хотите: 

subsets(Lst) ->
    N = length(Lst),
    Max = trunc(math:pow(2, N)),
    subsets(Lst, 0, N, Max).

subsets(Lst, I, N, Max) when I < Max ->
    _Subset = [lists:nth(Pos+1, Lst) || Pos <- lists:seq(0, N-1), I band (1 bsl Pos) =/= 0],
    % perform some actions on particular subset
    subsets(Lst, I+1, N, Max);
subsets(_, _, _, _) ->
    done.

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

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

...