制作日記

こういうの作った方が、逃げにくいじゃない

trigger参照の重さ

http://drabs.blog40.fc2.com/blog-entry-427.html
気が向いたので、上記記事の追加調査
ほんの少し、真面目に書いてみる

1.概要
 省略

2. "trigger"参照に掛かる秒数の調査
 ステート-2にnullステが一個あるだけのキャラを2体(以後、それぞれA,Bと呼称)用意
 以下の調査結果から、"trigger"参照に掛かる時間を算出した

2.1. AとBのnullステに"trigger1 = 1"をx個置き、1フレームの秒数を調査
 2500個:0.0090909……秒/F(110FPS)
 5000個:0.0259740……秒/F(38.5FPS)
 7500個:0.0540540……秒/F(18.5FPS)

2.2. Aのnullステに"trigger1 = 1"をx個、Bには1個だけ置き、1フレームの秒数を調査
 2500個:0.00625秒/F(160FPS)
 5000個:0.0147058……秒/F(68FPS)
 7500個:0.0285714……秒/F(35FPS)

2.3. 調査1,2の結果から差を取り、"trigger"参照に掛かった秒数を求める
 2500個:0.0028409……秒
 5000個:0.0112681……秒
 7500個:0.0254826……秒

3.考察
 2.3.の結果より、"trigger"参照に掛かる時間は、"trigger"の個数の2乗に比例していることがわかる
 よって、"trigger"の個数が極端に多い場合は、論理演算等を用いて"trigger"数を減らすことで、
 処理を軽くすることができる
 ただし、高確率で偽を返すような条件は、単独かつ優先的に判定するべきであり、
 軽量化のために"trigger"をまとめるべきとは断言できない

てな感じで、どうでしょう
続い、もっと込み入った内部的なデータ構造のお話
まず、ステコンについて
これは大体こんな感じ
struct stctrl{
struct trigger* trigger;
int enable;
int persistent;
int ignorehitpause;


省略


};
省略部分にはvalueとか。


で、便宜的にtrigger構造体って名前にしたけど、こいつポインタを2つもってる。
片方が、triggerの内容の配列
もう片方が、triggerの種類の配列

前者は"trigger1 = var(0)"の"var(0)"の部分
具体的には12バイトの構造体の配列
1とか2みたいに即値を指定した場合は、先頭4バイトにその値が入っていて、残り8バイトは0埋め
それ以外の説明は面倒なので、省略

後者は"trigger1 = var(0)"の"trigger1"とか何個目に置いてあるかとかの情報
こいつはこんな感じ
struct trigger_info{
int enable;
int pos;
int type;
int trigger_pos;
};

変数名は良いのが思いつかなかった
ebableはそのtriggerが有効かどうか(多分)
posは上から何個目にあるか
typeは1とか2とかallとかの情報
trigger_posはtrigger1とかtriggerallの中で、上から何個目にあるか

こっちの情報をtrigger参照のたびに上から順番に調べるから、
全トリガー参照の計算量がO(n^2)になってるっぽいね
このデータ構造はどうなんだろうか

trigger1とかtrigger2を別の配列にぶち込むだけで計算量はO(n)で済むのに、
なんでこんなことするの?

と思うけど、そんなにtriggerの数が多くなることなんてあり得ないから、そこまで考えないか
そんな数バイト、数十バイトのためにmallocするのはメモリの無駄遣いだしねー
mallocしたら、まず指定したバイト数+4バイトが確保されて、さらにポインタで4バイト
更にメモリアロケータが管理する用にいくらか確保される
ちびちび確保するから、大きく確保するよりメモリの利用効率も落ちるねー
mallocの回数が増えるから、メモリ確保に掛かる時間で読み込み時間増大

良いことないじゃん!

データ構造はこのままで、ぶちこむときにちゃんとソートすべきだね
ソートしとけば全参照の計算量もO(n)で済む
大量のtriggerを想定したデータ構造じゃないんだし、
読み込みとかソートで増える時間も微量と見なしていいはず
それなら、読み込み時1回と毎フレーム、どっちを軽くすべきかというと……

コメントの投稿

非公開コメント

プロフィール

Author:drab
霊夢改変キャラ
「12 3 ! {V} [_]」
公開中
L霊夢でもl_reimuでも好きなように読んでください

最新記事
最新コメント
月別アーカイブ
カテゴリ
検索フォーム
RSSリンクの表示
リンク