Erlang で LinkedList

Erlang に慣れるために、LinkedList を書いてみました。
レコード（実態はタプル）の中に入れ子式に要素を追加していく感じです。

でも

パフォーマンスはとてもよろしくないです。
プリミティブなリスト（言い方が正確ではないかもしれませんが）を使ったほうが 10 倍くらい早いです。

ソースコード

実装はこちらのサイトを参考にさせて頂きました。
API については http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/util/LinkedList.html を参考にさせて頂きました。

list, node という 2 種類のレコードを用意し、 node の next という要素に次の node が入るようにしました。

linkedlist.erl

-module(linkedlist).
-compile(export_all).

-record(list, {head, length = 0}).
-record(node, {data, next}).

new() ->
    #list{}.

new_node(Data) ->
    #node{data=Data}.

head(List) ->
    List#list.head.

next(Node) ->
   Node#node.next.

length(List) ->
    List#list.length.

% ---------------------------------------------------------------------------------------
% Append the specified Node to the end of the list.
% ---------------------------------------------------------------------------------------
add(Data, List) when List =:= #list{} ->
    % when the list is empty
    % create new node (= head node)
    #list{head = new_node(Data), length = 1};
add(Data, List) ->
    % when the list is not empty
    NewHead = append_node(Data, head(List)),
    NewLength = linkedlist:length(List) + 1,
    #list{head = NewHead, length = NewLength}.
    
append_node(Data, Node) when Node#node.next =:= undefined ->
    % when the node does not know the next node (= the Node is Tail Node)
    Node#node{next = new_node(Data)};
append_node(Data, Node) ->
    % when the node know the next node
    % re-construct the Node
    Node#node{next = append_node(Data, Node#node.next)}.

