在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中测试(我在模块中声明了这个函数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).