デザインパターンを覚えたい (Observer)

デザインパターン
Observerパターン

状態変化を他のオブジェクトに通知するパターン。
ポイントは

  • 通知によって複数オブジェクト間で同期を取れる

ことかな。前回のMediatorパターンと似てるけど、こっちは通知することが主目的。

実装。いい例が思い浮かばなかったので今回は非常に単純なのですいません。
http://dl.dropbox.com/u/7810000/code/design_pattern/observer.zip

実行。

$ ant test
Buildfile: /Users/xxx/tmp/observer/build.xml

build:

test:
[java] exception : java.lang.ArithmeticException: / by zero
[java] 1: ...
[java] 2: ...
[java] 3: ...
[java] exception : java.lang.ArrayIndexOutOfBoundsException: 5
[java] 1: ...
[java] 2: ...
[java] 3: ...
[java] exception : java.lang.NullPointerException
[java] 1: ガッ
[java] 2: ガッ
[java] 3: ガッ

BUILD SUCCESSFUL
Total time: 2 seconds

ポイントは以下のようにSubjectにObserverを登録して、Subject内でObserverのメソッドを叩いているところ。

public class Main {
    public static void main(String[] args) {
        Subject subject = new ExceptionSubject();

        subject.addObserver(new ExceptionObserver());
        subject.addObserver(new ExceptionObserver());
        subject.addObserver(new ExceptionObserver());

        subject.execute();
    }
}

public class ExceptionSubject extends Subject {
    public ExceptionSubject() {
        super();
    }

    public void execute() {
        try {
            int a = 0;
            int b = 2;
            int c = b / a;
        } catch (Exception e) {
            System.out.println("exception : " + e);
            notifyObservers(e);
        }

        try {
            Thread.sleep(1000);
        } catch (Exception e) {
            System.out.println("exception : " + e);
            notifyObservers(e);
        }

        try {
            int[] array = new int[5];
            for (int i=0; i<=5; i++) {
                array[i] = i;
            }
        } catch (Exception e) {
            System.out.println("exception : " + e);
            notifyObservers(e);
        }

        try {
            Thread.sleep(1000);
        } catch (Exception e) {
            System.out.println("exception : " + e);
            notifyObservers(e);
        }

        try {
            String nullStr = null;
            int nullLength = nullStr.length();
        } catch (Exception e) {
            System.out.println("exception : " + e);
            notifyObservers(e);
        }
    }
}

ちなみにObserver側の実装はこんな感じ。

public class ExceptionObserver implements Observer {

    /* 中略 */

    public void update(Object event) {
        if (event instanceof NullPointerException) {
            System.out.println(Integer.toString(observeId) + ": ガッ");
        } else {
            System.out.println(Integer.toString(observeId) + ": ...");
        }
    }
}

デザインパターンを覚えたい (Mediator)

デザインパターン
Mediatorパターン

相談役は一人、なパターン。クラス間のやり取りをMediatorとなるクラスを介して行うことで、処理のパスを一箇所に集約する。
ポイントは

  • クラス間の通信パスをスター型でまとめることでプログラムの見通しが良くなる
  • Mediatorに相談するColleagueクラス群が再利用しやすい、一方でMediator役は再利用しにくい

とかかな。処理を集約する点がFacadeパターンと似てるけど、Facadeはメソッドをまとめて一方的に使うのに対して、Mediatorパターンは双方向でやり取りする点が異なるとか。

実装。Javaのマルチスレッドで遊んでみる。内容は1人のManager (Davit) と3人のWorker (Alice, Bob, Charlie) のタスク処理。
Workerはスレッドとして動作 (地味にスレッド処理ではまって時間かかった、よくないね)
http://dl.dropbox.com/u/7810000/code/design_pattern/mediator.zip

実行結果は以下のとおり。
# 結構時間がかかるので注意

$ ant test
Buildfile: /Users/xxx/tmp/mediator/build.xml

build:

