erlang - 在 Erlang 中将列表拆分为相等大小的块

Question

我想拆分：

[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 秒。我还写了一个非常快的递归函数，但我只是感兴趣：这个列表理解是否也可以用不同的方式编写，以便更快？

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

在 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 毫秒）

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)与上面的相比，我对此做了一个更改，因为它用undefinedif 长度填充列表的末尾列表的 不能被所需的块长度完全整除。

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

这是一个更通用的答案，适用于任何子列表大小。

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 7

我正在寻找一个分区函数，它可以将大列表拆分为少量工人。使用 lkuty partition，您可能会发现一名工人的工作量几乎是其他所有工人的两倍。如果这不是您想要的，这里是一个子列表长度最多相差 1 的版本。

使用PropE进行测试。

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