2011/06/01

Processing でイテレータ

昨日、超てきとうにあんな記事を書いたところ、Processing 日本語コミュニティサイト p5info.com の方の目に留まり、激しく恐縮していますこんにちはこんにちは。


おお、面白い RT @tercel_s: Processingで画面遷移効果(くだけちるエフェクト) http://bit.ly/mHXM0e2011年5月31日 22:53 via web

で。

p5info.com さんの他のツイートを見ていたところ、ちょうど 『Processing で学ぶデザインパターン』 とかオブジェクト指向的な話がでてきていて、『おぉっ』と思ってしまった。

個人的に、Processing はオブジェクト指向色の薄い言語だと思うけれど、それでも時と場合によってはデザインパターンを採り入れた方がプログラムしやすくなったり安全になったりするし、そういった経験則を通して設計面の楽しさを知る機会はあったほうがうれしい。

実際、たとえ意識しなくても Processing で void setup() とか void draw() を書いている時点で、Template Method パターンを利用している事になるわけで、やっぱりぼくらは知らず知らずのうちにデザインパターンの恩恵を受けている。



というわけで、今日の話題は GoF のパターンの一つである『イテレータ』について。

ただし、『イテレータを一から設計するにはどうすればよいか』という話はできないのでしない。代わりに、『それを使うと何が便利なのか』という動機づけの話をしよう。

ArrayList とか LinkedList とかを使用していて、『ある条件に一致する要素すべてをリストから削除したいなあ』というシチュエーションを考える。

たとえば、以下のようなリストから、「要素が3であるもの」をすべて除去したいとしよう(実際はもっと複雑な状況を想定している)。

intList
 3   1   2   3   3   3   7   0 

こんなとき、初心者(というか僕)が真っ先に思い浮かぶのがこんな方法だ。
  1. // リストを作って  
  2. ArrayList intList = new ArrayList();  
  3.   
  4. // 要素を設定  
  5. intList.add(new Integer(3));  
  6. intList.add(new Integer(1));  
  7. intList.add(new Integer(2));  
  8. intList.add(new Integer(3));  
  9. intList.add(new Integer(3));  
  10. intList.add(new Integer(3));  
  11. intList.add(new Integer(7));  
  12. intList.add(new Integer(0));  
  13.   
  14. // 最初の中身を表示  
  15. println("intList:");  
  16. for(int i = 0; i < intList.size(); i++) {  
  17.   print(intList.get(i) + " ");  
  18. }  
  19. println();  
  20.   
  21. // 3を削除?  
  22. for(int i = 0; i < intList.size(); i++) {  
  23.   Integer element = (Integer)intList.get(i);  
  24.   if(element.intValue() == 3) {  
  25.     intList.remove(element);  
  26.   }  
  27. }  
  28.   
  29. // 削除後の中身を表示  
  30. println("intList:");  
  31. for(int i = 0; i < intList.size(); i++) {  
  32.   print(intList.get(i) + " ");  
  33. }  
  34. println();  

しかし、実行してみると分かるが、明らかに「削除漏れ」が起きている。
【実行結果】
intList:
3 1 2 3 3 3 7 0
intList:
1 2 3 7 0
この現象は、削除すべき要素が連続しているところで発生している。



以下の処理の途中からトレースしていこう。タネを明かせばこうだ。
  1. for(int i = 0; i < intList.size(); i++) {  
  2.   Integer element = (Integer)intList.get(i);  
  3.   if(element.intValue() == 3) {  
  4.     intList.remove(element);  
  5.   }  
  6. }  

1) i == 2 のとき: 下図の黄色で示した要素が参照される。
intList
 1   2   3   3   3   7   0 

2) 参照している要素を get(i) で取得し、削除すべきかどうかを判定
intList
 1   2   3   3   3   7   0 

3) 削除
intList
 1   2       3   3   7   0 

4) 要素が削除されると、リストは自動的にリサイズされる
intList
 1   2   3   3   7   0 

5) i++ :そのまま次のステップへ…
intList
 1   2   3   3   7   0 


要素を削除した後、インデックス i が指しているリストの要素がズレてしまい、それが削除漏れを引き起こしていたのだ。