% ---------------------------------------------------------------------------------------
% Inserts the specified Node at the specified position in the list.
% Shifts the Node currently at that position (if any)
% and any subsequent Nodess to the right. 
% 
% @throw indexOutOfBoundsException - if the specified index is out of range 
% (index < 0 || index >= size()).
% ---------------------------------------------------------------------------------------
add(_, Index, List) when ((List#list.length < Index) or (Index < 0)) ->
    % if the specified position is larger than List length,
    % throw excpetion.
    throw("indexOutOfBoundException");
add(Data, Index, List) when List#list.length =:= Index ->
    % if the specified position is same as the List length,
    % appends Node to the end of the list.
    add_last(Data,List);
add(Data, Index, List) when Index =:= 0 ->
    % if the specified position is 0,
    % insert the Node at the first position (=Head Node)
    add_first(Data, List);
add(Data, Index, List) ->
    % inserts Node at the specified position.
    NewHead = insert_node(Data, Index, 0, List#list.head),
    NewLength = linkedlist:length(List) + 1,
    #list{head = NewHead, length = NewLength}.

insert_node(Data, Index, Current, Node) when Index =:= Current ->
    % constructs the subsequent Node(s)
    #node{data = Data, next = Node};
insert_node(Data, Index, Current, Node) ->
    % steps forward
    NextNode = insert_node(Data, Index, Current + 1, Node#node.next),
    Node#node{next = NextNode}.

% ---------------------------------------------------------------------------------------
% Inserts the given Node at the beginning of this list.
% ---------------------------------------------------------------------------------------
add_first(Data, List) ->
    NewHead = #node{data = Data, next = head(List)},
    NewLength = linkedlist:length(List) + 1,
    #list{head = NewHead, length = NewLength}.

% ---------------------------------------------------------------------------------------
% Append the specified Node to the end of the list.
% (Identical in add/2 function; included only for consistency.) 
% ---------------------------------------------------------------------------------------
add_last(Data, List) ->
    add(Data, List).

% ---------------------------------------------------------------------------------------
% Removes the head Node of this list.
%
% @throw noSuchElementException - if this list is empty.
% ---------------------------------------------------------------------------------------
remove(List) when List#list.head =:= undefined ->
    throw("noSuchElementException");
remove(List) ->
    #list{head = (List#list.head)#node.next, length = List#list.length -1}.

% ---------------------------------------------------------------------------------------
% Removes the Node at the specified position in this list.
% Shifts any subsequent Nodes to the left (subtracts one from their indices). 
%
% @throw indexOutOfBoundsException - if the specified index is out of range (index < 0 || index >= size()).
% ---------------------------------------------------------------------------------------
remove(Index, List) when ((List#list.length < Index) or (Index < 0)) ->
    throw("indexOutOfBoundException");
remove(Index, List) when Index =:= 0 ->
    % if the specified position is 0,
    % removes the first Node (= Head Node)
    remove_first(List);
remove(Index, List) when Index =:= List#list.length - 1 ->
    % if the specified position is the last position,
    % removes the last Node (= Tail Node)
    remove_last(List);    
remove(Index, List) ->
    % removes the Node at the specified position
    NewHead = remove_node(Index, 0, List#list.head),
    NewLength = List#list.length - 1,
    #list{head = NewHead, length = NewLength}.
    
remove_node(Index, Current, Node) when Index =:= Current ->
    % constructs the subsequent Node(s)
    NextNode = Node#node.next,
    #node{data = NextNode#node.data, next = NextNode#node.next};

remove_node(Index, Current, Node) ->
    % steps forward
    NextNode = remove_node(Index, Current + 1, Node#node.next),
    Node#node{next = NextNode}.

% ---------------------------------------------------------------------------------------
% Removes the Node of at the begining of this list (=Head Node).
% (Identical in remove/0 function; included only for consistency.) 
%
% @throw noSuchElementException - if this list is empty.
% ---------------------------------------------------------------------------------------
remove_first(List) ->
    remove(List).

% ---------------------------------------------------------------------------------------
% Removes and returns the last Node from this list.
% ---------------------------------------------------------------------------------------
remove_last(List) -> 
    NewHead = remove_last(List#list.head, List),
    NewLength = List#list.length - 1,
    #list{head = NewHead, length = NewLength}.

remove_last(Node, _) when Node#node.next =:= undefined ->
    undefined;
remove_last(Node, List) ->
    % steps forward
    NextNode = remove_last(Node#node.next, List),
    Node#node{next = NextNode}.

% ---------------------------------------------------------------------------------------
% Returns true if this list contains the specified Node. 
% More formally, returns true if and only if this list contains at least one Node.
% ---------------------------------------------------------------------------------------
contains(_, List) when List#list.length =:= 0 ->
    false;
contains(Data, List) ->
    search_data(Data, List#list.head).

search_data(Data, Node) when Data =:= Node#node.data ->
    true;
search_data(_, Node) when Node#node.next =:= undefined ->
    false;
search_data(Data, Node) ->
    search_data(Data, Node#node.next).

% ---------------------------------------------------------------------------------------
% Gets the Nth Node from the list
% 
% @throw indexOutOfBoundsException - if the specified index is out of range (index < 0 || index >= size()).
% ---------------------------------------------------------------------------------------
nth(Index, List) when ((List#list.length < Index) or (Index < 0)) -> 
    throw("indexOutOfBoundException");
nth(Index, List) ->
    nth(Index, 0, List#list.head).

nth(Index, Current, Node) when Index =:= Current ->
    Node;
nth(Index, Current, Node) ->
    % steps forward
    nth(Index, Current + 1, Node#node.next).

% ---------------------------------------------------------------------------------------
% Replaces the Node at the specified position in this list with the specified Node. 
%
% @throw indexOutOfBoundsException - if the specified index is out of range (index < 0 || index >= size()).
% ---------------------------------------------------------------------------------------
set(_, Index, List) when ((List#list.length < Index) or (Index < 0)) ->
    % if the specified position is larger than List length,
    % throw excpetion.
    throw("indexOutOfBoundException");
set(Data, Index, List) ->
    % replaces Node at the specified position.
    NewHead = insert_node(Data, Index, 0, List#list.head),
    NewLength = linkedlist:length(List) + 1,
    #list{head = NewHead, length = NewLength}.

set_node(Data, Index, Current, Node) when Index =:= Current ->
    % constructs the subsequent Node(s)
    #node{data = Data, next = Node};
set_node(Data, Index, Current, Node) ->
    % steps forward
    NextNode = insert_node(Data, Index, Current + 1, Node#node.next),
    Node#node{next = NextNode}.

テスト

データを追加したり削除したりするテスト。

t_linkedlist.erl

-module(t_linkedlist).
-compile(export_all).

% ---------------------------------------------------------------------------------------
% test function
% ---------------------------------------------------------------------------------------
main() ->
%    DataList = [data0, data1, data2, data3, data4, data5, data6, data7, data8],
    L = linkedlist:new(),
    test_list(L, "* New List"),
    L0 = linkedlist:add(data0, L),
    test_list(L0, "* add data0"),
    L1 = linkedlist:add(data1, L0),
    test_list(L1, "* add data1"),
    L2 = linkedlist:add(data2, L1),
    test_list(L2, "* add data2"),
    L3 = linkedlist:add_last(data3, L2),
    test_list(L3, "* add_last data3"),
    L4 = linkedlist:add_first(data4, L3),
    test_list(L4, "* add_first data4"),
    L5 = linkedlist:add(data5, 3, L4),
    test_list(L5, "* add data5 @ index=3"),
    L6 = linkedlist:remove(L5),
    test_list(L6, "* remove (head)"),
    L7 = linkedlist:remove_last(L6),
    test_list(L7, "* remove_last"),
    L8 = linkedlist:remove_first(L7),
    test_list(L8, "* remove_first"),
    ok.

test_list(List, Description) ->
    io:format("~s~n", [Description]),
    erlang:display(List),
    io:format("\n"),
    ok.

実行

29> t_linkedlist:main().
* New List
{list,undefined,0}
* add data0
{list,{node,data0,undefined},1}
* add data1
{list,{node,data0,{node,data1,undefined}},2}
* add data2
{list,{node,data0,{node,data1,{node,data2,undefined}}},3}
* add_last data3
{list,{node,data0,{node,data1,{node,data2,{node,data3,undefined}}}},4}
* add_first data4
{list,{node,data4,{node,data0,{node,data1,{node,data2,{node,data3,undefined}}}}},5}
* add data5 @ index=3
{list,{node,data4,{node,data0,{node,data1,{node,data5,{node,data2,{node,data3,undefined}}}}}},6}
* remove (head)
{list,{node,data0,{node,data1,{node,data5,{node,data2,{node,data3,undefined}}}}},5}
* remove_last
{list,{node,data0,{node,data1,{node,data5,{node,data2,undefined}}}},4}
* remove_first
{list,{node,data1,{node,data5,{node,data2,undefined}}},3}
ok

ちゃんと動くようです。

とりあえず、add_first と add_last をプリミティブのリストを使った場合と比較したいと思います。

プリミティブな List (?) を利用した実装

リストの Head に add するのは簡単ですが、Tail に add する場合の実装方法は考える必要がありました。

一旦 Node を全て Head に add して、最後の最後に lists:reverse/1 を行う方法
- これだと、並行処理した場合に List 内要素の並び順が保証されないかも？
毎回 add する度に、 lists:reverse([Data|lists:reverse(List)]). とやる方法
- lists:reverse のコストによっては凄く遅くなりそう。
リスト結合の中間演算子 ++ を使う方法。
- ex) List ++ [Data]
- たぶん Joe に怒られる*1

ソースコード

prim_list.erl

-module(prim_list).
-compile(export_all).

new() ->
    [].

% ---------------------------------------------------------------------------------------
% Append the specified Node to the end of the list. (by reversing list each time)
% ---------------------------------------------------------------------------------------
add(Data, List) ->
    lists:reverse([Data|lists:reverse(List)]).

% ---------------------------------------------------------------------------------------
% Append the specified Node to the end of the list. (using ++ operator)
% ---------------------------------------------------------------------------------------
poor_add(Data, List) ->
    List ++ [Data].

% ---------------------------------------------------------------------------------------
% Inserts the given Node at the beginning of this list.
% ---------------------------------------------------------------------------------------
add_first(Data, List) ->
    [Data|List].

測定結果

たくさんノードを add してみました。

add_first

# of Nodes (nodes)	linkedlist (microseconds)	prim_list (microseconds)
1,000	141	38
2,000	242	91
3,000	321	126
4,000	417	144
5,000	572	179
10,000	1,037	428
20,000	2,617	811
30,000	3,485	1,065
40,000	4,683	2,076
50,000	5,888	1,950

プリミティブなリストの方が 3 倍程度早いですね。。。

add_last

プリミティブなリストには上記の 3 通りの方法 (最後に reverse する方法、毎回 reverse する方法、++ を使う方法) を試しました。

		reverse once	reverse each time	using ++
# of Nodes (nodes)	linkedlist (microseconds)	prim_list (microseconds)
1,000	45,406	39	2,790	2,006
2,000	185,735	77	12,653	9,631
3,000	402,851	116	34,848	30,081
4,000	723,359	208	68,384	47,920
5,000	1,123,141	261	118,364	81,040
10,000	4,565,314	513	481,990	32,844
20,000	18,286,288	1,003	1,993,936	1,346,024
30,000	41,103,235	2,389	4,372,823	3,000,710
40,000	73,152,422	2,452	7,747,635	5,211,024
50,000	116,033,399	4,464	12,242,963	8,540,952

自作 linkedlist は話になりません。。。lists:reverse のコストは結構かかりますね。 add したい要素はまとめて Head に add して、最後に一度だけ lists:reverse/1 する方法が一番早いようです。

勉強にはなりました

色々と funciton を書いたのですが、結局使い物にならない LinkedList を作ってしまいました。
しかし、Erlang での逐次プログラミングの書き方がほんの少しだけ分ってきた気がします。
無名関数、高階関数、エラー処理をもっとうまく使えるようになりたいなぁ。

測定に使ったコード

自前 LinkedList の測定用コード

spec_linkedlist.erl

-module(spec_linkedlist).
-compile(export_all).

main(N) ->
    io:format("---- # of Nodes = ~p ----~n", [N]),
    display("Add Node at the beg", timer:tc(spec_linkedlist, test_add_first, [N])),
    display("Add Node to the end", timer:tc(spec_linkedlist, test_add_last, [N])),
    ok.
    
display(Description, {Time, ok}) ->
    io:format("~p: Time = [~p] microseconds~n", [Description, Time]).

% ---------------------------------------------------------------------------------------
% Test function to Append N Nodes to the end of the list
% ---------------------------------------------------------------------------------------
test_add_last(N) ->
    List = linkedlist:new(),
    add_last_for(1, N, List),
    ok.

add_last_for(N, N, List) -> linkedlist:add(N, List);
add_last_for(I, N, List) -> add_last_for(I+1, N, linkedlist:add(I, List)).

% ---------------------------------------------------------------------------------------
% Test function to Append N Nodes at the begining of the list
% ---------------------------------------------------------------------------------------
test_add_first(N) ->
    List = linkedlist:new(),
    add_first_for(1, N, List),
    ok.

add_first_for(N, N, List) -> linkedlist:add_first(N, List);
add_first_for(I, N, List) -> add_first_for(I+1, N, linkedlist:add_first(I, List)).

プリミティブリストの測定用コード

-module(spec_primlist).
-compile(export_all).

main(N) ->
    io:format("---- # of Nodes = ~p ----~n", [N]),
    display("Add Node at the beg                               ", timer:tc(spec_primlist, test_add_first, [N])),
    display("Add Node to the end (reverse once)                ", timer:tc(spec_primlist, test_add_rev_once, [N])),
    display("Add Node to the end (reverse each time)           ", timer:tc(spec_primlist, test_add_rev, [N])),
    display("Add Node to the end (poor implemantation using ++)", timer:tc(spec_primlist, test_poor_add, [N])),
    ok.
    
display(Description, {Time, ok}) ->
    io:format("~p: Time = [~p] microseconds~n", [Description, Time]).

% ---------------------------------------------------------------------------------------
% Test function for Append N Nodes to the end of the list.
%  (reverse each time)
% ---------------------------------------------------------------------------------------
test_add_rev(N) ->
    List = prim_list:new(),
    add_rev_for(1, N, List),
    ok.

add_rev_for(N, N, List) -> prim_list:add(N, List);
add_rev_for(I, N, List) -> add_rev_for(I+1, N, prim_list:add(I, List)).

% ---------------------------------------------------------------------------------------
% Test function for Append N Nodes to the end of the list.
%  (poor implementation using ++)
% ---------------------------------------------------------------------------------------
test_poor_add(N) ->
    List = prim_list:new(),
    poor_add_for(1, N, List),
    ok.

poor_add_for(N, N, List) -> prim_list:poor_add(N, List);
poor_add_for(I, N, List) -> poor_add_for(I+1, N, prim_list:poor_add(I, List)).

% ---------------------------------------------------------------------------------------
% Test function for Append N Nodes to the end of the list.
%  (reverse at the end of adding Nodes process) 
% ---------------------------------------------------------------------------------------
test_add_rev_once(N) ->
    List = prim_list:new(),
    lists:reverse(add_first_for(1, N, List)),
    ok.

% ---------------------------------------------------------------------------------------
% Test function for Append N Nodes at the begining of the list.
% ---------------------------------------------------------------------------------------
test_add_first(N) ->
    List = prim_list:new(),
    add_first_for(1, N, List),
    ok.

add_first_for(N, N, List) -> prim_list:add_first(N, List);
add_first_for(I, N, List) -> add_first_for(I+1, N, prim_list:add_first(I, List)).

実行結果

51> lists:map(fun(N) -> spec_primlist:main(N) end, L).
---- # of Nodes = 1000 ----
"Add Node at the beg ": Time = [38] microseconds
"Add Node to the end (reverse once) ": Time = [39] microseconds
"Add Node to the end (reverse each time) ": Time = [2790] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [2006] microseconds
---- # of Nodes = 2000 ----
"Add Node at the beg ": Time = [91] microseconds
"Add Node to the end (reverse once) ": Time = [77] microseconds
"Add Node to the end (reverse each time) ": Time = [12653] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [9631] microseconds
---- # of Nodes = 3000 ----
"Add Node at the beg ": Time = [126] microseconds
"Add Node to the end (reverse once) ": Time = [116] microseconds
"Add Node to the end (reverse each time) ": Time = [34838] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [30081] microseconds
---- # of Nodes = 4000 ----
"Add Node at the beg ": Time = [144] microseconds
"Add Node to the end (reverse once) ": Time = [208] microseconds
"Add Node to the end (reverse each time) ": Time = [68384] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [47920] microseconds
---- # of Nodes = 5000 ----
"Add Node at the beg ": Time = [179] microseconds
"Add Node to the end (reverse once) ": Time = [261] microseconds
"Add Node to the end (reverse each time) ": Time = [118364] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [81040] microseconds
[ok,ok,ok,ok,ok]
52> lists:map(fun(N) -> spec_linkedlist:main(N) end, L).
---- # of Nodes = 1000 ----
"Add Node at the beg": Time = [141] microseconds
"Add Node to the end": Time = [45406] microseconds
---- # of Nodes = 2000 ----
"Add Node at the beg": Time = [242] microseconds
"Add Node to the end": Time = [185735] microseconds
---- # of Nodes = 3000 ----
"Add Node at the beg": Time = [321] microseconds
"Add Node to the end": Time = [402851] microseconds
---- # of Nodes = 4000 ----
"Add Node at the beg": Time = [417] microseconds
"Add Node to the end": Time = [723359] microseconds
---- # of Nodes = 5000 ----
"Add Node at the beg": Time = [572] microseconds
"Add Node to the end": Time = [1123141] microseconds
[ok,ok,ok,ok,ok]
53> L1 = [10000, 20000, 30000, 40000, 50000].
[10000,20000,30000,40000,50000]
54> lists:map(fun(N) -> spec_primlist:main(N) end, L1).
---- # of Nodes = 10000 ----
"Add Node at the beg ": Time = [428] microseconds
"Add Node to the end (reverse once) ": Time = [513] microseconds
"Add Node to the end (reverse each time) ": Time = [481990] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [328444] microseconds
---- # of Nodes = 20000 ----
"Add Node at the beg ": Time = [811] microseconds
"Add Node to the end (reverse once) ": Time = [1003] microseconds
"Add Node to the end (reverse each time) ": Time = [1993936] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [1346024] microseconds
---- # of Nodes = 30000 ----
"Add Node at the beg ": Time = [1065] microseconds
"Add Node to the end (reverse once) ": Time = [2389] microseconds
"Add Node to the end (reverse each time) ": Time = [4372823] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [3000710] microseconds
---- # of Nodes = 40000 ----
"Add Node at the beg ": Time = [2076] microseconds
"Add Node to the end (reverse once) ": Time = [2452] microseconds
"Add Node to the end (reverse each time) ": Time = [7747635] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [5211024] microseconds
---- # of Nodes = 50000 ----
"Add Node at the beg ": Time = [1950] microseconds
"Add Node to the end (reverse once) ": Time = [4466] microseconds
"Add Node to the end (reverse each time) ": Time = [12242963] microseconds
"Add Node to the end (poor implemantation using ++)": Time = [8540952] microseconds
[ok,ok,ok,ok,ok]
55> lists:map(fun(N) -> spec_linkedlist:main(N) end, L1).
---- # of Nodes = 10000 ----
"Add Node at the beg": Time = [1037] microseconds
"Add Node to the end": Time = [4565314] microseconds
---- # of Nodes = 20000 ----
"Add Node at the beg": Time = [2617] microseconds
"Add Node to the end": Time = [18286288] microseconds
---- # of Nodes = 30000 ----
"Add Node at the beg": Time = [3485] microseconds
"Add Node to the end": Time = [41103235] microseconds
---- # of Nodes = 40000 ----
"Add Node at the beg": Time = [4683] microseconds
"Add Node to the end": Time = [73152422] microseconds
---- # of Nodes = 50000 ----
"Add Node at the beg": Time = [5888] microseconds
"Add Node to the end": Time = [116033399] microseconds
[ok,ok,ok,ok,ok]

*1:「もし次のようなコードを見かけたら: List ++ [H] 頭の中で警報が鳴り響くようでないといけない。」- プログラミング Erlang P.53