分割したい：
[1,2,3,4,5,6,7,8]
の中へ：
[[1,2],[3,4],[5,6],[7,8]]
それは一般的にうまく機能します：
[ lists:sublist(List, X, 2) || X <- lists:seq(1,length(List),2) ] .
しかし、この方法では本当に遅いです。10000要素は私のネットブックで驚くべき2.5秒かかります。私も非常に高速な再帰関数を作成しましたが、単に興味があります。このリスト内包表記を別の方法で記述して、より高速にすることはできますか？
これを試して：
part(List) ->
part(List, []).
part([], Acc) ->
lists:reverse(Acc);
part([H], Acc) ->
lists:reverse([[H]|Acc]);
part([H1,H2|T], Acc) ->
part(T, [[H1,H2]|Acc]).
erlang-shell でテストします (この関数は module で宣言しましたpart):
2> part:part([1,2,3,4,5,6,7,8]).
[[1,2],[3,4],[5,6],[7,8]]
3>
3> timer:tc(part, part, [lists:seq(1,10000)]).
{774,
[[1,2],
[3,4],
[5,6],
[7,8],
"\t\n","\v\f",
[13,14],
[15,16],
[17,18],
[19,20],
[21,22],
[23,24],
[25,26],
[27,28],
[29,30],
[31,32],
"!\"","#$","%&","'(",")*","+,","-.","/0","12","34",
[...]|...]}
わずか 774 マイクロ秒 (約 0.8 ミリ秒)
どちらも柔軟な 2 つの簡単なソリューションを次に示します。1つは読みやすいですが、提案されたソリューションよりもわずかに高速です。もう 1 つは非常に高速ですが、読むには少し難解です。そして、私が提案したアルゴリズムは両方とも、数値の順序付けられたリストだけでなく、あらゆるリストに対して機能することに注意してください。
これが「読みやすい」ものです。までお電話くださいn_length_chunks(List,Chunksize)。たとえば、長さ 2 のチャンクのリストを取得するには、 を呼び出しますn_length_chunks(List,2)。これは、任意のサイズのチャンクで機能します。つまり、取得するために呼び出すことができn_length_chunks(List,4)ます[[1,2,3,4],[5,6,7,8],...]
n_length_chunks([],_) -> [];
n_length_chunks(List,Len) when Len > length(List) ->
[List];
n_length_chunks(List,Len) ->
{Head,Tail} = lists:split(Len,List),
[Head | n_length_chunks(Tail,Len)].
はるかに高速なものはここにありますが、間違いなく読みにくく、同じ方法で呼び出されます: (上記n_length_chunks_fast(List,2)のものと比較して、これに1つの変更を加えました.undefinedリストの は、目的のチャンクの長さできれいに割り切れません。
n_length_chunks_fast(List,Len) ->
LeaderLength = case length(List) rem Len of
0 -> 0;
N -> Len - N
end,
Leader = lists:duplicate(LeaderLength,undefined),
n_length_chunks_fast(Leader ++ lists:reverse(List),[],0,Len).
n_length_chunks_fast([],Acc,_,_) -> Acc;
n_length_chunks_fast([H|T],Acc,Pos,Max) when Pos==Max ->
n_length_chunks_fast(T,[[H] | Acc],1,Max);
n_length_chunks_fast([H|T],[HAcc | TAcc],Pos,Max) ->
n_length_chunks_fast(T,[[H | HAcc] | TAcc],Pos+1,Max);
n_length_chunks_fast([H|T],[],Pos,Max) ->
n_length_chunks_fast(T,[[H]],Pos+1,Max).
私の（本当に古い）ラップトップでテストしました：
編集：うわー、最初に完全な質問を読む必要があります。それが助けになるなら、私は後世のためにここにとどめておきます。私が知る限り、リスト内包表記を使用してこれを行う良い方法はありません。の各反復はsublist、連続する各 に到達するために毎回リストをトラバースする必要があるため、元のバージョンは遅くX、O(N^2) のすぐ下で複雑になります。
または折り目を付けて：
lists:foldr(fun(E, []) -> [[E]];
(E, [H|RAcc]) when length(H) < 2 -> [[E|H]|RAcc] ;
(E, [H|RAcc]) -> [[E],H|RAcc]
end, [], List).
@Tilmanによって提案されたものの、少し複雑だがより柔軟な（そしてほとんどがより高速な）ソリューションを提出したい
split_list(List, Max) ->
element(1, lists:foldl(fun
(E, {[Buff|Acc], C}) when C < Max ->
{[[E|Buff]|Acc], C+1};
(E, {[Buff|Acc], _}) ->
{[[E],Buff|Acc], 1};
(E, {[], _}) ->
{[[E]], 1}
end, {[], 0}, List)).
したがって、関数部分は次のように実装できます
part(List) ->
RevList = split_list(List, 2),
lists:foldl(fun(E, Acc) ->
[lists:reverse(E)|Acc]
end, [], RevList).
更新 順序を維持したい場合に備えて逆を追加しましたが、見ることができるように、処理時間の 20% しか追加されません。
大きなリストを少量のワーカーに分割できるパーティション関数を探していました。lkuty'spartitionを使用すると、1 人のワーカーが他のすべてのワーカーよりもほぼ 2 倍の仕事をしていることがわかる場合があります。それが望ましくない場合は、サブリストの長さが最大で 1 異なるバージョンを次に示します。
テストにはPropErを使用します。
%% @doc Split List into sub-lists so sub-lists lengths differ most by 1.
%% Does not preserve order.
-spec split_many(pos_integer(), [T]) -> [[T]] when T :: term().
split_many(N, List) ->
PieceLen = length(List) div N,
lists:reverse(split_many(PieceLen, N, List, [])).
-spec split_many(pos_integer(), pos_integer(), [T], [[T]]) ->
[[T]] when T :: term().
split_many(PieceLen, N, List, Acc) when length(Acc) < N ->
{Head, Tail} = lists:split(PieceLen, List),
split_many(PieceLen, N, Tail, [Head|Acc]);
split_many(_PieceLen, _N, List, Acc) ->
% Add an Elem to each list in Acc
{Appendable, LeaveAlone} = lists:split(length(List), Acc),
Appended = [[Elem|XS] || {Elem, XS} <- lists:zip(List, Appendable)],
lists:append(Appended, LeaveAlone).
テスト:
split_many_test_() ->
[
?_assertEqual([[1,2]], elibs_lists:split_many(1, [1,2])),
?_assertEqual([[1], [2]], elibs_lists:split_many(2, [1,2])),
?_assertEqual([[1], [3,2]], elibs_lists:split_many(2, [1,2,3])),
?_assertEqual([[1], [2], [4,3]], elibs_lists:split_many(3, [1,2,3,4])),
?_assertEqual([[1,2], [5,3,4]], elibs_lists:split_many(2, [1,2,3,4,5])),
?_assert(proper:quickcheck(split_many_proper1())),
?_assert(proper:quickcheck(split_many_proper2()))
].
%% @doc Verify all elements are preserved, number of groups is correct,
%% all groups have same number of elements (+-1)
split_many_proper1() ->
?FORALL({List, Groups},
{list(), pos_integer()},
begin
Split = elibs_lists:split_many(Groups, List),
% Lengths of sub-lists
Lengths = lists:usort(lists:map(fun erlang:length/1, Split)),
length(Split) =:= Groups andalso
lists:sort(lists:append(Split)) == lists:sort(List) andalso
length(Lengths) =< 2 andalso
case Lengths of
[Min, Max] -> Max == Min + 1;
[_] -> true
end
end
).
%% @doc If number of groups is divisable by number of elements, ordering must
%% stay the same
split_many_proper2() ->
?FORALL({Groups, List},
?LET({A, B},
{integer(1, 20), integer(1, 10)},
{A, vector(A*B, term())}),
List =:= lists:append(elibs_lists:split_many(Groups, List))
).
次のようにできます。
1> {List1, List2} = lists:partition(fun(X) -> (X rem 2) == 1 end, List).
{[1,3,5|...],[2,4,6|...]}
2> lists:zipwith(fun(X, Y) -> [X, Y] end, List1, List2).
[[1,2],[3,4],[5,6]|...]
これには、コンピューター上の 10000 要素のリストで約 73 ミリ秒かかります。元のソリューションには約 900 ミリ秒かかります。
しかし、とにかく再帰関数を使用します。