リスト構造と配列

[dfiq054]

今、プレイヤーの弾管理を作っているところなのですが、少し疑問に思ったため質問しました。
リスト構造を使って弾管理をしようとしていたのですが、ここに投稿されていた質問を見てみると
「リスト構造も配列も速度はあまり変わらない。むしろ遅くなる可能性もある」との回答がついていたのですが
あるサイトを見てみると配列で管理するよりもリスト構造で管理するほうが速いと書いてありどちらが正しいのでしょうか？
速度が変わらないのなら配列で管理したほうがいいと思うのですが、どうなんでしょう？

・リスト構造にすると、毎回メモリの確保・解放を行うため配列よりも遅くなる。
・配列にすると、空いている場所を探索するためリスト構造よりも遅くなる。

という風に解釈したのですが、どちらで管理するのがベストでしょうか？

[box]

「弾管理」の内容によると思います。
弾の数の上限はあるのか、追加・削除・探索・並べ替えなどが必要なのか不要なのか、
等々、どういう風に管理したいかによってどういうデータ構造を選ぶのがよいかが決まると思います。
配列・リスト構造とも、得手・不得手があると思いますので。

[dfiq054]

ご返信ありがとうございます。
弾管理の内容ですが、発射されていない弾を探して、発射できる状態であればフラグを立て、
発射中の弾には、移動処理をし、表示する。
というものです。
以前作成していたゲームでは弾のようなものを配列で管理していました。

また、リスト構造の場合、線形リスト・双方向リストではやはり双方向リストで管理すべきですよね？

[nil]

boxさんが既におっしゃっていますが、双方とも利点と欠点があります。
あと、場合にもよりますが、たいていはリストのほうが遅くなります。

newと配列に空きを探す作業では後者のほうが圧倒的に速いです(前述のとおり場合によりますが、dfiq054さんの求めているような用途で用いる場合はそうでしょう)。

逆にリストの利点としては、
出せる弾の数に上限がない(メモリの許す限りは)。
空きを探す関数をわざわざ定義する必要がない(push_backでOKなら)。

あとこれは本に載っていたことなのですが、
ゲームであれば敵には『弾を少ししか出さないもの』、『大量に出すもの』など様々な種類が必要になりますよね？
『少ししか出さない敵』にも『大量に出す敵』にも同じサイズの配列を持たせてやるとするならば、
そこには無駄が発生します。
それをリスト構造なら最小限に減らせるわけです。

ここまで書いておいてあれですが、
速度やメモリは3Dでもない限り気にしない方が良いと思います。
最近のパソコンはメモリは4GB以上CPUはi3以上なんていうのがざらなので、newなんかにもさほど時間はかかりませんし、
特に気にする必要もないのです。
しかも、newは重い、とは言ってもゲームの処理で大抵の場合一番時間がかかるのは描画です。
それに、速度を気にしていると堂々巡りになってしまうこともありますし……。
『今は』気にしないのが吉だと思います。

[softya（ソフト屋)]

ここで違う視点で提案を。
どうやったら管理しやすいかメンテしやすいかの視点で考えてみたらどうでしょうか？
メモリが足らなくなるとか、速度が遅くなるとか考えるのは抜きにしてですよ。

例えば弾の重なりが多く、重ね合わせの順番を考える必要があるのならソートは重要なキーワードになります。
あるいは、生成。消滅が繋がったデータで発生する場合が多い場合生成・消滅を一度に管理できるリスト構造は有利です。
またあるいは、ランダムに弾の情報にアクセスする必要があるなら配列のほうが便利で有利でしょう。
場合によっては配列とリストのハイブリッドで管理したほうが良いかも知れません。

つまり、要求される仕様でデータ構造の最適が決まるのでシューティングの弾だからという理由ではデータ構造は決まらないと言うことです。

[dfiq054]

みなさん回答ありがとうございます。

たしかに、気にするほど速度が遅くなるというわけでもないですね。
前作っていたゲームでも、正直弾の処理はそこまで重くならず、アニメーションや、画面の切り替わりのほうが断然遅くなっていました。
少し気にしすぎていたのかもしれません。
これから作る敵に関しても、よく考えてから配列にするかリストにするか決めたいと思います。
管理のしやすさでいうと、リストのほうがわかりやすいですが、作りやすさでいうとやはり配列なので、プレイヤーに関しては配列で作ってみようと
思います。
また、弾のアクセスの仕方ですが、ひとつひとつの弾に何か特殊な効果があるわけでもないので、リストで作る必要もなさそうです。
しかし、敵の管理となるとリストのほうが管理・メンテしやすそうなのでそこらへんは作るときになったら考えることにします。

こんな質問に回答していただきありがとうございます！
また利用するかもしれませんが、そのときはよろしくおねがいします。

[beatle]

管理のしやすさでいうと、リストのほうがわかりやすいですが、作りやすさでいうとやはり配列なので

お使いの言語はC++ですよね？
そうだとすれば，この際STLに入門してみてはいかがでしょうか．

STLはC++の標準ライブラリなので，どのようなC++処理系を使っていても使えます．
STLには動的配列（vector）や線形リスト（list）が用意されています．

これらを使うと，「配列の方が作るのが楽」ということはありません．
vectorを使っていたところをlistに切り替える，なんてこともやりやすいですし．
STLにはこれらの他にも便利なデータ構造が用意されていますので，是非勉強してみてください．