test:
[java] Davit: assign task "create core module" to Alice
[java] Davit: assign task "create user interface" to Bob
[java] Davit: assign task "make API document" to Charlie
[java] Alice: do task "create core module"
[java] Bob: do task "create user interface"
[java] Charlie: do task "make API document"
[java] Charlie: done after 3 hours, report to manager
[java] Davit: assign task "buy lunch for all members" to Charlie
[java] Charlie: do task "buy lunch for all members"
[java] Bob: done after 4 hours, report to manager
[java] Davit: assign task "test modules" to Bob
[java] Bob: do task "test modules"
[java] Charlie: done after 1 hours, report to manager
[java] Davit: assign task "make powerpoint for sales" to Charlie
[java] Charlie: do task "make powerpoint for sales"
[java] Alice: done after 5 hours, report to manager
[java] Davit: assign task "cleanup the desk" to Alice
[java] Alice: do task "cleanup the desk"
[java] Alice: done after 1 hours, report to manager
[java] Alice: go home
[java] Charlie: done after 2 hours, report to manager
[java] Charlie: go home
[java] Bob: done after 6 hours, report to manager
[java] Bob: go home
[java] Davit: all task done

BUILD SUCCESSFUL
Total time: 10 seconds

ポイントはWorkerがManagerのメソッドを、ManagerがWorkerのメソッドを相互に呼び合っていることと、やり取りはManagerとWorker間のみでWorker同士では行われないこと。

public class Manager implements Mediator {

    /* 中略 */

    public synchronized void reportTask(Task task) {
        Worker worker = assignMap.get(task.getName());
        assignMap.remove(task.getName());

        if (taskList.size() > 0) {
            Task newTask = taskList.removeFirst();
            System.out.println(name + ": assign task \"" + newTask.getName() + "\" to " + worker.getWorkerName());
            assignMap.put(newTask.getName(), worker);
            // Workerへタスクを割り当てる
            worker.assignTask(newTask);
        } else {
            worker.setEnd();
            if (assignMap.size() < 0) {
                isEnd = true;
            }
        }
    }
}

public class Worker extends Thread implements Colleague {

    /* 中略 */

    public void run() {
        while (!isEnd) {
            if (hasTask) {
                System.out.println(name + ": do task \"" + task.getName() + "\"");

                try {
                    Thread.sleep(task.getManHour() * 1000);
                } catch (Exception e) {
                    System.out.println("ERROR: Woker sleep: exception occured : " + e);
                }

                hasTask = false;

                System.out.println(name + ": done after " + String.valueOf(task.getManHour()) + " hours, report to manager");
                // Managerへタスクを報告する
                mediator.reportTask(task);
            } else {
                System.out.println(name + ": no task, take a break");

                try {
                    Thread.sleep(500);
                } catch (Exception e) {
                    System.out.println("ERROR: Woker sleep: exception occured : " + e);
                }
            }
        }

        System.out.println(name + ": go home");
    }
}

自分のコードがとっても汚いのが残念な感じですね。

デザインパターンを覚えたい (Facade)

デザインパターン
facadeパターン

複雑な処理の窓口となるクラスを用意し、複雑なAPIの操作を隠蔽するパターン。ポイントは、

  • 相互に関係しあるAPIの処理フローをひとつのメソッドにまとめることにより、使う側から見てわかりやすいAPIにする

といったところ？これだけだとあまりにも普通なので他にもっとメリットあるのかも。

実装。前回同様Java強化中なのでJavaで。巡回セールスマンを解く窓口を作ってみる。
http://dl.dropbox.com/u/7810000/code/design_pattern/facade.zip

実行。

$ ant test
Buildfile: /Users/xxx/tmp/facade/build.xml

build:
[javac] Compiling 1 source file to /Users/xxx/tmp/facade/classes

test:
[java] SalesmanFacade: load mapFile[resources/map.dat]
[java] SalesmanFacade: create mapImage[images/orgMap.jpeg]
[java] SalesmanFacade: resolve the problem
[java] before distance = 16543.048701547556
[java] after distance = 2674.8979194573894
[java] SalesmanFacade: create mapImage[images/resolvedMap.jpeg]

BUILD SUCCESSFUL
Total time: 1 second

今回のは2-Opt近傍を用いた局所探索で巡回セールスマン問題を解いて、結果を画像で出力している。
ちなみに元データでの巡回路がこれ。

最適化後の巡回路がこれ。

結果は一目瞭然ですね。ちなみに、やってる探索は非常に単純なものなので、本当はもっと短い経路があると思われる。

中でやってる処理は大きく分けると、

  1. マップデータ読み込み
  2. 探索前のデータを画像出力
  3. 探索
  4. 探索後のデータを画像出力

