拆分在二郎相等大小的块列表(Splitting a list in equal sized chun

2019-07-31 18:58发布

我想分裂:

[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秒。 我也写了一个非常快的递归函数,但我只是感兴趣:莫非这个list解析也被写入以不同的方式,所以这是更快?

Answer 1:

试试这个:

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]).

测试在二郎山壳(我已经声明模块该功能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毫秒)



Answer 2:

这里有你,既灵活的两个快速的解决方案。 一个易于阅读,但只比你提出的解决方案稍快。 另一种是比较快的,但它是一个有点神秘阅读。 并注意我的两个建议的算法将用于什么名单,而不仅仅是数字有序列表工作。

这里是“轻松阅读”之一。 通过调用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)我做了一个改变这与上面的一个比较,因为它垫的结束列表与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).

在测试了我的(真的老了)笔记本电脑:

  • 你提出的解决方案花了约3秒钟。
  • 我缓慢但可读的一个稍微更快,需要大约1.5秒(仍然很慢)
  • 我的快速版本大约需要5毫秒。
  • 为了完整起见,ISAC的解决方案把我的同一台机器上大约180毫秒。

编辑:哇,我需要先阅读完整的问题。 哦,好吧,我会继续在这里为后人是否有帮助。 据我所知,有没有做到这一点使用列表内涵的好方法。 你原来的版本是缓慢的,因为每个迭代sublist需要每次遍历列表去每个连续的X ,导致复杂性略低于O(N ^ 2)。



Answer 3:

或用褶皱:

  lists:foldr(fun(E, []) -> [[E]]; 
                 (E, [H|RAcc]) when length(H) < 2 -> [[E|H]|RAcc] ;
                 (E, [H|RAcc]) -> [[E],H|RAcc]
              end, [], List).


Answer 4:

我想稍微提交复杂,但更灵活(而且大多更快)由@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%。



Answer 5:

你可以做这样的:

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]|...]

这需要〜73毫秒与我的计算机上的10000元列表。 原来的解决方案利用〜900毫秒。

不过,我想用递归函数反正去。



Answer 6:

我一直在寻找一个分区功能,可以大名单分裂工人的少量。 随着lkuty的partition ,你可能会得到一个工人得到比其他人几乎增加一倍的工作。 如果这不是你想要的,这里是一个子列表长度至多1不同版本。

采用适当的测试。

%% @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))
           ).


Answer 7:

下面是与任何子列表大小的作品更普遍的答案。

1> lists:foreach(fun(N) -> io:format("~2.10.0B -> ~w~n",[N, test:partition([1,2,3,4,5,6,7,8,9,10],N)]    ) end, [1,2,3,4,5,6,7,8,9,10]).
01 -> [[1],[2],[3],[4],[5],[6],[7],[8],[9],[10]]
02 -> [[1,2],[3,4],[5,6],[7,8],[9,10]]
03 -> [[1,2,3],[4,5,6],[7,8,9],[10]]
04 -> [[1,2,3,4],[5,6,7,8],[10,9]]
05 -> [[1,2,3,4,5],[6,7,8,9,10]]
06 -> [[1,2,3,4,5,6],[10,9,8,7]]
07 -> [[1,2,3,4,5,6,7],[10,9,8]]
08 -> [[1,2,3,4,5,6,7,8],[10,9]]
09 -> [[1,2,3,4,5,6,7,8,9],[10]]
10 -> [[1,2,3,4,5,6,7,8,9,10]]

和代码来实现,这是存储在文件名为里面test.erl

-module(test).
-compile(export_all).

partition(List, N) ->
    partition(List, 1, N, []).

partition([], _C, _N, Acc) ->
    lists:reverse(Acc) ;

partition([H|T], 1, N, Acc) ->
    partition(T, 2, N, [[H]|Acc]) ;

partition([H|T], C, N, [HAcc|TAcc]) when C < N ->
    partition(T, C+1, N, [[H|HAcc]|TAcc]) ;

partition([H|T], C, N, [HAcc|TAcc]) when C == N ->
    partition(T, 1, N, [lists:reverse([H|HAcc])|TAcc]) ;

partition(L, C, N, Acc) when C > N ->
    partition(L, 1, N, Acc).

这或许可以更优雅关于其中C> N.注意,C是当前子表的规模正在建造的特殊情况。 在开始时,它是1。然后它递增,直到它到达N的分区大小

我们也可以使用@chops代码的修改版本,让最后一个列表包含了剩余的项目,即使其尺寸<N:

-module(n_length_chunks_fast).

-export([n_length_chunks_fast/2]).

n_length_chunks_fast(List,Len) ->
    SkipLength = case length(List) rem Len of
        0 -> 0;
        N -> Len - N
    end,
    n_length_chunks_fast(lists:reverse(List),[],SkipLength,Len).

n_length_chunks_fast([],Acc,_Pos,_Max) -> 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).


Answer 8:

我稍微改变从@JLarky实施,取下保护的表达,这应该是稍快:

split_list(List, Max) ->
    element(1, lists:foldl(fun
        (E, {[Buff|Acc], 1}) ->
            {[[E],Buff|Acc], Max};
        (E, {[Buff|Acc], C}) ->
            {[[E|Buff]|Acc], C-1};
        (E, {[], _}) ->
            {[[E]], Max}
    end, {[], Max}, List)).


文章来源: Splitting a list in equal sized chunks in Erlang
标签: erlang