array型 - az-prolog @ ウィキ

az-prologでは配列のような入れ子型は、
リスト型とは別にアレイ型というものがあります。
アレイには大量にデータを入れることができるので、
単位節の代わりに使うと便利です。

簡単に単位節をassertする時間と、
単位節の一番先頭を削除するretractする時間を調べる
ベンチマークプログラムを作成してみました。

test:-
	timecount(  1000),
	timecount(  5000),
	timecount( 10000),
	timecount( 30000),
	timecount( 50000),
	timecount( 70000),
	timecount(100000),
	timecount(300000),
	timecount(500000),
	true.

timecount(X):-
 A is cputime,
 create_func(X),
 B is cputime,
 C is B-A,
 retract(func(X)),
 D is cputime -B,
 abolish(func,1),
 write_listnl(['Num:',X,' create_time:',C,' retract_time:',D]).

create_func(0).
create_func(N):-M is N-1,assert(func(N)),create_func(M).

テストしてみましょう。

||?-test.
Num:1000 create_time:0.000999927520751953 retract_time:0.00300002098083496
Num:5000 create_time:0.00300002098083496 retract_time:0.0620000362396240
Num:10000 create_time:0.00600004196166992 retract_time:0.260999917984009
Num:30000 create_time:0.0160000324249268 retract_time:2.47800016403198
Num:50000 create_time:0.0679998397827148 retract_time:7.28299999237061
Num:70000 create_time:0.0300002098083496 retract_time:16.6899998188019
Num:100000 create_time:0.0880000591278076 retract_time:40.6140000820160
Heap area exausted       ---- Backtrace
assert(func(90341)) create_func(300000) timecount(300000) test ?-

ヒープ領域がオーバーフローしてしまいました。
これを防ぐのはprolog立ち上げ時にコマンドオプションでヒープ領域を指定しておきましょう。

prolog -h 10000

再度テストしてみましょう。

| ?-test.
Num:1000 create_time:0.000000000000000 retract_time:0.00199985504150391
Num:5000 create_time:0.00200009346008301 retract_time:0.0609998703002930
Num:10000 create_time:0.00399994850158691 retract_time:0.249000072479248
Num:30000 create_time:0.0109999179840088 retract_time:2.29399991035461
Num:50000 create_time:0.0190000534057617 retract_time:7.05999994277954
Num:70000 create_time:0.0279998779296875 retract_time:16.8590002059937
Num:100000 create_time:0.0399999618530273 retract_time:40.8570001125336
Num:300000 create_time:0.198000192642212 retract_time:457.813999891281
Num:500000 create_time:1.27499985694885 retract_time:1301.64199995995

create時間が線形的になっていません。
特にretractが数が多くなるごとに時間が多く掛かっています。
この場合、単位節自身を更新しながら追加するような処理には向かないことが分かります。
(例:好きな食べ物の集計 func(焼き肉,3人) →func(焼き肉,4人))
このような時にアレイ型を使うとこの問題が解消されます。

次にアレイ型のベンチマークプログラムを作ってみました。

test:-
	timecount(    1000),
	timecount(    5000),
	timecount(   10000),
	timecount(   30000),
	timecount(   50000),
	timecount(   70000),
	timecount(  100000),
	timecount(  300000),
	timecount(  500000),
	timecount(  700000),
	timecount( 1000000),
	timecount( 3000000),
	timecount( 5000000),
	timecount( 7000000),
	timecount(10000000),
	true.

timecount(X):-
 Y is X-1,
 A is cputime,
 create_array(X,Z),
 B is cputime,
 C is B-A,
 
 D is cputime,
 sets_array(Z,Y),
 E is cputime,
 F is E-D,
 
 G is cputime,
 gets_array(Z,Y),
 H is cputime,
 I is H-G,
 write_listnl(['Num:',X,' create_time:',C,' sets_time:',F,' gets_time:',I]).

sets_array(Z,-1).
sets_array(Z,N):-set_array(Z,N,N),M is N-1,sets_array(Z,M).

gets_array(Z,-1).
gets_array(Z,N):-get_array(Z,N,T),M is N-1,gets_array(Z,M).

setとgetは経過時間が数に比例して線形的に増加していることが分かります。

Num:1000 create_time:0.000000000000000 sets_time:0.000999927520751953 gets_time:0.000000000000000
Num:5000 create_time:0.000000000000000 sets_time:0.00199985504150391 gets_time:0.00100016593933105
Num:10000 create_time:0.000000000000000 sets_time:0.00300002098083496 gets_time:0.00399994850158691
Num:30000 create_time:0.000000000000000 sets_time:0.00899982452392578 gets_time:0.00900006294250488
Num:50000 create_time:0.000000000000000 sets_time:0.0150001049041748 gets_time:0.0139999389648438
Num:70000 create_time:0.000000000000000 sets_time:0.0210001468658447 gets_time:0.0299999713897705
Num:100000 create_time:0.000999927520751953 sets_time:0.0290000438690186 gets_time:0.0269999504089355
Num:300000 create_time:0.000999927520751953 sets_time:0.0970001220703125 gets_time:0.0950000286102295
Num:500000 create_time:0.00199985504150391 sets_time:0.164000034332275 gets_time:0.160000085830688
Num:700000 create_time:0.00200009346008301 sets_time:0.230999946594238 gets_time:0.216000080108643
Num:1000000 create_time:0.00300002098083496 sets_time:0.322000026702881 gets_time:0.319999933242798
Num:3000000 create_time:0.00999999046325684 sets_time:0.983000040054321 gets_time:0.944999933242798
Num:5000000 create_time:0.0170001983642578 sets_time:1.59099984169006 gets_time:1.57400012016296
Num:7000000 create_time:0.0250000953674316 sets_time:2.26300001144409 gets_time:2.21700000762939
Num:10000000 create_time:0.0350000858306885 sets_time:3.21299982070923 gets_time:3.21100020408630