Listオブジェクトのremoveメソッド(要素の削除)について

List 系オブジェクトの remove メソッド(要素の削除)について

ゲームプログラミングでは、List オブジェクトに対して、
要素の追加/削除(add/remove)を頻繁に行う場合があります。

例えば、敵などのキャラクターの保管場所に利用したりする場合です。

他にも、AWT/Swing を利用する際は、Container オブジェクトに対して Component を add していきますが、
その先には、ArrayList が存在しているような格好となっています。
JavaFX に関しても、Parent 系オブジェクト( Group オブジェクト等)に Node を add していきますが、
きっちりと(ソースを)追えていませんが、まず間違いなく ArrayList のようです。
(興味があったら、ソースを追ってみてくださいね)

このような感じで、List オブジェクトが使われていますが、
remove メソッドについては、若干、考慮した方が良さそうです。

それは、「System.arraycopy」が使われていることです。
この「System.arraycopy」は、非常に早い処理で行われますが、
しかしながら、多用すると、やはり負荷がかかってきます。
負荷をかけないためには、「remove」メソッドの呼び出しをできるだけ少なくする方が良いです。

そこで、わたしが考えたのは、リストの置き換え。
remove の代わりに null に置き換えて、あるタイミングで null以外のリストを一時的に作成して置き換える方法です。
その方法で検証をしてみました。

検証内容。

プログラム。

import java.util.ArrayList;

public class ListRemove {

	private final String DATA = "1234567891123456789212345678931234567894123456789512345678961234567897123456789812345678991234567890";

	public static void main(String[] args){
		ListRemove obj = new ListRemove();
	}

	public ListRemove() {

		// リストを生成
		ArrayList<String> list = new ArrayList<String>();

		// 各要素に文字列を設定
		for(int i = 0; i < 10000; i++){
			list.add(new String(DATA));
		}

		// 5回テスト
		for(int t = 0; t < 5; t++){

			System.out.println((t + 1) + " 回目テスト");

			//
			// Removeテスト
			//

			// START
			long time0 = System.currentTimeMillis();
			System.out.println("LIST REMOVE START TIME : " + time0);

			// 100万回ループ
			for(int i = 0; i < 1000 * 1000; i++){

				// 0番目の要素を削除
				list.remove(0);
				// 各要素に文字列を設定
				list.add(new String(DATA));

			} // end for 100万回ループ

			// END
			long time1 = System.currentTimeMillis();
			System.out.println("LIST REMOVE END TIME   : " + time1);
			System.out.println("LIST REMOVE PROC TIME  : " + (time1 - time0));

			//
			// nullテスト
			//

			// START
			time0 = System.currentTimeMillis();
			System.out.println("LIST SET NULL START TIME : " + time0);

			// nullにするインデックス
			int indexNull = 0;

			// 100万回ループ
			for(int i = 0; i < 1000 * 1000; i++){

				// i番目の要素をnull化
				list.set(indexNull, null);
				// 各要素に文字列を設定
				list.add(new String(DATA));

				// インデックス+1
				indexNull++;

				// 999回の場合、
				if(i % 1000 == 999){

					// インデックスを初期化
					indexNull = 0;

					// リストを置き換え
					ArrayList<String> listWk = new ArrayList<String>();
					int size = list.size();
					for(int j = 0; j < size; j++){
						String strWk = list.get(j);
						if(strWk != null){
							listWk.add(strWk);
						}
					}
					list.clear();
					list.addAll(listWk);

				} // end if 1000回の場合

			} // end for 100万回ループ

			// END
			time1 = System.currentTimeMillis();
			System.out.println("LIST SET NULL END TIME   : " + time1);
			System.out.println("LIST SET NULL PROC TIME  : " + (time1 - time0));

			System.out.println("LIST SIZE : " + list.size());

		} // end for 5回テスト

	} // end ListRemove

}

測定した結果はこれです。
要素数1万で検証したログ詳細
要素数1千でも検証したログ詳細
(上記の表は、要素数1万で検証した表です)

約8.5倍の開きがありました。

100万回ループした結果をふまえると、大きい差なのかは、?なところもありますが、
System.arraycopyが早いと言われてるとはいえ、100万回System.arraycopyを呼び出すようなプログラムは、CPUにはやさしくない、エコではない。といえるでしょう。

少なくても、考慮すべき点になるのではないかと思っています。

「Javaでゲームを作ろう」の中では、この点を考慮し、リスト置き換え方式としています。
と、いうのも、体感したような気がしたんです。
たしか・・・ですが。カクカク感が改善したような気がします。
(いろいろと改善した中のひとつという位置づけではありますが)

あまり参考にはならないと思いますが、スペックはこれです。

(補足)

・Listはインターフェースですが、Listを利用したArrayListなどのクラスを想定して、オブジェクトとここでは呼びました。

・この方法は、「Javaでゲームを作ろう!」の中で利用していたのですが、
体感的な話ばかりをしてきて、検証をしてきませんでしたが、
やっと、やる気が出て(!)、検証してみた次第です。

シェアしていただけるとうれしいです。

コメントを残す

メールアドレスが公開されることはありません。

CAPTCHA