Можно ли написать это без аккумулятора? - PullRequest
Новая
       21

Можно ли написать это без аккумулятора?

4 голосов
/ 16 сентября 2011

Первоначально я пытался написать это без хвостовой рекурсии, поскольку согласно http://www.erlang.org/doc/efficiency_guide/myths.html ЛУЧ делает это сам.Это работает, мне просто интересно, если мой код слишком уродлив / неэффективен.Тот, что в грамотных программах http://en.literateprograms.org/Selection_sort_%28Erlang%29, кажется немного менее лаконичным, чем моя версия, но я чувствую, что у меня слишком много параметров, чтобы их было легко понять.Я не уверен, чувствую ли я это так, если бы я был более опытным с рекурсией. 

-module(selection).
-export([selection/1]).

selection([H|T]) -> lists:reverse(selection(T,H,[],[])).

selection([],Min,[H|T],Acc) -> selection(T,H,[],[Min|Acc]);
selection([],Min,[],Acc) -> [Min|Acc];
selection([H|T],Min,Rest,Acc) when H < Min -> selection(T,H,[Min|Rest],Acc);
selection([H|T],Min,Rest,Acc) -> selection(T,Min,[H|Rest],Acc).

1 Ответ

1 голос
/ 16 сентября 2011

Вот одна версия: 

-module(selection).

-export([selection/1]).

selection([]) -> [];
selection([H|T]) -> 
  {Min, Rest} = remove_min(H, T, []),
  [Min | selection(Rest)].

remove_min(Min, [], Rest) -> {Min, Rest};
remove_min(SoFar, [H|T], Acc) when H < SoFar ->
  remove_min(H, T, [SoFar|Acc]);
remove_min(Min, [H|T], Acc) -> remove_min(Min, T, [H|Acc]).

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

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

selection([],Max,[H|T],Acc) -> selection(T,H,[],[Max|Acc]);
selection([],Max,[],Acc) -> [Max|Acc];
selection([H|T],Max,Rest,Acc) when H > Max -> selection(T,H,[Max|Rest],Acc);
selection([H|T],Max,Rest,Acc) -> selection(T,Max,[H|Rest],Acc).

Кажется, у обоих почти одинаковая производительность.

...