で、こんなときのために(?)、イテレータ(Iterator / 別名 Cursor)と呼ばれる仕掛け存在する。

イテレータについては、Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides 著、本位田 真一, 吉田 和樹 監訳『オブジェクト指向における再利用のためのデザインパターン 改訂版』に、以下の記述がある。
集約オブジェクトが基にある内部表現を公開せずに、その要素に順にアクセスする方法を提供する。
つまりイテレータは、『利用するコンテナ(Java でいうコレクション)の種類が変わっても、そこに格納されている各要素への順次アクセスは同じ方法がいい』という目的を達成するために作られた仕組みなのだが、それを多少拡大解釈すると、
ArrayList の内部がどうなっているかを知らなくとも安全・確実に全要素をトラバースできるんです。そう、イテレータならね。
という事になる。

何はともあれ、まずは先ほどのソースコードの14行目~19行目(インデックス i を用いてリストの要素を反復的に参照する処理)を、イテレータ方式に書き換えてみる。

Processing の公式リファレンスには存在しないが、ぼくが使っている Processing 1.0 はちゃんと Iterator をサポートしている。
  1. // 最初の中身を表示  
  2. println("intList:");  
  3. for(Iterator iterator = intList.iterator(); iterator.hasNext(); ) {  
  4.   print(iterator.next() + " ");  
  5. }  
  6. println();  

使い方は Java の Iterator と一緒なので、JDK のドキュメントを読めばOK。それによると、Java の Iterator インタフェースには、remove メソッドが用意されている。これは、
基になるコレクションから、反復子によって最後に返された要素を削除します (任意のオペレーション)。 (中略) 反復子の動作は、繰り返し処理がこのメソッドの呼び出し以外の方法で実行されているときに基になるコレクションが変更された場合は保証されません。
というものである。

つまり、Iterator を実装したクラスの remove を用いれば、反復処理の中で安全に要素を削除できるという意味だ。

これを踏まえて、先ほどの不完全な削除の処理を、イテレータを用いて書き換えたものを以下に示す。
  1. // 3を削除  
  2. for(Iterator it = intList.iterator(); it.hasNext(); ) {  
  3.   Integer element = (Integer)it.next();  
  4.   if(element.intValue() == 3) {  
  5.     it.remove();  
  6.   }  
  7. }  
これでうまくいった。

めでたし、めでたし。



ちなみに、ぼくがイテレータなるものを知る前は、前述の削除漏れ問題に対応するために以下のような処理を書いていた。
  1. // =====================  
  2. // 3を削除する処理  
  3. // =====================  
  4.   
  5. // まず、intListのうち、  
  6. // 削除する要素を格納しておく一次リスト(removeElements)を作る  
  7. // ※ 名前がおかしいのはご愛嬌  
  8. ArrayList removeElements = new ArrayList();  
  9. for(int i = 0; i < intList.size(); i++) {  
  10.   Integer element = (Integer)intList.get(i);  
  11.   if(element.intValue() == 3) {  
  12.     removeElements.add(element);  
  13.   }  
  14. }  
  15.   
  16. // 削除用の一次リスト removeElements に含まれる全ての要素を、  
  17. // intList から削除する  
  18. for(int i = 0; i < removeElements.size(); i++) {  
  19.   intList.remove(removeElements.get(i));  
  20. }  
これでももちろんうまく動くが、見るからに酷いコードである。

余分なデータ構造を用意する分、処理のオーバーヘッドも大きいし、そもそも可読性が低い。

あと余談だけど、もっと簡単な方法として、
  1. while(intList.remove((Integer)3));  
という書き方もある。

ただしこれは、『2以上、かつ7以下の要素を削除する』みたいに、条件が少しでも複雑になっただけですぐに通用しなくなるので、汎用性を考えるとイテレータを使うべきだと思う。まる。



というわけで、まとめ。

ぼくらは知らず知らずのうちにデザインパターンを使っている。

でも、知らないパターンもある。

知ると、ちょっと安全でしかも簡潔なプログラムを書けるようになる。

かも知れない。

0 件のコメント:

コメントを投稿

ひとことどうぞφ(・ω・,,)