GDD2011 DevQuiz スライドパズル

以下のサイトを見ると、皆さんいろいろなアルゴリズムで探索しているようです。

「GDD2011 DevQuiz のスライドパズル晒し祭りをまとめてみた」
http://d.hatena.ne.jp/harapon1012/touch/20110912/1315805381

言語はjavaが多いようですが、中にはJavaScriptで4000問以上正解したという人もいたようです。

私もJava(Swing)で作成しました。幅優先探索とステップ実行を並列処理で行うようにしました。
枝刈りには、MD（移動距離）及びID（転倒距離）の厳しい方を採用。ここで壁を考慮した枝刈りをすればもっと効率の良い探索が出来たんだろうなぁと思います。


■ 探索アルゴリズムの纏め

１．深さ優先探索（DFS）
先頭のノードから、子のない最後のノードに行き着くまで、深く伸びていく探索、その後はバックトラックして、最も近くの探索の終わっていないノードまで戻る。

２．幅優先探索（BFS）
先頭のノードで始まり隣接した全てのノードを探索する。それからこれらの最も近い子ノードのそれぞれに対して同様のことを繰り返す。

３．反復深化（IDDFS）
深さ優先探索の深さ制限を徐々に増大させ、最終的に目標状態の深さになるまで反復するもの。

４．A*探索（IDA*）
過去のステップ数と残りの距離見積りの和で与えた閾値を上げながら反復深化（これが最も有効だったようだ）

５．双方向探索
同時に2つの方向から探索を行う。一方は初期状態から順方向に探索し、もう一方は最終状態から逆方向に探索して、その中間でぶつかった時点で終了する

６．端優先
人がパズルを組み立てる時のように端から順に揃えていくアルゴリズム。

７．ステップ実行
指定された回数探索を行い、それまでにゴールに達しなかった場合、過去に見つかった残りの距離見積りが最小のものをスタートに再度探索を繰り返す。（それ以外のノードを捨てる）
実装は簡単ですが、無駄なノードに対しても与えられた探索回数までは広く探索を行う点が難。


■ 作成したソース
https://github.com/isystk/gdd2011jp

■ デモ
http://www.ise-web.com/sample/jws/

■ 結果

■ 参考にしたサイト
http://www.ic-net.or.jp/home/takaken/nt/slide/solve15.html

Tomcat7のデーモン化手順

Tomcat7からjsvcを利用したデーモン化の方法がちょっと変わったみたいなので、メモしておく。

デーモンの設定方法

cd $CATALINA_HOME/bin
tar xvfz commons-deamon-native.tar.gz
cd commons-daemon-1.0.x-native-src/unix
./configure
make
cp jsvc ../../
cd ../../

Java SE 7最新動向

JSR 203: More New I/O APIs for the Java Platform ("NIO.2")
～　ファイルシステムへのアクセスや非同期I/Oなどといった、入出力関連の拡張機能が提供される。

JSR 255: Java Management Extensions (JMX) Specification, version 2.0
～　JMX Remote仕様(JSR 160)の後継バージョンで、Java SE 6の数々の新機能に対応したアップデートが行われる。

JSR 260: Javadoc Tag Technology Update
～　Javadocのタグを拡張するための仕様である。

JSR 262: Web Services Connector for Java Management Extensions (JMX) Agents
～　Webサービス経由でJMX Remote APIにアクセスするためのコネクタを定義し、
これによってJavaアプリケーション以外のクライアントからもJavaプログラムのマネージメントが行えるようになる。

JSR 268: Java Smart Card I/O API
～　JavaプログラムでスマートカードにアクセスするためのAPI仕様。

JSR 275: Units Specification
～　Javaプログラムにおいて数量や単位を扱うための強力な機能を提供する拡張API

JSR 277: Java Module System
～　JARファイルの拡張版といった位置付けのJSRで、Javaアプリケーションの配布やデプロイ、
ファイル間の依存関係の解決などを容易に行えるようにするもの。

JSR 292: Supporting Dynamically Typed Languages on the Java Platform
～　Java仮想マシンに動的な型をサポートするための仕様を織り込み、
Javaプラットフォーム上で動作する動的言語(JRuby、Jython、Beanshell)の開発を容易にすることを目指している。

JSR 294: Improved Modularity Support in the Java Programming Language
～　パッケージの概念を拡張するもので、パッケージレベルでのアクセス権を扱えるようにするための仕組みなどが規定される。

JSR 295: Beans Binding
～　JavaBeanのプロパティを同期させるためのAPI

JSR 296: Swing Application Framework
～　Swingを用いたGUIアプリケーション開発のための標準的なフレームワークを提供する。

JSR 303: Bean Validator
～　アノテーションを使用してJavaBeanの検証を行うための仕組みを提供するAPI

JSR 310: Date and Time API
～　Javaプログラムにおける日付や時間の情報を取り扱うためのAPI

JDK7 にバンドル予定の新機能 メモ

■ JDK7 にバンドル予定の新機能　メモ


【APIの改善点】
・switch 文での String
～　switch 文で String を使用できるようになる。
例：

switch (myString) {
    case "one":
        <do something>;
        break;
    case "red":
        <do something else>;
        break;
    Default:
        <do something generic>;
}

・Generics インスタンス生成のための型推論の改善
～　2 番目の <> 構成体を以下のように推定することができる。
例：

Map<String, List<String>> anagrams = new HashMap<();

・コレクションの言語サポート
～　配列を初期化する構文を使用して配列に含める値を指定することが出来る。
例：

List<String> numbers = ["one", "two", "three", "four", "five"];

・自動リソース管理
～　try 文の実行が完了すると、InputStream や OutputStream などのリソースが自動的に閉じられる。
例：

