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子列表函數的性能

回答

相關問題