シューティング ： リストと配列

[メンマ]

シューティングゲーム製作中の初心者です。
現在シューティングでの弾幕及び敵を配列で管理しているのですが、これをリストに変更しようと考えています。
しかし、例えば一度に１０００発の弾を生成するような処理が起こった場合、１０００発分の動的メモリ確保をすることになると思います。動的メモリ確保には時間がかかるものなのかどうかがわからず、処理時間に遅延がでないかを懸念しています。
配列で管理している現在は弾は最初に生成しておき、登録時にフラグ変数を変更するだけの処理になっています。

変数を変更する処理と比較して動的メモリ確保の処理はやはり遅いのでしょうか？トンチンカンなことを聞いているのかもしれませんがその場合は勉強できるサイトなどを教えていただけると幸いです。ご意見、ご回答よろしくおねがいしますｍ（_ _）ｍ

[softya（ソフト屋)]

> 変数を変更する処理と比較して動的メモリ確保の処理はやはり遅いのでしょうか？ト

早くはないですが致命的かはプログラムの組み方次第です。
ただポインタ利用などプログラムの複雑度は上がるので、メンテナンス性は下がり、バグの発生度が上がり、バグ追求の難易度も上がります。
それを超えるメリットや、勉強のためという理由がない限りはデメリットのほうが多いと思います。
動的管理にしなければいけない理由を教えて下さい。

[メンマ]

動的確保のリストにしようと考えた理由としましては

１．配列の場合、毎フレーム配列の最大数分フラグが立っているかどうかを調べなければいけないため、リストにして必要分だけの処理にしたほうが無駄がないのではないか。

２．設定した最大数分以上弾を生成しようとした場合、配列だと生成できないがリストで動的確保をするとその数に縛られず自由に生成できる。また、実際には弾の数は最大数以下の状態が多く、動的確保にしたほうがメモリの節約にもなるのではないか。

以上のように考えたからです。
しかし、質問文のように動的メモリ確保にはどれくらい処理時間がかかるかわからず、弾を同時にたくさん生成した時一気に重くなるのであればやめたほうがいいかなあ・・・と思い質問させていただきました。
ある程度スペックの低いPCでも動かせるようにできるだけ配慮したいと考えています。多少なら複雑度、バグの難易度が上がることは気にしないのですが、一時的にでも処理速度に影響がでるのであればやめておこうと思います。

考えていることがあっているかどうかもわからないので、誤りがあればご指摘くださると幸いです。

[softya（ソフト屋)]

１．少なくともフラグ判定よりはnew/mallocのコストは大きいです。メモリが細かく分断されるほどコストアップします。
ただ、メンマさんがリストと呼んでいるもののアルゴリズムによっても変わります。１つづつ確保せずに１００個づつ確保するなどテクニックもあります。

【補足】
ちょっと語弊があるので補足です。
new/mallocのコストは大きいですが、new/mallocされていない間はフラグのコストもそれなりにあります。
瞬間コストと継続コストで、どちらが問題に成るか考えてみる必要があります。

２．メモリをどれだけ使っているか計算してみたほうが良いと思います。昔のパソコン(PC98)なら問題でも今のパソコンでは問題にならないことが多いです。

【追記】
あれこれ悩んでいるよりも計測用の弾幕プログラムを作って何パターンか実装を試してみた方が良い経験になります。
計測方法やら、様々なアルゴリズムに触れる良い機会だと思いますけどね。

[みけCAT]

両方のいいところを取って、毎回動的にオブジェクト(弾)のデータ領域を確保することはないが、
リストで無駄なくアクセスできるようにする、というのはどうでしょうか？

例えば、このような実装が考えられます。

コード:

#include <cstdio>
#include <iterator>