という4つの処理を行なっているけど、これをSalesmanFacadeの中で一つのメソッドにまとめている。

public class SalesmanFacade {
    public static final String ORG_MAP_IMAGE = "images/orgMap.jpeg";
    public static final String RESOLVED_MAP_IMAGE = "images/resolvedMap.jpeg";

    public static void resolveTravelingSalesman(String mapFile) {
        try {
            System.out.println("SalesmanFacade: load mapFile[" + mapFile + "]");
            List<Town> townList = MapLoader.loadMap(mapFile);

            System.out.println("SalesmanFacade: create mapImage[" + ORG_MAP_IMAGE + "]");
            MapImage.saveMapImage(townList, ORG_MAP_IMAGE);

            System.out.println("SalesmanFacade: resolve the problem");
            TwoOptSolver solver = new TwoOptSolver(townList);
            double orgDist = solver.calcTotalDistance();
            System.out.println("  before distance = " + Double.toString(orgDist));
            solver.resolve();
            double resolvedDist = solver.calcTotalDistance();
            System.out.println("  after distance = " + Double.toString(resolvedDist));

            System.out.println("SalesmanFacade: create mapImage[" + RESOLVED_MAP_IMAGE + "]");
            MapImage.saveMapImage(solver.getTownList(), RESOLVED_MAP_IMAGE);
        } catch (Exception e) {
            System.out.println("ERROR: failed to resolve the problem: Exception = " + e);
        }
    }
}

SalesmanFacadeで必要な処理を全部まとめているため、Mainではこの処理を呼ぶだけでいい。なので、Mainがとってもシンプルになっている。

public class Main {
    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("ERROR: please specify mapFile");
            return;
        }

        // Facadeのメソッドを呼ぶ
        SalesmanFacade.resolveTravelingSalesman(args[0]);
    }
}

デザインパターンを覚えたい (Visitor)

デザインパターン
Visitorパターン

データ構造上を探索しながら処理をしていくパターン。データとなるElementクラスとそれに処理を行うVisitorクラスを用意し、相互にメソッドを呼び合うことでデータの網羅的な処理を行う。
ポイントは

  • データ構造とそれに対する処理を分離することができる

ところ。後で処理を追加する場合が容易になる一方で、新しいデータを追加したり修正するのは苦手。相互に呼び合うといってるけど、実際の処理はVisitor側でまとめて行う (シーケンス図みるとわかる)。

実装。今日はJavaで。題材はVisitorということでダイクストラ法にする。
http://dl.dropbox.com/u/7810000/code/design_pattern/visitor.zip

実行結果は以下の通り。
なお、テストで用いた経路図は以下のサイトのものを利用してます。
http://www.deqnotes.net/acmicpc/dijkstra/

$ ant test
Buildfile: /Users/xxx/tmp/visitor/build.xml

build:

test:
[java] nodeId=0 : cost=0
[java] nodeId=1 : cost=5
[java] nodeId=2 : cost=4
[java] nodeId=3 : cost=2
[java] nodeId=4 : cost=6
[java] nodeId=5 : cost=10

BUILD SUCCESSFUL
Total time: 0 seconds

# 多分数値はあってるはず

実装のポイントはNodeクラスとDijkstraVisitorクラスの以下の部分で相互に呼び合ってるところ

public class Node implements Element {

    /* 中略 */

    // Visitorから呼ばれる部分
    public void accept(Visitor v) {
        v.visit(this);
    }
}

public class DijkstraVisitor extends Visitor {

    /* 中略 */

    protected void visit(Node node) {
        if (!costMap.containsKey(node.getNodeId())) {
            throw new NodeNotFoundException();
        }

        // 現在のノードのコストを取得
        int baseCost = costMap.get(node.getNodeId());

        // 隣接ノードについてコスト更新
        Iterator<Edge> edgeIter = node.getEdgeIterator();
        while (edgeIter.hasNext()) {
            Edge edge = edgeIter.next();
            Node distNode = edge.getDistNode();

            // コスト更新
            if (!costMap.containsKey(distNode.getNodeId())) {
                costMap.put(distNode.getNodeId(), baseCost + edge.getCost());
                nodeQueue.offer(distNode);
            } else {
                int curCost = costMap.get(distNode.getNodeId());
                if (curCost > baseCost + edge.getCost()) {
                    costMap.put(distNode.getNodeId(), baseCost + edge.getCost());
                    nodeQueue.offer(distNode);
                }
            }
        }

        Node nextNode;
        while ((nextNode = nodeQueue.pollFirst()) != null) {
            // かなり無理やりだけどデータの方のacceptを呼ぶ
            nextNode.accept(this);
        } 
    }
}

