Erlang子列表函数的性能

我在阅读http://learnyousomeerlang.com/其中包括一个尾部递归子列表函数，它颠倒了列表以保持顺序。我写了一个不需要反向调用的替代方案。我的效率是否更高（当然更详细，但我不关心）或者我忽略了一些东西？Erlang子列表函数的性能

-module(sublist). 

-export([sublist/2,sublistR/2]). 

-include_lib("eunit/include/eunit.hrl"). 

sublist(_,0) -> 
    []; 
sublist([],_) -> 
    []; 
sublist(List,Length) -> 
    sublist([hd(List)], tl(List), Length-1). 

sublist(Acc,[],_) -> 
    Acc; 
sublist(Acc,_,0) -> 
    Acc; 
sublist(Acc,Tail,Length) -> 
    sublist(Acc++[hd(Tail)], tl(Tail), Length-1). 

sublistR(L, N) -> lists:reverse(sublistR(L, N, [])). 

sublistR(_, 0, SubList) -> SubList; 
sublistR([], _, SubList) -> SubList; 
sublistR([H|T], N, SubList) when N > 0 -> 
    sublistR(T, N-1, [H|SubList]). 

sublist_test() -> 
    sublisttest(fun sublist:sublist/2), 
    sublisttest(fun sublist:sublistR/2). 

sublisttest(SublistFunc) -> 
    [] = SublistFunc([],10), 
    [] = SublistFunc([1,2,3], 0), 
    [1,2,3] = SublistFunc([1,2,3],3), 
    [1,2,3] = SublistFunc([1,2,3],4), 
    [1,2] = SublistFunc([1,2,3],2).

来源

2014-12-13 Myles McDonnell

TL;博士：不可以，但不要失去心脏 - 你所要求的准确正确的问题，并在代码中进行正确的实验以真正实现计算出你的自学。这是一件好事！ – zxq9 2014-12-13 14:48:44

不，不过感觉不好，这是每个人都必须在早期达成共识的。

它的所有这样的说法：

AcC++ [hd(Tail)]

比方说Acc = [1,2,3]是真实的。然后AcC++ [hd(Tail)]直接等于[1,2,3 | [Head]]。这是什么意思？

在这种特殊情况下这意味着它是正是一样的车Acc写出每一个元素和使用的[hd(Tail)]的结果作为一个新的利弊的CDR。这意味着要将单个元素连接到现有列表的末尾，必须遍历整个列表（用于解构，以显示最终的cdr）。另一方面，将单个元素添加到列表的开始是一个简单的操作。

在使用lists:reverse/1（以及在使用cons风格列表的语言中这是习惯用法的全部原因）的神奇之处在于它是用C语言实现的数组操作，而不是您正在编写的对象语言的扩展然后。

访问的最后一个元素是昂贵VS访问的第一个元素这个问题的原因hd/1（或其他语言head()）返回一个列表的第一个元素，但tl/1（或其他语言tail()）返回的一切但是列表的第一个元素。保证访问列表最后一个元素的函数的使用通常包含警告“这很慢！”。

这也是为什么你会很少看到任何人使用几乎任何语言foldr。如果他们确实需要从右侧折叠（比如说，因为非交换操作），他们通常会先执行lists:reverse/1，然后再调用foldl。 foldl可以是尾递归的，但真的foldr不能。

实际上，Erlang的文档具有此一提：http://www.erlang.org/doc/man/lists.html#foldl-3

从右侧随着清单的长度增加折叠的成本。这就是发生这种情况的原因：

1> AMillionThings = lists:seq(1, 1000000). 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 
23,24,25,26,27,28,29|...] 
2> OneThing = [0]. 
[0] 
3> timer:tc(fun() -> OneThing ++ AMillionThings end). 
{13, 
[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 
    23,24,25,26|...]} 
4> timer:tc(fun() -> AMillionThings ++ OneThing end). 
{31291, 
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22, 
    23,24,25,26,27|...]}

13μsvs31291μs。哎哟。

另见：

来源

2014-12-13 14:39:40 zxq9

伟大的，宝贵的答案，谢谢！ – 2014-12-13 16:36:18

PS。定时器：tc模块以微秒（us）而不是毫秒（ms）返回已用时间，http://erlang.org/doc/man/timer.html#tc-1 – Shawn 2015-02-06 20:37:24

@Shawn事实上，我使用了错误的单位时间符号！我现在纠正了它。感谢您的高举。 :-) – zxq9 2015-02-07 04:48:52

Erlang子列表函数的性能

回答

相关问题