template<typename T>
class data_supplier {
	private:
		// データの最大数
		size_t max_num;
		T *data; // データ本体
		// データを格納する領域の情報
		struct data_link_t {
			T *data;
			data_link_t *prev; // 前のデータ領域
			data_link_t *next; // 次のデータ領域
		} *data_link;
		// 先頭と末尾のデータの位置
		data_link_t *head;
		data_link_t *tail;
		// データの空き位置を管理するキュー(リングバッファ)
		data_link_t **empty_queue;
		size_t empty_start, empty_end, empty_count;
		// コピー・代入を許可しない
		data_supplier(const data_supplier<T>& d) {}
		data_supplier<T>& operator=(const data_supplier<T>& d) const {
			return *this;
		}
		// キューの操作
		bool is_queue_empty() const {return empty_count == 0;}
		bool is_queue_full() const {return empty_count == max_num;}
		data_link_t *dequeue() {
			if (is_queue_empty()) return 0;
			data_link_t *ret = empty_queue[empty_start];
			empty_start = (empty_start + 1) % max_num;
			empty_count--;
			return ret;
		}
		void enqueue(data_link_t *v) {
			if (is_queue_full()) return;
			empty_queue[empty_end] = v;
			empty_end = (empty_end + 1) % max_num;
			empty_count++;
		}
	public:
		// イテレータの定義
		class iterator : public std::iterator<std::input_iterator_tag, T*> {
			friend class data_supplier;
			private:
				// 参照先のデータの情報
				data_supplier::data_link_t *data;
				data_supplier::data_link_t data_end;
				// 勝手にイテレータを作られないようにする
				iterator(){}
				iterator(data_link_t* d, data_link_t* prev = NULL) {
					data = d;
					data_end.prev = prev;
				}
			public:
				// コピーコンストラクタ
				iterator(const data_supplier& d) {
					data = d.data;
					data_end = d.data_end;
				}
				// 進める
				iterator& operator++() {
					if (data->next == NULL) {
						data_end.data = NULL;
						data_end.prev = data;
						data_end.next = NULL;
						data = &data_end;
					} else {
						data = data->next;
					}
					return *this;
				}
				iterator operator++(int) {
					iterator bak = *this;
					++(*this);
					return bak;
				}
				// データを取得する
				T* operator*() const {
					return data->data;
				}
				// 比較する
				bool operator==(const iterator& it) const {
					data_link_t* d = data;
					data_link_t* itd = it.data;
					if (d == &data_end) d = NULL;
					if (itd == &it.data_end) itd = NULL;
					return d == itd;
				}
				bool operator!=(const iterator& it) const {
					return !(*this == it);
				}
		};

		// 先頭要素のイテレータを返す
		iterator begin() const {
			return iterator(head);
		}
		// 末尾のイテレータを返す
		iterator end() const {
			return iterator(NULL, tail);
		}

		// 初期化
		data_supplier(size_t max = 1) {
			max_num = max;
			// 領域の確保
			data = new T[max];
			data_link = new data_link_t[max];
			head = NULL;
			tail = NULL;
			for (size_t i = 0; i < max_num; i++) {
				data_link[i].data = &data[i];
			}
			// キューの初期化
			empty_queue = new data_link_t*[max];
			empty_start = 0;
			empty_end = 0;
			empty_count = max_num;
			for (size_t i = 0; i < max_num; i++) {
				empty_queue[i] = &data_link[i];
			}
		}
		// 開放
		~data_supplier() {
			delete[] data;
			delete[] data_link;
			delete[] empty_queue;
		}
		// 全消し
		void clear() {
			head = NULL;
			tail = NULL;
			empty_start = 0;
			empty_end = 0;
			empty_count = max_num;
			for (size_t i = 0; i < max_num; i++) {
				empty_queue[i] = &data_link[i];
			}
		}
		// 新しいデータの追加
		T* create_new_data() {
			if (is_queue_empty()) {
				return NULL;
			} else {
				// 次のデータ領域を取得する
				data_link_t *next_data = dequeue();
				// リストの先頭に追加する
				if (head == NULL) {
					head = next_data;
					head->prev = NULL;
					head->next = NULL;
					tail = head;
				} else {
					data_link_t *old_head = head;
					head = next_data;
					head->prev = NULL;
					head->next = old_head;
					old_head->prev = head;
				}
				return next_data->data;
			}
		}
		// データの削除
		iterator delete_data(const iterator& it) {
			if (it == end()) return it;
			data_link_t *prev = it.data->prev;
			data_link_t *next = it.data->next;
			if (prev != NULL) prev->next = next; else head = next;
			if (next != NULL) next->prev = prev;
			enqueue(it.data);
			return iterator(next);
		}
};