try (BufferedReader reader = new BufferedReader(new FileReader(file)) {
    return reader.readLine();
}

・マルチキャッチ
～　複数の例外を同じcatchブロックでキャッチできる。
例：

try {
    ・・・
} catch (IOException | InterruptedException e) {

・java.util.Objectsクラスの提供
～　リフレクションを使い、オブジェクトのすべてのフィールドを書き出すtoString(arg)など。


・ダイアモンド演算子
～　new LinkedList<>()


・enumの大小比較
・BigDecimalで直接演算子で計算が可能
・引数チェック用のアノテーション(@NotNullみたいなもの）



【VMの改善点】

・コンプレス64ビットオブジェクトポインタ
～　64ビットJavaでもポインタ(オブジェクトの位置を表現する変数)を短く表現することで消費メモリを減らす機能


・G1ガベージコレクタ
～　ヒープ領域は1つだけ用意され、その中を小さな領域に分割する。
そしてその領域のうちいくつかをYoung領域とし、残りをOld領域として利用する。(FullGCの発生頻度を減らす効果)
Java SE for Businessのサポート契約を購入する必要がある。


・クラスローダアーキテクチャアップグレード


■ その他（JDK8に持ち越し？）
・クロージャ
・Swingアプリケーションフレームワーク

partimageを使ったOSのバックアップ＆リストア手順

partimageを使ったOSのバックアップ＆リストア手順

■ 事前準備
ハードディスクを３台用意する。それぞれは以下の目的で利用する。
HD1　・・・　WindowsXP(通常利用するOS)、Ubuntu(バックアップやリストア作業を行う為のOS)
２つのOSをデュアルブート起動出来るようにしておく。
HD2　・・・　データ専用(作成したデータは、すべてここに保存する。マイドキュメントの位置もCドライブから移動しておく)
HD3　・・・　HD1のWindowsXPがインストールされているパーティションのクローン。
通常利用するOSが壊れたときのための緊急用OS
NAS　・・・　OSイメージをバックアップしておく場所。HD2のバックアップにも利用する。


■ バックアップ
# 管理者になる
su -

# バックアップイメージを保存するファイルサーバーをマウントする。
mkdir /mnt/private
smbmount //<NASのIPアドレス> /mnt/nas -o password=<パスワード>,username=<ユーザーID>,ip=<NASのIPアドレス>

# partimageを起動
partimage

・ 設定内容
１."Partition to save/restore"にバックアップ対象のパーティションを選択する。
例) /hdb/dev1

２."Image file to create/use"にイメージファイルの保存先を指定する。
例)"/mnt/nas/partimage/xp_20110417"

３."Action to be done"で"Save partition into a new image file"が選択されている事を確認する。

F5を押す。
イメージの圧縮方法がGZipになっていると時間がかかるのでNoneにする。

F5 → OK　→ OK

※ ハードディスクが断片化していると、うまくリストアできない場合がある、
バックアップをとる前に、"Defraggler"などのツールを利用して、
断片化されているファイルを０個にすることをお勧めする。


■ リストア
# 管理者になる
su -

# partimageを起動
partimage

・ 設定内容
１."Partition to save/restore"にリストア対象のパーティションを選択する。
例) /hda/dev1

２."Image file to create/use"にイメージファイルの保存先を指定する。
例)"/mnt/nas/partimage/xp_20110417.000"
※末尾に".000"が付いていることに注意

３."Action to be done"で"Restore partition from an image file"が選択されている事を確認する。

F5を押す。
F5 → OK　→ OK

Javaの例外処理を復習

■ Ａグループ
～　ThrowableのサブクラスErrorのサブクラス。
まれにしか起こらず対処することは不可能、あるいは対処すべきでないもの。

・java.lang.OutOfMemoryError　・・・　メモリ不足
・java.lang.StackOverflowError　・・・　スタックオーバーフロー

■ Ｂグループ
～　ThrowableのサブクラスExceptionのサブクラスでＣグループ以外のもの。
mainまでのどこかでtry～catchにより対処しなければならないもの。

・java.io.IOException　・・・　入出力エラー
・java.io.FileNotFoundException　・・・　ファイルが見つからない（IOExceptionのサブクラス）
・java.lang.ClassNotFoundException　・・・　クラスが見つからない

■ Ｃグループ
～　ThrowableのサブクラスExceptionのサブクラスRuntimeExceptionのサブクラス。
プログラムの実行中どこでも起こりうるもので、プログラム作成者のミスによるもの。

・java.lang.ArithmeticException　・・・　整数演算での０による除算
・java.lang.ArrayIndexOutOfBoundsException　・・・　配列の添字の不正
・java.lang.IllegalArgumentException　・・・　引数の値のエラー
・java.lang.NullPointerException　・・・　nullポインタへのアクセス

他のマシン上で起動しているTomcatをリモートからデバックする方法

他のマシン上で起動しているTomcatをリモートからデバックする方法

■ デバッグされる側の準備

・Tomcat 起動時に引数を指定する方法
$TOMCAT_HOME/bin/catalina.sh jpda start

・VM オプションを環境変数に設定する方法
（当方ではjsvcを利用してtomcatをデーモン化している為、
こちらを利用した。）

-Xdebug -Xrunjdwp:transport=dt_socket,server=y,suspend=n,address=5005


■ 接続確認
jdb -connect com.sun.jdi.SocketAttach:hostname=localhost,port=5005


■ ローカルのEclipseからリモートのTomcatをデバックする。

メニューバーから「実行(R)」→「デバッグ(B)」→「起動構成」
以下のように設定します。
・接続方法：ソケット
・ホスト名：接続するIPアドレス（または、ホスト名）
・ポート番号：5005 (-Xrunjdwpのaddressで指定したもの)