2

ソートされたリストを1つのリストにマージする必要がありました（リストの数は異なる場合があります）。私はErlangを初めて使用するので、かなりの機能について知りませんでしたlists:merge/1。そこで、独自のmerge/1関数を実装しました。複雑さはO（m * n）（m-リストの数、n-リスト内の要素の平均数）であり、末尾再帰を使用します。これが私の関数です：

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

merge( ListOfLists ) ->
        merge( ListOfLists, [] ).

merge( [], Merged ) ->
        lists:reverse( Merged );
merge( ListOfLists, Merged ) ->
        [ [ Hfirst | Tfirst ] | ListOfLists_Tail ] = ListOfLists,
        % let's find list, which has minimal value of head
        % result would be a tuple { ListWithMinimalHead, Remainder_ListOfLists }
        { [ Hmin | Tmin ], ListOfLists_WithoutMinimalHead } =
        lists:foldl(
                fun( [ Hi | Ti ] = IncomingList, { [ Hmin | Tmin ], Acc } ) ->
                         case Hi < Hmin of
                                true ->
                                        % if incoming list has less value of head then swap it
                                        { [ Hi | Ti ], [ [ Hmin | Tmin ] | Acc ] };
                                false ->
                                        { [ Hmin | Tmin ], [ IncomingList | Acc ] }
                        end
                end,
                { [ Hfirst | Tfirst ], [] },
                ListOfLists_Tail ),
        % add minimal-valued head to accumulator, and go to next iteration
        case Tmin == [] of
                true ->
                        merge( ListOfLists_WithoutMinimalHead, [ Hmin | Merged ] );
                false ->
                        merge( [ Tmin | ListOfLists_WithoutMinimalHead ], [ Hmin | Merged ] )
        end.

しかし、私が知った後、私lists:merge/1は自分のソリューションのパフォーマンスをテストすることにしました。

結果は次のとおりです。

1> c(merge).
{ok,merge}
2>
2> 
3> timer:tc( lists, merge, [ [ lists:seq(1,N) || N <- lists:seq(1,5) ]  ] ).   
{5,[1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]}
3> 
3> timer:tc( merge, merge, [ [ lists:seq(1,N) || N <- lists:seq(1,5) ]  ] ). 
{564,[1,1,1,1,1,2,2,2,2,3,3,3,4,4,5]}
4> 
4> 
4> timer:tc( lists, merge, [ [ lists:seq(1,N) || N <- lists:seq(1,100) ]  ] ). 
{2559,
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]}
5>  
5> timer:tc( merge, merge, [ [ lists:seq(1,N) || N <- lists:seq(1,100) ]  ] ). 
{25186,
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]}
6> 
6> 
6> timer:tc( lists, merge, [ [ lists:seq(1,N) || N <- lists:seq(1,1000) ]  ] ). 
{153283,
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]}
7>  
7> timer:tc( merge, merge, [ [ lists:seq(1,N) || N <- lists:seq(1,1000) ]  ] ). 
{21676268,
 [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1|...]}
8>

0.153秒で感動しました。vs21.676秒 私の関数は非常に遅く動作します。

匿名関数を使用するとパフォーマンスが低下すると思いましたが、削除しても効果はありfunません。

私が主な間違いをした場所を教えていただけますか？または、なぜモジュールリストからの関数が非常に高速なのですか？

ありがとう

4

1 に答える 1

1

違いは、アルゴリズムの複雑さにあります。私が間違っていない限り、あなたのアルゴリズムはO（m ^ 2 * n）です。ここで、nは内部リストの長さ、mは入力リストの内部リストの数です。これは、関数が内部リストのリスト全体を効果的にトラバースして、結果のリストの1つの要素を生成するためです。したがって、テスト例では、実行時間はC1 * N ^ 3に比例します（この場合、C1は定数<1です）。

ただし、通常、事前にソートされたリストのマージ操作は、O（n）の複雑さを持ちます。ここで、nはすべてのリストの全長です。したがって、テストケースの場合、複雑さはO（n * m）である必要があります。つまり、 C2 * N^2に比例する必要があります。

実際、テストのNが10倍になるとわかるように、実装が結果を生成するのに860倍の時間がかかりますが、「lists：merge/1」は入力をマージするのに53倍の時間が必要です。比率は実際の入力サイズと「形状」によって異なりますが、一般的な傾向は依然としてN^3対N^2です。

標準の「lists：merge / 1」はそれほど単純ではありません：https ：//github.com/erlang/otp/blob/maint/lib/stdlib/src/lists.erl#L1441 （「merge/1」は単に「 mergel / 1'）ですが、実際には、単純で、最適化されておらず、末尾再帰ではない「ヘッドリストをマージされたテールとマージするだけ」でも、実装よりもはるかに優れたパフォーマンスを発揮します。

merge2([]) ->
    [];
merge2([Ls|Lss]) ->
    merge2(Ls,merge2(Lss), []).

merge2([], Ls, Acc) ->
    lists:reverse(Acc) ++ Ls;
merge2(Ls, [], Acc) ->
    lists:reverse(Acc) ++ Ls;
merge2([H1|Ls1], [H2|_] = Ls2, Acc) when H1 =< H2 ->
    merge2(Ls1, Ls2, [H1|Acc]);
merge2(Ls1, [H2|Ls2], Acc) ->
    merge2(Ls1, Ls2, [H2|Acc]).

繰り返しになりますが、実際にはよくあることですが、最適化の最初のステップはアルゴリズムを調べることです。

UPD：ええと、私の例は実際にはO（m ^ 2 * n）でもあります-複雑さの点であなたよりも良くはありません。ここでおそらく必要なのは、O（m * n * ln（n））への複雑さを改善する「分割統治」アプローチです。

UPD2：前回の更新の修正と明確化：「分割統治」とは、次のアルゴリズムを意味します。

入力リストにm個のソート済みリストがあり、それぞれがn個の要素で構成されているとします。それで：

  1. 入力リストを2つのサブリストに分割し、それぞれにm/2リストを追加します
  2. このアルゴリズムをそれぞれに再帰的に適用します。
  3. 標準の2リストマージを使用して、結果の2つのソート済みリストをマージします。

このアルゴリズムの漸近的な複雑さは、実際にはO（n * m * ln（m））です。理由は次のとおりです。1。スプリット操作はすべてのスプリットレベルでO（m）であるため、無視できます。2.マージ操作はすべてのレベルでO（m * n）です。上位（最初の分割）レベルでは、 O（n * m）を持つn * m/2要素のそれぞれ2つのリストをマージする必要があります。次のレベル（2番目の分割）では、2つの独立したマージを実行する必要があります。それぞれがn * m / 4要素の2つのリストをマージします。これもO（m * n）であり、 m=2またはm=1になるまで続き ます。レベルの数は明らかにlog2（m）であるため、結果として得られる複雑さはO（n * m * ln（m））です。

実際、このアルゴリズムは、わずかに早く分割を「停止」するマージソートの単なる変形と見なすことができ（したがって、 ln（m * n）ではなくln（m ）を持ちます）、 n = 1の場合に本格的なマージソートになります（最初のアルゴリズムは事実上選択ソートになります）

于 2012-08-17T06:03:23.753 に答える