コグノスケ

Javaのイテレータ

目次: Java

Javaを始めたときにコケたので思い出深いのですが、C++とJavaってイテレータの概念が全然違いますね。

C++のイテレータはコレクションの要素そのものを指しています。N個要素を持つ配列aのイテレータitであれば、a.begin() はa[0] を指し、itはa[0] からa[N - 1] の間まで有効な要素を指し続けます。a.end() は存在しないa[N] を指します。

begin()                                        end()
|                                              |
a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]   a[N]
|      コレクションの有効範囲       |

C++方式の利点は、イテレータが何を指すのか直感的に理解しやすく、イテレータ経由での要素の書き換えや削除のイメージが沸きやすいことです。

欠点はbegin() は参照して良いのに、end() は参照してはいけない、という非対称な仕様になってしまうことです。例えば、逆転イテレータ（reverse_iterator）を実装するとbegin() をend(), ++ を -- として扱うだけでは作れずに、悲しい思いをします。

Javaのイテレータは要素と要素の「間」を指しています。Javaにbegin(), end() はありませんが、対比のため無理やり書くと下記のようなイメージです。

 begin() = iterator()                           end() = hasNext() がfalse
 |                                              |
   a[0]   a[1]   a[2]   ... a[N - 2]   a[N - 1]
   |      コレクションの有効範囲       |

Java方式の利点はbeginとendが対称的になることです。もうbeginとendで悲しい思いをすることはありません。

欠点は書き換えや削除の対象がわかりづらいことです。特に双方向イテレータ（ListIterator）が顕著なので、もう少し詳しくご紹介しましょうか。

Javaコレクションの仕様ではイテレータが「最後に返した要素」が書き換え（set）や削除（remove）の対象、となります。ListIteratorは進む/戻るのどちらもできますから、イテレータの現在位置の「直前」あるいは「直後」どちらかの要素が対象となります。下記に図示します。

最後の操作がnext() だった場合
------------------------------
       set()/remove() の対象
       |    現在位置
       |    |
a[0]   a[1]   a[2]   ...


最後の操作がprevious() だった場合
----------------------------------
            現在位置
            | set()/remove() の対象
            | |
a[0]   a[1]   a[2]   ...

現在位置が全く同じでもset()/remove() の対象が変わる、この動きは正直ややこしいです。

利点の両立は難しいでしょうから、あとは皆さんの好みでしょうか。私は対称性を取ってJava方式に一票かなあ…。

神の一手

コンピュータ将棋の電王戦が非常に話題になっていました。盛り上がりについて行けていませんが、結果だけ聞くとプロと勝負できるまでになったとか、こりゃすごい。

チェッカーは神の一手（全手読み切った上での、最善の一手）がわかるそうですが、チェス、将棋、囲碁は探索範囲が広すぎるのでほぼ不可能でしょう…。神の一手は興味深いですが、わからないからと言ってコンピュータ将棋が弱くなるわけでもなく、今後、コンピュータ将棋はもっと盛り上がることでしょう。

将棋の探索範囲の広さは1局面にざっと80通り（※）指せて、終局まで110〜120手くらい指すので、探索空間は80^120程度です。10のべき乗がお好きなら、
10^x = 80^120の自然対数取って、
x * ln10 = 120 * ln80
x = 120 * ln80 / ln10 = 228.5
となって10の228乗くらい、と見積もれます。調べてみると一般的には10^220と言われているようです。ややズレたのは、なんでだろ…。

（※）歩が9枚（1通り * 9）飛（16通り）角（最も動けて16、動けなくて8なので、間を取って12通り）王（8通り）金（6通り * 2）銀（5通り * 2）桂（2通り * 2）香（最も動けて9、動けなくて0なので、間取って4.5通り * 2）として、1局面80通り、駒を取られても再び置けるため、指せる手の平均値はほぼ変わらない、とした。

囲碁はどうか？

コンピュータ囲碁はどうだろう？と調べてみると、2006年にモンテカルロ法（1手ずつデタラメに置いて、勝ちの確率が高い手を探す）を採用した強いソフトが出て、今やアマ有段者並の強さとのこと。こちらもすごいですね…。