int main(void) {
	data_supplier<int> ds(10);
	for(;;) {
		int query = 0;
		puts("1: 追加、2: 削除、    3: インクリメント");
		puts("4: 閲覧、5: リセット、6: 終了");
		fputs(">", stdout);
		if(scanf("%d", &query) != 1) return 1;
		switch (query) {
			case 1: {
				fputs("数値>", stdout);
				if (scanf("%d", &query) != 1) return 1;
				int *next = ds.create_new_data();
				if (next == NULL) {
					puts("容量不足です");
				} else {
					*next = query;
					puts("セットしました");
				}
				break;
			}
			case 2: {
				fputs("数値>", stdout);
				if (scanf("%d", &query) != 1) return 1;
				for (data_supplier<int>::iterator it = ds.begin();
				it != ds.end();) {
					printf("%d : ", **it);
					if (**it == query) {
						puts("YES");
						it = ds.delete_data(it);
					} else {
						puts("NO");
						++it;
					}
				}
				break;
			}
			case 3: {
				for (data_supplier<int>::iterator it = ds.begin();
				it != ds.end(); ++it) (**it)++;
				puts("インクリメントしました");
				break;
			}
			case 4: {
				for (data_supplier<int>::iterator it = ds.begin();
				it != ds.end(); ++it) printf("%d\n", **it);
				break;
			}
			case 5:
				ds.clear();
				puts("リセットしました");
				break;
			case 6:
				return 0;
			default:
				puts("コマンドが不正です");
				break;
		}
	}
	return 0;
}

このサンプルでは、弾データの代わりにintのデータを生成/削除しています。
使いかた

コード:

・変数宣言
data_supplier<管理する型名> 変数名(最大要素数);
・新しいデータの生成
create_new_data() // 新しいデータのポインタが返る
・先頭イテレータの取得
begin()
・末尾イテレータの取得
end()
・データの削除
delete_data(削除するデータを指すイテレータ) // 次の要素を指すイテレータが返る
・データの全消し(初期化)
clear()

この実装だと、データを生成/削除した時にそのデータのコンストラクタやデストラクタは呼ばれないので、
管理するデータはコンストラクタやデストラクタでの処理が必要ないもの(C言語的な「構造体」など)にしてください。
clearすることで前のデータの影響を受けない、std::vectorなどでも大丈夫なはずです。
データの初期化は、コンストラクタではなく生成したデータのポインタが指す先にアクセスすることで行ってください。

オフトピック

ついでにサンプル化しました。
動的確保しないリスト

[メンマ]

＞softya（ソフト屋) さん
１．やはり処理としては変数変更よりもメモリ確保のほうがだいぶコストがかかるんですね。なるほど、アルゴリズムの組み方次第ではありなのかもしれませんね。瞬間コストと継続コストのどちらをとるかの天秤がけなどは現状では決めかねるので、最終的な形が明確になってから改めて考えてみます。
２．メモリについてはおまけ程度で考えていましたが、やはり現状のPCでの環境を考えると無視しても差し支えなさそうですね。処理速度のほうを重視しようと思います。

そのとおりですね（汗）。リアルの時間が限られるので、質問で解決すればと甘えてしまいました。勉強にもなるし自分で計測方法などを調べたり考えたりしてみます。


＞みけCATさん
確かに動的に確保はせず、かつランダムアクセスでないリストの長所を活かすのは処理時間で考えるといいかもしれませんね。
おお・・・ソースコードまで・・・ありがとうございます！このソースコードを使用、または参考にさせていただきます。


仕様変更については一長一短がありそうなので、計測したり最終的な形が明確になってから改めて決めてみます。お二方、回答ありがとうございました。