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でゲームを作ろう!」の中で利用していたのですが、
体感的な話ばかりをしてきて、検証をしてきませんでしたが、
やっと、やる気が出て(!)、検証してみた次第です。