tomohikoのブログ: 1月 2012

2012年1月25日水曜日

Erlang ２分探索木 take_smallest 最小ノード取り出し

今日は、２分探索木の削除の一部を。

２分探索木のツリーからあるノードを削除する場合、削除対象ノードの右の部分木から最小のノードを取り出し、削除対象ノードと置き換える動作を行う。

削除の中核をなすこの動作のソースを記載したいと思う。

◆take_smallest/1
ツリーから最小ノードを取り出し、取り出した後のツリーとのタプルを返す。

【構文】
take_smallest( tree() ) -> { Key, Value, tree() }
（Key, Value:右の部分木の最小ノードのキーバリュー）
（tree():最小ノードを取り出した後のツリー）

【ソース】

-module( binary_tree_take_smallest ).
-export( [ take_smallest/1 ] ).

-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-endif.

-ifdef( debug ).
-define( T1, #tree{ key=nine, value=9 } ).
-define( Big, #tree{ key=ten, value=10 } ).
-define( Sml, #tree{ key=eight, value=8 } ).
-define( T2, #tree{ key=nine, value=9, bigger=?Big } ).
-define( T2L, #tree{ key=nine, value=9, smaller=?Sml } ).
%-define( T1, #tree{ ker=nine, 9, undefined, undefined } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=?Big } ).
-endif.

% tree()
-record( tree, { key, value, smaller, bigger } ).

%% @spec take_smallest( tree() ) -> { Key, Value, tree() }.
take_smallest( Tree ) when is_record( Tree, tree ) ->
take_smallest_1( Tree ).

take_smallest_1( #tree{ key=Key, value=Value, smaller=undefined, bigger=Bigger } ) ->
{ Key, Value, Bigger };
take_smallest_1( Tree ) ->
{ Key1, Value1, Smaller1 } = take_smallest_1( Tree#tree.smaller ),
{ Key1, Value1, Tree#tree{ smaller=Smaller1 } }.

-ifdef(debug).
t1_test() -> ?assert( { nine, 9 , undefined } =:= take_smallest_1( ?T1 ) ).
t2_test() -> ?assert( { nine, 9, ?Big } =:= take_smallest_1( ?T2 ) ).
t3_test() -> ?assert( { eight, 8, ?T1 } =:= take_smallest_1( ?T2L ) ).
t4_test() -> ?assert( { five, 5, ?T2 } =:= take_smallest_1( ?Tree ) ).
-endif.

参考：
gb_tree.erlのtake_smallest/1

2012年1月22日日曜日

Erlang ２分探索木更新 update

今日は、２分探索木の更新(update/3)を。青文字部分はユニットテストのためのソース。

仕様は以下の２点。
１．更新するノード（Key）がある場合、Valueを更新する。
２．更新するノード（Key）がない場合、対象ノードを挿入する。

◆ソース

-module( binary_tree_update ).
-export( [ update/3 ] ).

-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-define( print(Fmt, Args), io:format ( "~p:~p " Fmt "~n", [ ?MODULE, ?LINE ] ++ Args ) ).
-else.
-define( print(Fmt, Args), ok ).
-endif.

-ifdef( debug ).
-define( E, #tree{ key=nine, value=9 } ).
-define( T1, #tree{ key=nine, value=9 } ).
%-define( T1, #tree{ ker=nine, 9, undefined, undefined } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=10 } } ).
-endif.

% tree()
-record( tree, { key, value, smaller, bigger } ).
-define( procCase( X, Y ),
( begin
case is_record( SubTree1, tree ) of
false->
?print( "",[] ),
Tree;
true ->
?print( "",[] ),
Tree#tree{ X=Y }
end
end )
).
-define( ArgNode, { Key, _ } = Node ).
-define( ArgTree, #tree{ key=Key1, value=Value, smaller=Smaller, bigger=Bigger } = Tree ).
-define( procInsert( X, Y, Z), X = insert_1( Y, Z ) ).

%% @spec update( Key, Value, Tree ) -> tree()
%% Tree内にKeyが存在する場合、Valueを更新する.
%% Tree内にKeyが存在しない場合、Key/Valueのノードを挿入する.
update( Key, Value, Tree ) ->
update_1( #tree{ key=Key, value=Value }, Tree ).

update_1( Node, undefined ) ->
Node;

update_1( Node, Tree ) when Node#tree.key < Tree#tree.key ->
SubTree1 = update_1( Node, Tree#tree.smaller ),
?procCase( smaller, SubTree1 );

update_1( Node, Tree ) when Node#tree.key > Tree#tree.key ->
SubTree1 = update_1( Node, Tree#tree.bigger ),
?procCase( bigger, SubTree1 );

update_1( Node, Tree ) ->
Tree#tree{ value=Node#tree.value }.

-ifdef(debug).
%% insert test
u1_test() ->
#tree{ key=nine, value=9 }
=
update_1( ?E, undefined ).
u3_test() ->
#tree{ key=nine, value=9, smaller=#tree{ key=eight, value=8 } }
=
update_1( #tree{ key=eight, value=8 }, ?T1 ).
u4_test() ->
#tree{ key=nine, value=9, bigger=#tree{ key=ten, value=10 } }
=
update_1( #tree{ key=ten, value=10 }, ?T1 ).
u5_test() ->
#tree{ key=nine,
value=9,
smaller=
#tree{ key=five,
value=5,
smaller=#tree{ key=eight, value=8 } },
bigger=#tree{ key=ten, value=10 } }
=
update_1( #tree{ key=eight, value=8 }, ?Tree ).
%% update test
u6_test() ->?assert(
#tree{ key=nine, value=90 }
=:=
update_1( #tree{ key=nine, value=90 }, ?T1 )
).
u2_test() -> ?assert(
?Tree
=:=
update_1( ?E, ?Tree ) ).
u7_test() -> ?assert(
#tree { key=nine, value=9, smaller=#tree{ key=five, value=50 }, bigger=#tree{ key=ten, value=10 } }
=:=
update_1( #tree{ key=five, value=50 }, ?Tree ) ).
u8_test() -> ?assert(
#tree { key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=100 } }
=:=
update_1( #tree{ key=ten, value=100 }, ?Tree ) ).
-endif.

Erlang ２分探索木挿入 insert

今日は、２分探索木のinsertを作ってみた。
■insert/2
insert( Key, Value , Tree ) -> tree() | {key_exists, Value }

{key_exists, Value }はすでに同一キーがTreeにある場合。
tree()は挿入後のツリー

【ソース】

-module( binary_tree_insert ).
-export( [ insert/3 ] ).

-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-define( print(Fmt, Args), io:format ( "~p:~p " Fmt "~n", [ ?MODULE, ?LINE ] ++ Args ) ).
-else.
-define( print(Fmt, Args), ok ).
-endif.

% tree()
-record( tree, { key, value, smaller, bigger } ).
-define( procCase( X, Y ),
( begin
case is_record( SubTree1, tree ) of
false->
?print( "",[] ),
Tree;
true ->
?print( "",[] ),
Tree#tree{ X=Y }
end
end )
).
-define( ArgNode, { Key, _ } = Node ).
-define( ArgTree, #tree{ key=Key1, value=Value, smaller=Smaller, bigger=Bigger } = Tree ).
-define( procInsert( X, Y, Z), X = insert_1( Y, Z ) ).

%% @spec insert( Key, Value , Tree ) -> tree() | {key_exists, Value }
%% { key_exists, Value } = already exist.

insert( Key, Value, Tree ) ->
insert_1( #tree{ key=Key, value=Value }, Tree ).

insert_1( Node, undefined ) ->
Node;

insert_1( Node, Tree ) when Node#tree.key < Tree#tree.key ->
SubTree1 = insert_1( Node, Tree#tree.smaller ),
?procCase( smaller, SubTree1 );

insert_1( Node, Tree ) when Node#tree.key > Tree#tree.key ->
SubTree1 = insert_1( Node, Tree#tree.bigger ),
?procCase( bigger, SubTree1 );

insert_1( _, Tree ) ->
{ key_exists, Tree#tree.value }.

-ifdef(debug).
-define( E, #tree{ key=nine, value=9 } ).
-define( T1, #tree{ key=nine, value=9 } ).
%-define( T1, #tree{ ker=nine, 9, undefined, undefined } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=10 } } ).

i1_test() ->
#tree{ key=nine, value=9 }
=
insert_1( ?E, undefined ).
i2_test() ->
{ key_exists, 9 }
=
insert_1( ?E, ?Tree ).
i3_test() ->
#tree{ key=nine, value=9, smaller=#tree{ key=eight, value=8 } }
=
insert_1( #tree{ key=eight, value=8 }, ?T1 ).
i4_test() ->
#tree{ key=nine, value=9, bigger=#tree{ key=ten, value=10 } }
=
insert_1( #tree{ key=ten, value=10 }, ?T1 ).
i5_test() ->
#tree{ key=nine,
value=9,
smaller=
#tree{ key=five,
value=5,
smaller=#tree{ key=eight, value=8 } },
bigger=#tree{ key=ten, value=10 } }
=
insert_1( #tree{ key=eight, value=8 }, ?Tree ).
-endif.

参考：
M.Hiroi's Home Page / お気楽 Erlang プログラミング入門 : http://www.geocities.jp/m_hiroi/func/abcerl05.html
Erlang -- erlang : http://www.erlang.org/doc/man/erlang.html#is_record-2
letter: 2007/05 - 2007/06 : http://read-eval-print.blogspot.com/2007_05_01_archive.html
gb_tree.erlのソース

2012年1月21日土曜日

Erlang io:format デバッグ可変引数

Erlangには、可変引数がないみたい。検索に引っかからない。
どうにか、デバッグ(io:format)で可変引数っぽくできないかと考え、作ってみた。

■ソース

-module(va_args).
-export([start/0]).
-define( LOG( Fmt, Args ), io:format( Fmt, Args ) ).
-define( LOG2( Fmt, Args ), io:format( "~p:~p " Fmt, [ ?MODULE, ?LINE ] ++ Args ) ).

start() ->
?LOG( "~p~n", [test] ),
?LOG2( "~p~n", [test2] ).

■実行結果

C:\Users\andre\ework>erlc va_args.erl

C:\Users\andre\ework>erl -noshell -run va_args start -run init stop
test
va_args:8 test2

引数にフォーマットとリスト渡せば、可変引数として使える。

なぜ、デバッグでio:format？と思われるかもしれないが、まだ技術力が足りないせいである。

Erlang ２分探索木探索 lookup

今日は、２分探索木の探索についてのソースを。
【データ構造】
-record( tree, { key, value, smaller, bigger } ).
タプルだね。

【アルゴリズム】
基本的な２分探索木のサーチ

■ソース(gb_tree.erlを参考に作りました：ほぼ一緒)

-module( bin_tree ).
-export( [ lookup/2 ] ).

-ifdef( debug ).
-include_lib( "eunit/include/eunit.hrl" ).
-define( print(Fmt, Args), io:format ( "~p:~p " Fmt "~n", [ ?MODULE, ?LINE ] ++ Args ) ).
-else.
-define( print(Fmt, Args), ok ).
-endif.

% tree()
-record( tree, { key, value, smaller, bigger } ).
-define( Tree, #tree{ key=nine, value=9, smaller=#tree{ key=five, value=5 }, bigger=#tree{ key=ten, value=10 } } ).

%% @spec lookup( Target, Tree ) -> undefined | { value, Value }
lookup ( Key, T ) ->
lookup_1 ( Key, T ).

lookup_1 ( _, undefined ) ->
?print( "", [] ),
undefined;

lookup_1 ( Key, Tree ) when Key < Tree#tree.key ->
?print( "", [] ),
lookup_1 ( Key, Tree#tree.smaller );

lookup_1 ( Key, Tree ) when Tree#tree.key < Key ->
?print( "", [] ),
lookup_1 ( Key, Tree#tree.bigger );

lookup_1 ( _, Tree ) ->
?print( "", [] ),
{ value, Tree#tree.value }.

-ifdef(debug).
%-define( Tree, { nine, 9, { five, 5, undefined, undefined }, {ten, 10, undefined, undefined} } ).
-define( L(X,Y), lookup (X, Y) ).
l1_test() -> { value, 9 } = ?L( nine, ?Tree ).
l2_test() -> { value, 5 } = ?L( five, ?Tree ).
l3_test() -> { value, 10 } = ?L( ten, ?Tree ).
l4_test() -> undefined = ?L( eight, ?Tree ).
-endif.

2012年1月17日火曜日

Erlang queueモジュールによるstackモジュール作成

~~stackモジュールがないので、作ってみた。突貫で。~~
~~コンパイルとおしただけ。~~

１番下にある追記参照。

【ソース】

-module(stack).
-ifdef(debug).
-include_lib("eunit/include/eunit.hrl").
-endif.
-export([new/0,
is_stack/1,
is_empty/1,
len/1,
push/2,
pop/1,
from_list/1,
to_list/1,
reverse/1
]).
% -----
% stack of queue module
% -----
% stack()
-record( stack, { stk=undefined } ).
-define( __q, queue ).
-define( __is_q( X ), ?__q:is_queue( X ) ).
-define( __proc_q( X ), ( begin
case ?__is_q( Stack ) of
true ->
?__q:X( Stack );
_ ->
error
end
end )
).
% @spec new() -> stack()
new() ->
#stack{ stk=queue:new() }.

% @spec is_stack(Term::term()) -> boolean
is_stack( #stack{ stk=Stack } ) ->
?__is_q( Stack );
is_stack( _ ) ->
error.

% @spec is_empty(S :: stack()) -> boolean | error
%is_empty(Stack) ->
is_empty( #stack{ stk=Stack } ) ->
?__proc_q( is_empty );

is_empty( _ ) ->
error.

% @spec len( stack() ) -> integer() >= 0 | error
len( #stack{ stk=Stack } ) ->
?__proc_q( len );
len( _ ) ->
error.

% @spec push( term(), stack() ) -> stack() | error
push( Item, #stack{ stk=Stack } ) ->
case ?__is_q( Stack ) of
true ->
Stack1 = queue:in( Item, Stack ),
#stack{ stk=Stack1 };
_ ->
error
end;
push( _, _ ) ->
error.

% @spec pop( stack() ) -> {{value, term()}, stack()} | {empty, stack()} | error
pop( #stack{ stk=Stack } ) ->
Stack1 = ?__proc_q( out_r ),
case Stack1 of
{ { value, Value }, Queue } ->
{ {value, Value}, #stack{ stk=Queue } };
{ empty, Queue } ->
{ empty, #stack{ stk=Queue } };
_ ->
error
end;
pop( _ ) ->
error.

% @spec from_list( list() ) -> stack()
from_list( List ) when is_list( List ) ->
Stack = queue:from_list( List ),
#stack{ stk=Stack };
from_list( _ ) ->
error.

% @spec to_list( stack() ) -> list()
to_list( #stack{ stk=Stack } ) ->
case ?__is_q( Stack ) of
true ->
queue:to_list( Stack );
_ ->
error
end;
to_list( _ ) ->
error.

%@spec reverse( stack() ) -> stack() | error
reverse( #stack{ stk=Stack } ) ->
Stack1 = ?__proc_q( reverse ),
case Stack1 of
error ->
error;
_ ->
{ stack, Stack1 }
end;
reverse( _ ) ->
error.

Erlang 2分探索速報版

サンプル（速報版）

-module(binary_search).
-export([search/2]).
-include_lib("eunit/include/eunit.hrl").
-define(Middle,Mid = (Lo + Hi) div 2).
-ifdef(debug).
-define(print,io:format("~p:~p~n",[?MODULE,?LINE])).
-else.
-define(print,ok).
-endif.

% @spec search(Array,Target) -> {true,pos} | false
search(Array,Target) ->
i_search(Array,Target,0,array:size(Array)-1).

i_search(Array,Target,Lo,Hi) when Lo =< Hi ->
?Middle,
X = array:get(Mid,Array),
if
Target < X ->
?print,
i_search(Array,Target,Lo,Mid -1);
true ->
?print,
i_search(Array,Target,Mid + 1, Hi)
end;

i_search(Array,Target,Lo,Hi) when Lo > Hi ->
Mid = (Lo + Hi ) div 2,
X = array:get(Mid,Array),
if
Target =:= X ->
?print,
{true,Hi};
Hi =:= 0 ->
?print,
false;
true ->
?print,
false
end.

-ifdef(debug).
-define(FUNC(X,Y),search(X,Y)).
-define(AL(),array:from_list( [1,3,4,6,89] )).
s1_test() -> {true,0} = ?FUNC(?AL(),1).
s2_test() -> {true,1} = ?FUNC(?AL(),3).
s3_test() -> {true,2} = ?FUNC(?AL(),4).
s4_test() -> {true,3} = ?FUNC(?AL(),5).
s5_test() -> false = ?FUNC(?AL(),6).
-endif.

果たして、これでいいのか。

2012年1月14日土曜日

Erlang 配列による線形探索

アルゴリズムの勉強で線形探索をやっている。
cで作ったけど、Erlangでも作ってみた。
ソースを記載しておく。

こういったものはGitHubに置くべきだと思う。今セッティング中...

【ソース】
----- ここから -----
%% -------------
%% linear_search of array
%% -------------

-module(linear_search).
-export([search2_2_1/2]).
-ifdef(test).
-include_lib("eunit/include/eunit.hrl").
-endif.

% 表の線形探索
% @spec search2_2_1(Array,Target) -> {true,pos} | false
search2_2_1(Array,Target) ->
i_search2_2_1(Array,Target,0).

% @spec i_search2_2_1(Array,Target,Index) ->{true,pos} | false
i_search2_2_1(Array,Target,Index) when Index < size(Array) ->
X = array:get(Index,Array),
if
X =:= Target -> {true,Index};
true -> i_search2_2_1(Array,Target,Index + 1)
end;
i_search2_2_1(Array,Target,Index) when Index >= size(Array) ->
false.

-ifdef(test).
-define(FUNC(X,Y),search2_2_1(X,Y)).
-define(AL(),(array:from_list( [1,3,4] ))).
m1_test() -> ?FUNC(?AL(),1) =:= 0.
m2_test() -> ?FUNC(?AL(),3) =:= 1.
m3_test() -> ?FUNC(?AL(),4) =:= 2.
m4_test() -> ?FUNC(?AL(),2) =:= false.
-endif.

----- ここまで -----

次は、2分探索をErlangで書いてみたい。

Erlang Eunit の簡単な勉強

Eunitでテスト駆動開発したくて、勉強した。
参考：
shibu.jp: EUnitユーザーズガイド : http://articles.shibu.jp/category/777978-1.html

まず、上記サイトを参考にして、プログラム書いてみた。

【ソース】
----- ここから -----

-module(test_eunit).
-include_lib("eunit/include/eunit.hrl").
%-export([start/0]).
-define(TEST(X),reverse_X_test()).

-ifdef(debug).
%start() ->
% reverse_test(),
% ?TEST(nil),
% reverse_one_test(),
% reverse_two_test(),
% reverse_ng_test().

% 任意の値を返すとテストは成功とみなされる。
% なんらかの例外を投げる場合には失敗したとみなされる。
reverse_test() -> lists:reverse([1,2,3]).

?TEST(nil) -> [] = lists:reverse([]).
reverse_one_test() -> [1] = lists:reverse([1]).
reverse_two_test() -> [2,1] = lists:reverse([1,2]).
reverse_ng_test() -> [1,1] = lists:reverse([1,2]).

-endif.

----- ここまで -----

これをコマンドプロンプト上から実行した。

【コマンドプロンプト】

$> C:\Users\andre\ework>erlc -Ddebug test_eunit.erl

$> C:\Users\andre\ework>erl -noshell -run test_eunit test -run init stop

test_eunit: reverse_ng_test...*failed*

::error:{badmatch,[2,1]}

in function test_eunit:reverse_ng_test/0

=======================================================

Failed: 1. Skipped: 0. Passed: 4.

ソース上はコメントアウトされているが、start()から全テストプログラムを実行しなくていい。それが素晴らしい！

単に、xx_test()と関数名の最後にtestと付けただけで、Eunitはテスト関数だと認識してくれて、実行し、実行結果を出してくれる。いい！

defineは気にしないでX-(

Erlang arrayモジュールまとめ(size,sparse_size)

今日は、sizeとsparse_sizeについて。

■size/1
[構文]
size(Array :: array()) -> integer() >= 0

array内のエントリの数を返す。エントリは0からsize(Array)-1まで。

■sparse_size/1
[構文]
sparse_size(A::array()) -> integer()
うまく訳せない。

実行例）

Erlang R14B01 (erts-5.8.2) [smp:2:2] [rq:2] [async-threads:0]

Eshell V5.8.2 (abort with ^G)
1> D0 = [{0,1},{1,2},{4,9}].
[{0,1},{1,2},{4,9}]
5> A0 = array:from_orddict(D0,0).
{array,5,10,0,{1,2,0,0,9,0,0,0,0,0}}
7> A1 = array:set(6,0,A0).
{array,7,10,0,{1,2,0,0,9,0,0,0,0,0}}
8> array:size(A1).
7
9> array:sparse_size(A1).
5

2012年1月12日木曜日

Erlang arrayモジュールまとめ(to_list,to_orddict,sparse_to_list,sparse_to_orddict)

to_list,to_orddict,sparse_to_list,sparse_to_orddictを一気に。

注目は
to_listとsparse_to_orddictの違い
と
to_orddictとsparse_to_orddictの違い

■to_orddict(Array::array()) -> [{Index::integer(), Value::term()}]
arrayから{Index,Value}型のオーダーリストへ変換する。

■to_list(Array::array()) -> list()
arrayからリストへ変換する。

■sparse_to_orddict(Array::array()) -> [{Index::integer(), Value::term()}]
arrayから{Index,Value}型のオーダーリストへ変換する。ただし、初期値はスキップする。

■sparse_to_list(Array::array()) -> list()
arrayからリストへ変換する。ただし、初期値はスキップする。

【実行例】

Erlang R14B01 (erts-5.8.2) [smp:2:2] [rq:2] [async-threads:0]

Eshell V5.8.2 (abort with ^G)
1> L1 = [3,2,6,7].
[3,2,6,7]
2> A0 = array:from_list(L1).
{array,4,10,undefined,
{3,2,6,7,undefined,undefined,undefined,undefined,undefined,
undefined}}
4> A1 = array:set(5,5,A0).
{array,6,10,undefined,
{3,2,6,7,undefined,5,undefined,undefined,undefined,
undefined}}

8> A3 =
8>
8> array:set(9,0,A1).
{array,10,10,undefined,
{3,2,6,7,undefined,5,undefined,undefined,undefined,0}}

11> array:sparse_to_list(A3).
[3,2,6,7,5,0]
12> array:sparse_to_list(A1).
[3,2,6,7,5]
13> array:sparse_to_orddict(A3).
[{0,3},{1,2},{2,6},{3,7},{5,5},{9,0}]
14> array:sparse_to_list(A2).
[3,2,6,7]
15> array:to_list(A3).
[3,2,6,7,undefined,5,undefined,undefined,undefined,0]
16> array:to_orddict(A3).
[{0,3},
{1,2},
{2,6},
{3,7},
{4,undefined},
{5,5},
{6,undefined},
{7,undefined},
{8,undefined},
{9,0}]

Erlang arrayモジュールまとめ(map)

今日はarray:mapについて

■map/2
【構文】
map(Function, Array::array()) -> array()

　arrayの各値に対して、Functionを実行する。Indexの低い方から順に。
Functionが関数でない場合、badargエラーである。

【実行例】

1> L1 = [{1,3},{2,4},{3,6}].
[{1,3},{2,4},{3,6}]
3> A1 = array:from_orddict(L1,0).
{array,4,10,0,{0,3,4,6,0,0,0,0,0,0}}
4> Fun = fun(Index,Value) -> Index + Value end.
#Fun<erl_eval.12.113037538>
5> array:map(Fun,A1).
{array,4,10,0,{0,4,6,9,0,0,0,0,0,0}}
6>

2012年1月11日水曜日

Erlang arrayモジュールまとめ(from_orddict)

arrayモジュールのfrom_orddict関数について

なんと、{Key,Value}型を値とするリストをarrayプロセスにしてしまう。

■from_orddict(Orddict::list()) -> array()
from_list(List, undefined)と同等

■from_orddict(List::list(), Default::term()) -> array()

リストをarrayに変換する。初期値はDefaultの値。Listがリストでない場合、badargエラーである。

【実行例】
1> L0 = [{0,3},{1,4},{2,6}].
[{0,3},{1,4},{2,6}]
2> array:from_orddict(L0).
{array,3,10,undefined,
{3,4,6,undefined,undefined,undefined,undefined,undefined,
undefined,undefined}}
3> array:from_orddict(L0,0).
{array,3,10,0,{3,4,6,0,0,0,0,0,0,0}}
4> L1 = L0 ++ [{5,7},{10,9}].
[{0,3},{1,4},{2,6},{5,7},{10,9}]
5> array:from_orddict(L1).
{array,11,100,undefined,
{{3,4,6,undefined,undefined,7,undefined,undefined,undefined,
undefined},
{9,undefined,undefined,undefined,undefined,undefined,
undefined,undefined,undefined,undefined},
10,10,10,10,10,10,10,10,10}}

6> array:from_orddict(0).

** exception error: bad argument

in function array:from_orddict/2

Erlang arrayモジュールまとめ(foldl)

今日は、arrayモジュールのfoldlについて

foldは英語で折りたたむという意味。
よって、arrayプロセス内の値を引数に与えられたFunctionで計算して、１つの値を出力する。

foldlのlはleftなので、arrayのindex = 0から順に計算する。

■foldl(Function, InitialAcc::term(), Array::array()) -> term()

　Function = (Index::integer(), Value::term(), Acc::term()) -> term()

初期値と与えられたFunctionを使用し、arrayの値をFoldする。値はインデックスの低いほうから、高い方へ順に移動する。

もし、Functionが関数でない場合、badargエラーとなる。

【実行例】
1> A0 = [1,2,3,4,5].
[1,2,3,4,5]
2> A1 = array:from_list(A0,0).
{array,5,10,0,{1,2,3,4,5,0,0,0,0,0}}
3> Fun = func(Index,Value,Sum) -> Index + Sum end.
* 1: syntax error before: '->'
3> Fun = fun(Index,Value,Sum) -> Index + Sum end.
#Fun<erl_eval.18.105910772>
4> array:foldl(Fun,0,A1).
10
5> array:foldl(Fun,1,A1).
11
6> FunB = fun(Index,Value,Sum) -> Value + Sum end.
#Fun<erl_eval.18.105910772>
7> array:foldl(FunB,0,A1).
15

2012年1月10日火曜日

Erlang arrayモジュールまとめ（from_list)

夜も遅いので、軽いやつを。
リストからarrayモジュールへの変換関数。

■from_list/1
【構文】
from_list(List :: list()) -> array()
→from_list(List,undefined)と等しい。

【実行例】
18> L0 = [1,2,3,4].
[1,2,3,4]
19> array:from_list(L0).
{array,4,10,undefined,
{1,2,3,4,undefined,undefined,undefined,undefined,undefined,
undefined}}

■from_list/2
【構文】
from_list(List :: list(), Default :: term()) -> array()
→リストから拡張可能arrayモジュールへ変換します。第2引数のDefaultはarrayモジュールの初期化されていない部分の初期値に使われる。第1引数のListがリストじゃなければ、badargエラーを返す。

【実行例】

18> L0 = [1,2,3,4].
[1,2,3,4]
23> A1= array:from_list(L0,0).
{array,4,10,0,{1,2,3,4,0,0,0,0,0,0}}

■from_list/1 と from_list/2 の違い

初期値がundefinedかオプションのものか。

■その他

見てわかるとおり、初期Maxサイズは10みたい。

メモ：

実はfoldl/3の実行例を作成しようとしていたんだけど、まだちょっとよくわからないのと、いい例が見つからない。

2012年1月9日月曜日

Erlang arrayモジュールまとめ(set,relax,fix)

arrayモジュールのまとめ set,relax,fix編

■set/3
【構文】
set(I :: array_indx(), Value :: term(), Array :: array()) -> array()

インデックス I に対して、Valueを設定する。
以下の場合はエラー:badargを返す。

インデックス I が負の値
arrayプロセスがfixedであり、インデックス I が最大サイズ以上のとき

arrayプロセスがfixedでなく、インデックス I がsize(Array)-1より大きい場合は、arrayプロセスはI+1サイズに拡張される。

■relax/1
【構文】relax(Array::array()) -> array()

arrayプロセスを拡張可能にする。

■fix/1
【構文】fix(Array::array()) -> array()

arrayプロセスを固定サイズに設定する。arrayプロセスが自動的に拡張されることを防ぐ。

実行例）
3> A1 = array:new(2).
{array,2,0,undefined,10} % arrayプロセス生成
4> A2 = array:set(1,2,A1). % index = 1 に value = 2 を設定
{array,2,0,undefined,
{undefined,2,undefined,undefined,undefined,undefined,
undefined,undefined,undefined,undefined}}
5> A3 = array:set(0,3,A2). % index = 0 に value = 3 を設定
{array,2,0,undefined,
{3,2,undefined,undefined,undefined,undefined,undefined,
undefined,undefined,undefined}}
6> A4 = array:set(2,3,A3). % index = 2 に value = 3 を設定 → fixedのためbadargエラー
** exception error: bad argument
in function array:set/3

8> array:is_fix(A3). % fixedかどうか調べる
true

10> A4 = array:relax(A3). % 拡張可能にする
{array,2,10,undefined,
{3,2,undefined,undefined,undefined,undefined,undefined,
undefined,undefined,undefined}}
11> array:fix(A4). % fixedする
{array,2,0,undefined,
{3,2,undefined,undefined,undefined,undefined,undefined,
undefined,undefined,undefined}}

12> array:set(2,5,A4). % index = 2 に value = 5 を設定 → 拡張可能なため、OK。

{array,3,10,undefined, % arrayプロセスのサイズが 3 (= I + 1)となっている

{3,2,5,undefined,undefined,undefined,undefined,undefined,

undefined,undefined}}

13> array:set(11,5,A4). % index = 11 に value = 5 を設定 → 拡張可能なため、OK

{array,12,100,undefined, % arrayプロセスのサイズが 12 (= I + 1)となっている

{{3,2,undefined,undefined,undefined,undefined,undefined,

undefined,undefined,undefined},

{undefined,5,undefined,undefined,undefined,undefined,

undefined,undefined,undefined,undefined},

10,10,10,10,10,10,10,10,10}}

Erlang arrayモジュールまとめ(array:default)

今日は、arrayモジュールのdefaultについて。

defaultの構文は以下のとおり。
【構文】
default(Array::array()) -> term()

実行例）
5> A2 = array:new(5,{default,0}).
{array,5,0,0,10}

15> array:default(A2).

11> A5 = array:new(4,{default,4}).

{array,4,0,4,10}

12> array:default(A5).

1> A0 = array:new(5).

{array,5,0,undefined,10}

2> array:default(A0).

undefined

上記の実行例の赤文字の部分が返却される。

arrayプロセスを生成したときに、オプションで設定したdefaultの値が返ってくる。

オプション設定していなければ、undefinedが返ってくる。

2012年1月8日日曜日

Erlang arrayモジュールまとめ(array:new)

Erlangのarrayモジュールについて、ちょっと書きたいと思う。

R14B01のarrayモジュール一覧を下記に示す。

default/1 fix/1 foldl/3
foldr/3 from_list/1 from_list/2
from_orddict/1 from_orddict/2 get/2
is_array/1 is_fix/1 map/2
module_info/0 module_info/1 new/0
new/1 new/2 relax/1
reset/2 resize/1 resize/2
set/3 size/1 sparse_foldl/3
sparse_foldr/3 sparse_map/2 sparse_size/1
sparse_to_list/1 sparse_to_orddict/1 to_list/1
to_orddict/1

今回はnew関数について、ドキュメントを参照しつつ、Eshell？で動かしてみた。

■new/0
new()->array()

【説明】
arrayプロセスの新規生成。サイズは０。サイズを拡張可能。

例）
8> A2 = array:new().
{array,0,10,undefined,10}
9> A2.
{array,0,10,undefined,10}
10> array:size(A2).
0

■new/1

new(Options::term()) -> array()

【説明】

オプションの指定に基づいて、arrayプロセスを生成。デフォルトは、拡張可能なサイズ０のもの。indexは０から指定する。

【オプション】
オプションは単一のタプルもしくは複数のタプルのリストで指定可能。

N::integer() or {size, N::integer()}
→arrayの初期サイズ。Nが負の整数の場合、bad argumentエラー(badarg)。

例）

11> A3 = array:new(-1).
** exception error: bad argument
in function array:new_1/4

12> A3 = array:new(0).
{array,0,0,undefined,10}

13> A4 = array:new(4).
{array,4,0,undefined,10}

14> A5 = array:new({size,4}).
{array,4,0,undefined,10}

fixed or {fixed, true}
→固定サイズのarrayプロセスを生成。

例）
20> A8 = array:new([{size,5},{fixed,true}]).
{array,5,0,undefined,10}
23> array:is_fix(A8).
true

27> A9 = array:new().
{array,0,10,undefined,10}
28> array:is_fix(A9).
false

{fixed, false}
→拡張可能なarrayプロセスを生成。

例）
29> A10 = array:new([{size,2},{fixed,false}]).
{array,2,10,undefined,10}

30> array:is_fix(A10).
false

{default, Value}
→初期値Valueのarrayプロセスを生成。

例）
31> A11 = array:new([{size,2},{default,10}]).
{array,2,0,10,10}

33> A12 = array:new({size,2}).
{array,2,0,undefined,10}

■new/2
new(Size::integer(), Options::term()) -> array()

【説明】

オプションとサイズに基づいて、arrayプロセスを新規生成する。

Sizeが負の整数の場合、badargエラーである。

固定サイズで生成される。
注意：オプションでサイズを指定すれば、そのサイズで上書きされ、arrayプロセスが生成される。

例）
35> A13 = array:new([10,{default,0}]).
{array,10,0,0,10}
37> array:set(2,5,A13).
{array,10,0,0,{0,0,5,0,0,0,0,0,0,0}}

38> A14 = array:new(10).
{array,10,0,undefined,10}
39> array:set(2,5,A14).
{array,10,0,undefined,
{undefined,undefined,5,undefined,undefined,undefined,
undefined,undefined,undefined,undefined}}

2012年1月2日月曜日

Erlang queue バイナリとかリストではなくqueue

Erlangでキューってどうやるんだ？という問から検索をかけたら、バイナリでやるとかリストでやるとか出てきた。

え～・・・と思いつつ、放置↔queue検索を繰り返していたら、queueモジュールがあることがわかった。
基本操作だけやってみた。

■queue:new()->queue ------------------------------------------

空のキューを作成する。

Erlang R14B01 (erts-5.8.2) [smp:2:2] [rq:2] [async-threads:0]
Eshell V5.8.2 (abort with ^G)

1> Q = queue:new().
{[],[]}

■queue:in(term,queue)->queue ------------------------------------------

第1引数：キューに入れるもの

第2引数：操作対象のキュー

戻り：操作後のキュー

2> Q1 = queue:in(3,Q).

{[3],[]}

・・・

5> Q4 = queue:in(6,Q3).

{[6,5,4],[3]}

■queue:out(queue)->{{value, term}, queue} | {empty, queue}------------------------------------------

第1引数：対象のキュー

戻り：キュー内の先頭の値もしくは空（{empty, queue}）

6> queue:out(Q4).

{{value,3},{[6,5],[4]}}

■queue:in_r(term,queue) -> queue ------------------------------------------

第1引数：キューの先頭に入れるデータ

第2引数：操作対象のキュー

戻り：操作後のキュー

キューの先頭に値を入れる。

9> Q5 = queue:in_r(7,Q4).

{[6,5,4],[7,3]}

■queue:out(queue)->queue ------------------------------------------

第1引数：操作対象のキュー

戻り：操作後のキュー

10> queue:out(Q5).

{{value,7},{[6,5,4],[3]}}

■queue:out_r(queue)->queue ------------------------------------------

第1引数：操作対象のキュー

戻り：操作後のキュー

キューの1番最後から値をとる。

11> queue:out_r(Q5).

{{value,6},{[5,4],[7,3]}}

■queue:from_list(list)->queue ------------------------------------------

第1引数：リスト

戻り：キュー
リストからキューを作る。

15> queue:from_list([1,2,3,4,5]).
{[5,4,3],[1,2]}

■queue:to_list(queue) ->list   ------------------------------------------
第1引数：キュー
戻り：リスト

16> queue:to_list(Q5).
[7,3,4,5,6]

■queue:reverse(queue)->queue   ------------------------------------------
第1引数：キュー
戻り：キュー

17> queue:reverse(Q5).
{[7,3],[6,5,4]}

■queue:split(Integer,queue)->{queue,queue}   ------------------------------------------
第1引数：整数
第2引数：キュー
戻り：キューのタプル

20> {Q6,Q7} = queue:split(2,Q5).
{{[3],[7]},{[6,5],[4]}}

21> Q6.
{[3],[7]}
22> Q7.
{[6,5],[4]}

■queue:join(queue,queue)->queue   ------------------------------------------
第1引数：キュー
第2引数：キュー
戻り：キュー

23> queue:join(Q6,Q7).
{[6,5],[7,3,4]}

■queue:filter(fun,queue)->queue ------------------------------------------
第1引数：関数
第2引数：キュー
戻り：キュー

9> Q5 = queue:in_r(7,Q4).

{[6,5,4],[7,3]}

24> Fun1 = fun(X) -> true end.
#Fun<erl_eval.6.13229925>
25> queue:filter(Fun1,Q5).
{[6,5,4],[7,3]}

26> Fun2 = fun(X) -> false end.
#Fun<erl_eval.6.13229925>
27> queue:filter(Fun2,Q5).
{[],[]}

28> Fun3 = fun(X) -> if X rem 2 == 0 -> true;
28> true -> false end
28> end.
#Fun<erl_eval.6.13229925>
29> queue:filter(Fun3,Q5).
{[6],[4]}
30> Q5.
{[6,5,4],[7,3]}

■queue:member(term,queue)->boolean ------------------------------------------
第1引数：データ
第2引数：キュー
戻り：真偽

9> Q5 = queue:in_r(7,Q4).

{[6,5,4],[7,3]}

31> queue:member(3,Q5).
true
32> queue:member(10,Q5).
false

登録: 投稿 (Atom)