hinekure.net が http://hspdev-wiki.net/ から自動クローリングした結果を表示しています。画像やリソースなどのリンクが切れています。予めご了承ください。
オブジェクトID/HSP3 - HSP開発wiki
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS

小ワザ

[hsp3]

オブジェクトID for HSP3

割り当てられるオブジェクトIDを取得する

オブジェクトIDの割り当てルールから、BMSCR構造体からオブジェクト管理領域へのポインタmem_objをたどってオブジェクトのハンドルが無効(0,NULL)かどうかを順番に調べる方法がまず考えられると思います。

+  SAMPLE1

ただし、この方法は線形探索でアルゴリズム的には最も簡単で、最も遅い方法です。
オブジェクトが多くなれば時間がかかることは明白です。(実際には制限が1024個なので最悪のケースでもかかる時間は微々たるものだと思います。)

この方法は使用/未使用IDをプログラマが自己管理していないため、直接システムを参照するしかない、採らざるを得ない方法です。
ただしシステムを直接参照するので自己管理の手間が省ける分、メモリ消費は最も小さくなります。

配列を用いて自己管理する

次に配列を用いて未使用かどうかを自己管理するサンプルです。
ここでも探索アルゴリズムは線形探索で行っていきます。

+  SAMPLE2

オブジェクトIDの使用状況は配列変数recで管理されています。
オブジェクトを割り当てる時は、直前に配列変数recを先頭から順番に未使用(FREE)のIDを探します。
この方法はSAMPLE1と大して変わらない上に自己管理のためのメモリを消費してしまいます。

中心となる操作の計算量
使用中IDの探索
選出したIDが使用中かどうかは配列要素の添え字を指定して参照するだけで取得できるのでO(1)のオーダーで実行できます。
再利用IDの登録
再利用IDの登録は配列要素の添え字を指定して未使用フラグを立てるだけなので0(1)のオーダーで実行できます。
再利用IDの検索
配列要素を先頭から順番に検索するので0(N)のオーダーがかかります。

「次に割り当てられるIDを管理」するためのデータ構造

ここで改めて管理方法を考え直してみると、オブジェクトIDがもれなく割り当てられていれば、次に割り当てられるIDは「現在のオブジェクトの数」だけで取得できます。
なぜ管理が必要なのかといえば、ところどころ削除したりして未使用のIDがあるために、割り当てられるIDが一定でないからです。

このため、「次に割り当てられるIDを管理する」データが必要になってきますが、これは現在のオブジェクトの数と再利用されるIDとその数を管理すれば実現できます。
また、(平均すると)すべてのIDの使用状況を管理せずに済み、消費メモリも減らすことができ、あらかじめ管理用データのサイズを決めておかなくても済みます。

+  SAMPLE3

SAMPLE3で再利用されるIDを管理しているのがリサイクルテーブルと呼んでいる配列recです。
オブジェクトを削除したらリサイクルテーブルに削除したIDを登録します。
オブジェクトを作成する際はリサイクルテーブルを調べ、再利用可能なIDがあれば利用し、リサイクルテーブルからそのIDを削除します。

中心となる操作の計算量
使用中IDの探索
選出したIDが使用中かどうかはリサイクルテーブルに登録されていないIDなのでO(N)のオーダーがかかります。*1
再利用IDの登録
リサイクルテーブルをソート状態に保つため、適切な位置へ挿入するのにO(N)のオーダーがかかります。*2
再利用IDの検索
リサイクルテーブルがソート状態にあるため、最小のIDはO(1)のオーダーで取得できます。

コメント

  • 私の欠点は結論にたどり着くまでの前置きが長すぎること... -- kz3 2007-01-01 (月) 18:00:12
  • いやいや、前置きがあるからこそ納得するんですから(^^;) -- ちたん? 2007-01-01 (月) 23:19:20
  • あーちたんさんコメントありがとうございます。これでちたんさんも開発wiki仲間ですね [bsmile2]サンプルの動作が混乱しそうですが、注目すべき動作は、「削除されたオブジェクトがIDの若いものから再利用されている」かつ「再利用されたオブジェクトのチェック状態が適切に反映されている」の2点です。チェック状態が適切に反映されているのは、オブジェクトを実際に配置する前に割り当てられるIDが取得できていて、きちんと配列chkの添え字と一致しているからですね。 -- kz3 2007-01-03 (水) 13:48:55
  • 選出したIDのオブジェクトを配置する(../HSP2)のとは違うので注意です。 -- kz3 2007-01-03 (水) 14:27:10

URL B I U SIZE Black Maroon Green Olive Navy Purple Teal Gray Silver Red Lime Yellow Blue Fuchsia Aqua White

*1 リサイクルテーブルがソート状態にあることを利用して探索アルゴリズムを変えればオーダーをO(N)以下に抑えることができる。
*2 リサイクルテーブルをソート状態に保つための整列アルゴリズムを変えればオーダーをO(N)以下に抑えることができる。
添付ファイル:
filev3_057_GetNextObjectID.hsp
128件 [詳細]
filev3_056_GetNextObjectID.hsp
144件 [詳細]
トップ    編集凍結 差分バックアップ添付複製名前変更リロード   新規一覧単語検索最終更新   最終更新のRSS
Last-modified: 2007-04-08 (日) 02:38:50 (2436d)