モンテカルロ法はリバーシや囲碁などの性質を非常に上手く使っています。リバーシや囲碁は1手指せば1つ空きマスが減るため、メチャクチャに打っても必ず終局にたどり着ける、という性質があります。これを上手く利用して、メチャクチャに打った手の中で勝率が高い手はどれか？を探すそうです。

囲碁では有効なモンテカルロ法ですが、将棋への適応は難しいようです。なぜなら将棋はデタラメに指しても終局に近づかない（ループして盤面が戻ってしまう）ためです。

並べられることの多い、将棋と囲碁ですが、探索方法一つとっても違いがハッキリ出ていて面白いですなー。

何も解決しない結論

なぜなぜ分析は、危険だ - タイム・コンサルタントの日誌からを読んで。

会社のなぜなぜ分析も、この記事の「悪い方の例」とそっくりです。

大の大人が何時間も掛けて分析した結論が「以降、ミスしないように気をつけます」ですからね。

まさか小学生じゃあるまいし、そんなのありえないよ！って思うかも知れませんが、悲しいことに現実なんですわ…。

メモ: 技術系の話はFacebookから転記しておくことにした。

好き嫌い？優劣？

プログラミング言語の優秀さと道具としての評価は別 - kなんとかの日記を読んで。

本文に異論は無いんですが、タイトルの「プログラミング言語の優秀さ」って何だろう？と思った。

言語屋さんから見て、明確に優劣が決まる基準があるのかなあ？変な言語に手を出す前に、その基準で見てみたい…。

メモ: 技術系の話はFacebookから転記しておくことにした。

The Tower DSクラシック

久しぶりにThe Towerをやりたくなったのですが、PC版は動かせる環境がもうなくて（※）起動すらできなかったので、DSi WareのThe Tower DSクラシック（1000ポイント）を買いました。

（※）WinGというDirect Drawの前身に当たるグラフィクスライブラリが必要ですが、対応環境がWindows 3.1〜95（98も使えたっけ？）ときたもんだ。そんな環境もう持って無いんよ…。

The Towerを一言で言うとビルのシミュレーションで、特にビル内での人の移動（＝エレベータ＆エスカレータ＆階段）に特化したシミュレーションです。

基本的なThe Towerの進め方は下記の通りです。要はテナントを作って、テナントの評価を良い状態に保ち、テナントからお金を得て、さらにビルをデカくすることが目的です。

• ビルを維持、拡張するにはお金が必要
• お金はビル内のテナントからもらえる
• テナントには客が必要
• 客は移動手段、エレベータとかがあれば勝手に来る
• 客は最初は少ないが、評価が良ければ客は自然に増える
• 客が増えればテナントから収益が出る、逆に客が少ないと損失が出る

肝心のテナントの評価はどう決まるかというと「移動手段の快適さ」でほぼ決まります。

ビルに来る客はエレベータで乗る時に待たされたり、階段を何階も登り降りさせられる、とイライラします。このイライラ度合いが大きい＝ビル内のテナントの評価が下がる、という仕組みになっています。

すなわち、大量に作ったテナントにやってくる、超大量の客をいかに待たせずにスムーズに移動させるか？がこのゲームのほぼ全て、と言っても過言ではないはずです。

とだけ書くと、いかにも簡単そうに見えますが…、

• 移動手段をケチるとキャパオーバーして評価が落ちて赤字
• 場当たり的な対応を続けると収益＜維持費になって評価は良いのに赤字

以上のようなハマりどころも多く、腹立つところも多いですが、バッチリ決まったときの爽快感は中々のものです。

有名どころのシムシリーズ（特にSimCity 4ラッシュアワー）も交通手段が多彩になって、移動のシミュレーションがかなり重視されてきていますから、世界中どこでも人の流れってゲームになる、面白いと感じられているんでしょうね。

クリアした感想

クラシックと付くだけあって、ゲーム内容はPC版ほぼそのままです。懐かしい＆面白いです。シナリオが1面しかない、ビルが小規模、辺りの制限は、所詮1000円分ってことなのかな。

不満があるとすると、早送りでも時間の経過が遅いことです。特に40階建てを超えた辺りから遅くてイライラします。DSiの処理能力上、仕方ないのかもしれませんけど…。

操作性は悪くないです。画面デザインはDSiのゲームっぽくないですが、悪くはないです。PCから移植しました！って雰囲気が漂います。