10

私がErlangについて読んでいる本の後ろには演習があり、1つはlists：append関数を再作成することです。

++演算子を使用するだけでこれを行うことができますが、これは本当に遅いのではないでしょうか。そして、演習のポイントは、私が書いたリスト操作を使用してそれを行うことだと思います。

これまでのところ、私が考えることができる唯一のアプローチは、次のようなことを行うことです。

concat([], _, Results)->
  Results;
concat(_, [], Results)->
  Results;
concat([Ah|At],B,Results) ->
  concat(At,B,[Ah|Results]).

しかし、私はこれが間違っていることを知っています...

これを行う方法について何か提案はありますか？

編集：質問を明確にするために、ここに入力と出力の例があります：

入力：[[1,2,3]、[]、[4,5]、[6]]出力：[1,2,3,4,5,6]

しばらく働いた後、私もこのコードを思いついた：

append([A|[B|[T|[]]]]) ->
  append([A++B|T]);
append([H|T]) ->
  H++T.

ただし、これはリストのサイズが3の場合にのみ機能します。ランダムなサイズのリストの任意の数で機能するようにこれを変更するにはどうすればよいですか。

4

4 に答える 4

14

++は、間違って使用した場合にのみ遅くなります。注意深く使用すると、手作業で作成できるものと同じくらい高速になります。リストを正しい方向に処理する必要があります。そうしないと、結果の追加はO（N ^ 2）になります。X ++ Yを実行するときは、Xのコピーを作成してから、コピーされていないYの前に追加する必要があります。

この関数では、アキュムレータが++の左側に表示されるため、追加は効率的ではありません。

concatl(Lst) ->
    concatl(Lst, []).
concatl([], Acc) ->
    Acc;
concatl([H|T], Acc) ->
    concatl(T, Acc ++ H).

この関数は、末尾再帰ではありませんが、はるかに優れたパフォーマンスを発揮します。

concat([]) -> [];
concat([H|T]) ->
    H ++ concat(T).

この場合、末尾再帰に書き換えることは、わずかな改善にすぎません。

concat2(Lst) ->
    concat2(lists:reverse(Lst), []).
concat2([], Acc) -> Acc;
concat2([H|T], Acc) ->
    concat2(T, H ++ Acc).

大きな入力リストのタイミングは、改善がどれほど大きいかを示しています。（時間はマイクロ秒単位です。）

41> Time(fun() -> test:concatl([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
14539061
40> Time(fun() -> test:concat([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
245356
42> Time(fun() -> test:concat2([lists:seq(1,1000) || X <- lists:seq(1,1000)]) end).
211571
于 2009-07-15T14:59:20.837 に答える
4

concat関数に必要なパラメーターは2つだけです。これは、パラメーターの1つに追加するため、最終的にはそれが返されるためです。（未テスト）のようなもの：

concat(L,[]) ->
   L;
concat(L,[H|T]) ->
   concat(L ++ [H],T).

++は追加演算子です。効率的にするには、これを行う必要があります。

（上記の考え方は、左がなくなった場合は左のパラメーターを返すか、要素の1つを右から左に移動した後に再度呼び出すことです）。逆に追加を実行し、最後に答えを逆にすることの方がおそらくより効率的ですが、ちょっと...）

（あなたの編集を見たばかりで、もちろん私のものは追加する2つのものに対してのみ機能しますが、リストのリスト内の各要素に対して上記の関数を繰り返すことができます...）

于 2009-07-15T13:20:28.167 に答える
4

きちんとしたアプローチの1つは、を使用することlists:foldrです。

concat(A,B) ->
    lists:foldr(fun(X,XS) -> [X|XS] end, B, A).

concat(XS) ->
    lists:foldr(fun concat/2, [], XS).

独自のフォルダ関数を作成するのも良い練習です...

于 2009-07-15T16:29:17.667 に答える
0 
    -module(functional).
    -export([my_append/2,helper/2]).

    my_append(L1,L2) ->
      % concatenates lists L1 and L2
        functional:helper(lists:reverse(L1),L2).
    helper(L1,L2) ->
        if
            L1 == [] -> L2;
            L2 == [] -> L1;
            true     -> [H1|T1] = L1,
                        functional:helper(T1,[H1|L2])
        end.
于 2016-01-17T16:45:53.220 に答える