コメントにも書いてあるけどかなり無理やり。多分Visitorパターンって深さ優先探索に向いてる形な気がするけど、ダイクストラ法だとどちらかというと幅優先探索なのでコードがきれいにまとめられなかったのかな。
# Visitorパターンの使い方が間違ってたりして、うーむ

デザインパターンを覚えたい (Chain of Responsibility)

デザインパターン
Chain of Responsibilityパターン

処理をチェインさせて順次実行していき、目的の処理を決めるパターン。ポイントは、

  • 処理と要求を結びつきを弱めることができる
  • 状況に応じた処理の切り替えがしやすくなる

といったところですかね。

実装します。Javaの勉強したいので今回もJavaです。Loggerもどき作ります。
http://dl.dropbox.com/u/7810000/code/design_pattern/chain_of_responsibility.zip

実行結果

$ ant test
Buildfile: /Users/xxx/project/design_pattern/chain_of_responsibility/build.xml

build:
[javac] Compiling 1 source file to /Users/xxx/project/design_pattern/chain_of_responsibility/classes

test:
[java] LogLevelFilterHandler: ACCEPT logLevel[FATAL] message
[java] LogDumpHandler: DUMP logLevel[FATAL] msg[this is FATAL message]
[java] LogLevelFilterHandler: ACCEPT logLevel[ERROR] message
[java] LogDumpHandler: DUMP logLevel[ERROR] msg[this is ERROR message]
[java] LogLevelFilterHandler: ACCEPT logLevel[WARN] message
[java] LogDumpHandler: DUMP logLevel[WARN] msg[this is WARN message]
[java] LogLevelFilterHandler: DENY logLevel[INFO] message
[java] LogLevelFilterHandler: DENY logLevel[DEBUG] message
[echo] --- output dumped message ---
[exec] FATAL : this is FATAL message
[exec] ERROR : this is ERROR message
[exec] WARN : this is WARN message

BUILD SUCCESSFUL
Total time: 1 second

実装ではChain of Responsibilityパターンをロギング処理にて

  1. 対象ログレベルのチェック
  2. 実際のログのダンプ

と2つの処理をチェインさせる部分で使ってます。
# もしかして本来のパターンの使い方と違うかも

コードのポイントはハンドラ内の連続実行の部分かな。

public abstract class LogHandler {
    private LogHandler next;

    public LogHandler setNext(LogHandler next) {
        this.next = next;
        return next;
    }

    public final void logDump(int level, String msg) {
        if (!execute(level, msg) && next != null) {
            next.logDump(level, msg);
        }
    }

    protected abstract boolean execute(int level, String msg);
}

上のlogDumpメソッドの中でメンバ変数として持っている次のハンドラのメソッドをある意味再帰的に呼び出している。
ちなみにチェインさせている部分はLoggerクラスの中にあります。

public class Logger {
    private static Logger instance = null;
    private LogLevelFilterHandler logLevelFilterHandler;
    private LogDumpHandler logDumpHandler;

    private Logger(String propFile) throws Exception {
        Properties prop = new Properties();
        prop.load(new FileInputStream(propFile));

        int logLevel = LoggerUtils.getLogLevel(prop.getProperty("logLevel"));
        String logFile = prop.getProperty("logFile");

        logLevelFilterHandler = new LogLevelFilterHandler(logLevel);
        logDumpHandler = new LogDumpHandler(logFile);

        // Handlerをチェイン
        logLevelFilterHandler.setNext(logDumpHandler);
    }

    public static Logger getInstance() throws NullPointerException {
        if (instance == null) {
            System.out.println("ERROR: Logger is not setup");
            throw new NullPointerException();
        }
        return instance;
    }

    public static void setup(String propFile) throws Exception {
        instance = new Logger(propFile);
    }

    public void fatal(String msg) {
        logLevelFilterHandler.logDump(LogLevel.LOG_FATAL, msg);
    }

    /* --- 以下省略 --- */
}

初段のハンドラのメソッドをキックすることでチェインされたハンドラが必要に応じて実行される。

デザインパターンを覚えたい (Decorator)

デザインパターン
Decoratorパターン

クラスをかぶせていって機能追加を行うパターン。共通の親元を持つ中身と飾りのクラスを用意し、共通メソッドを再帰的に呼び出していくことで機能拡張をする。
Decoratorパターンの特徴は、

  1. 共通の親クラスを持つサブクラスで包んでいくため、外部プログラムからは共通のメソッドが見える
  2. 大元の中身となる部分を変更することなく、機能拡張を行うことができる

といったところかな。java.ioとかがDecoratorパターンとしては有名。

実装。今日はc++で行こうかね。
http://dl.dropbox.com/u/7810000/code/design_pattern/decorator.zip

実行結果。

$ ./decorator_test
ご飯　どーん
トンカツ　どーん
まぐろ　どーん
いくら　どーん
天ぷら　どーん
天いくら鉄火カツ丼(1000 kcal) 一丁、へいおまち！

コードのポイントは呼び出し部分でコンストラクタをどんどん被せていってるところ。

int main() {
    Component* don = 
        new Tempura(
            new Ikura(
                new Tuna(
                    new Tonkatsu(
                        new Rice()
                        )
                    )
                )
            );

    std::cout << don->getName() << "(" << don->getCalorie() << " kcal) 一丁、へいおまち！" << std::endl;

    return 0;
}

coutのgetNameとgetCalorieでは内部で包んだインスタンスが再帰的に呼ばれている。

これで12パターン目で、23パターンもちょうど半分ですかね。先は長いねぇ。
一度やったパターンでもやっぱり理解がまだまだ浅いから、どこかでまとめて整理するタイミングが必要かも。

デザインパターンを覚えたい (Composite)

デザインパターン
Compositeパターン

共通メソッドによる再帰処理を行うパターン。
例えばファイルシステムの検索とかを実装する際に、FileクラスとDirectoryクラスを同一の親クラスを継承して作成することによって、クラスを同一視して扱うみたいな感じ。
Compositeパターンの特徴は。。。なんだろ、再帰が綺麗に作れること？

実装。ちょっとJavaの勉強したいので、前回に引き続きJavaでやります。
例としてゲームAIでよく出てくるミニマックス探索をやる。
http://dl.dropbox.com/u/7810000/code/design_pattern/composite.zip

実行結果は以下のとおり。

$ java -classpath classes Main
[RT] : 1
[RT] -> [c4] : 1
[RT] -> [c4] -> [c5] : 1
[RT] -> [c4] -> [e3] : 3
[RT] -> [e6] : -2
[RT] -> [e6] -> [f5] : -2
[RT] -> [e6] -> [f4] : 1

オセロの手の表記方法を意識してます。スコアはテキトー。
実装ではBranchとLeafとゲーム木の要素を2つに分けたけど、普通はNode一個で扱うんだろうね、たぶん。

ポイントはBranchの再帰処理のところ？実装がとっても汚い。

    protected void printTree(Deque<String> selectList, Side curSide) {
        // XXX: 本当は表示とスコア計算を同時にやるべき
        int senteScore = (curSide == Side.SENTE ? getScore(curSide) : -getScore(curSide));
        StringBuffer prefix = new StringBuffer();
        for (String select : selectList) {
            prefix.append("[" + select + "] -> ");
        }
        System.out.println(prefix.toString() + "[" + getSelect() + "] : " + senteScore);

        // 再帰的にサブツリーを表示
        Side nextSide = (curSide == Side.SENTE ? Side.GOTE : Side.SENTE);
        selectList.add(select);
        for (Node node : childNodes) {
            node.printTree(selectList, nextSide);
        }
        selectList.removeLast();
    }

子ノードを呼ぶところで親元であるNodeクラスのprintTreeを呼んでいて、これは実体がLeafクラスだろうがBranchクラスだろうが呼びだす側としては同じに見ている。

そういえば、今回Dequeのadd/removeLastを使って実装してるけど、初めstackっぽくpush/popでやったら順序が変になったんだよね。なんでだろ、そういう仕様なのかな。