devneko is not cat.

勉強のため、いまさらながらダイクストラ法をJavaで書いてみた。

/**　ノード間をつなぐ節 */
public class Edge {
	/** 距離 */
	private int distance;
	/** 接続するノード */
	private Node node;

	public Edge(Node node, int distance) {
		this.node = node;
		this.distance = distance;
	}

	public int getDistance() {
		return distance;
	}

	public Node getNode() {
		return node;
	}

}

/** ノード */
public class Node {
	private int id;
	/** 始点からの距離 */
	private int distance = Integer.MAX_VALUE;
	/** 最短距離となるルートの一つ前のノード */
	private Node shortDistanceNode;

	public Node(int id) {
		this.id = id;
	}

	private boolean done;
	private List edges = new ArrayList();

	public int getId() {
		return id;
	}
	public int getDistance() {
		return distance;
	}
	public void setDistance(int distance) {
		this.distance = distance;
	}
	public boolean isDone() {
		return done;
	}
	public void setDone(boolean done) {
		this.done = done;
	}
	public List getEdges() {
		return edges;
	}
	public void addEdge(Edge edge) {
		edges.add(edge);
	}
	public Node getShortDistanceNode() {
		return shortDistanceNode;
	}
	public void setShortDistanceNode(Node shortDistanceNode) {
		this.shortDistanceNode = shortDistanceNode;
	}
}

public class NodeComparator implements Comparator {
	@Override
	public int compare(Node arg0, Node arg1) {
		return arg0.getDistance() - arg1.getDistance();
	}
}

public class Main {

	public static void main(String[] args) {

		Node[] nodes = generateNodes();

		// 始点を設定
		nodes[0].setDistance(0);

		// 優先度付きキューにノードを追加する
		PriorityQueue nodeQueue = new PriorityQueue(100, new NodeComparator());
		for ( Node node : nodes ) {
			nodeQueue.add(node);
		}

		while ( !nodeQueue.isEmpty() ) {
			Node node = nodeQueue.remove();
			// 隣接ノードの距離を更新する
			for ( Edge edge : node.getEdges() ) {
				int newDistance = node.getDistance() + edge.getDistance();
				if ( newDistance < edge.getNode().getDistance() ) {
					Node forwardNode = edge.getNode();
					forwardNode.setDistance(newDistance);
					forwardNode.setShortDistanceNode(node);
					// 距離を更新した場合は正しい位置にノードを追加し直す
					nodeQueue.remove(forwardNode);
					nodeQueue.offer(forwardNode);
				}
			}
		}

		// 最短ルートのノードのリストを作る
		List route = new ArrayList();
		Node mostShortNode = nodes[nodes.length - 1];
		while ( mostShortNode != null ) {
			route.add(mostShortNode);
			mostShortNode = mostShortNode.getShortDistanceNode();
		}
		Collections.reverse(route);

		// ルートを表示
		for ( Node node : route ) {
			System.out.println(node.getId() + ":" + node.getDistance());
		}
	}

	private static Node[] generateNodes() {
		Node[] nodes = new Node[22];
		for ( int i = 0; i < nodes.length; i++ ) {
			nodes[i] = new Node(i);
		}
		for ( int i = 0; i < nodes.length - 9; i += 3 ) {
			for ( int j = 0; j < 3; j++ ) {
				nodes[i + j].addEdge(new Edge(nodes[i+j*3+1], 1 + (int)(Math.random() * 30)));
				nodes[i + j].addEdge(new Edge(nodes[i+j*3+2], 1 + (int)(Math.random() * 30)));
				nodes[i + j].addEdge(new Edge(nodes[i+j*3+3], 1 + (int)(Math.random() * 30)));
			}
		}
		return nodes;
	}
}

ソース

ここ１年でSilverlightとAdobe Flexをフロントに据えたプロジェクトを経験した。もちろん実業務で。

感想箇条書き
・Flexバグ多すぎ。Silverlightの品質が良いのではない。Flexの品質が圧倒的に悪い。
・FlexはUIコンポーネントだけでなく、コンパイラも誤ったエラー検出をしたりする。
・AS3(ActionScript3.0)よりはC#の方が使いやすかった。クロージャの記述やコレクションなどはC#の方が楽だった。
・XMLの扱いはe4xのあるAS3の方が楽。
・AdobeはFlex捨てた。(AdobeはHTML5に注力すると宣言したうえ、FlexはApacheに寄贈された)
・Silverlightもしばらくしたら消えるだろうけれど、開発スタイルはWinRTなどへ引き継がれるし移行もおそらく簡単。
・SilverlightのMVVMはなかなか良い。

まとめ： SilverlightかFlexかだったらSilverlight一択。Flexは既に死んでいる。

Alert.show()を使った場合、ダイアログの縦幅、横幅の最大サイズが設定されているおかげで想定外の表示を
してしまう場合がある。これを回避するために、Alertの拡張などを考えたのだけれど、肝心な部分がmx_internalだったり
privateだったりして、うまく拡張できなさそうだった。結局は一から作るハメになる。Flexではよくあること。
とりあえず MessageBox.mxml を作って以下を実現した。
・最大height,widthの拡張
・最大heightを越える場合はスクロールバーを表示。
ただのPanelを継承してるだけなので、あとは自由にカスタマイズできる。

AdvancedDataGridでセルの内容をコピーする方法は各所で紹介されているが
階層データやセル選択モード(MULTIPLE_CELLS)に対応しているものがない。
いろいろ試行錯誤した結果、AdvancedDataGridを継承して、下記のようなコードを書けば
選択中のセルの情報を取得できそうなことがわかった。
最初はlistItemsを使おうと思ったのだけれど、listItemsは基本的に表示中のアイテムしか
保持していないため、選択中のデータの取得には使えなかった。
それにしても、この程度のことが簡単にできないFlexにちょっと萎えた。

public var selectedCellDatas:Array = [];
override protected function addCellSelectionData(uid:String, columnIndex:int, selectionData:AdvancedDataGridBaseSelectionData):void {
	var column:AdvancedDataGridColumn = columns[selectionData.columnIndex] as AdvancedDataGridColumn;
	var label:String = column.itemToLabel(selectionData.data);
	selectedCellDatas.push({
		rowIndex: selectionData.rowIndex,
		columnIndex: selectionData.columnIndex,
		label: label
	});
	super.addCellSelectionData(uid, columnIndex, selectionData);
}
override protected function clearCellSelectionData():void {
	selectedCellDatas = [];
	super.clearCellSelectionData();
}

BigDecimalの演算速度を検証しました。

検証の結果、以下のことがわかりました。
・ div/reminder は遅い
・ doubleのコンストラクタを使うと遅い
・ longのコンストラクタでも毎回newすると計算時間が増える。(まぁあたりまえだけど)
・ 桁が増えると遅くなる

BigDecimalは桁数に応じて内部データの持ち方を変えるようです。
桁が大きくなればなるほど遅くなると思われます。
データがintで表せる数である場合とlongで表せる数値の場合ではガクッと計算速度が変わります。

検証方法：
Core i 5 2500K 3.2GHz のマシンで100万回単純計算

検証コード：

import java.math.BigDecimal;
import java.math.MathContext;

public class Main {

	public static void main(String[] args) {
		long start,end;
		int repeat = 10000 * 100;

		start = System.currentTimeMillis();
		testAdd1D(repeat, 100000);
		end = System.currentTimeMillis();
		System.out.println("add1 loop内new double constructor 桁少なめ ms:" + (end - start));

		start = System.currentTimeMillis();
		testAdd1D(repeat, Long.MAX_VALUE);
		end = System.currentTimeMillis();
		System.out.println("add1 loop内new double constructor 桁多め ms:" + (end - start));

		start = System.currentTimeMillis();
		testAdd1L(repeat, 100000);
		end = System.currentTimeMillis();
		System.out.println("add1 loop内new long constructor 桁少なめ ms:" + (end - start));

		start = System.currentTimeMillis();
		testAdd1L(repeat, Long.MAX_VALUE);
		end = System.currentTimeMillis();
		System.out.println("add1 loop内new long constructor 桁多め ms:" + (end - start));

		start = System.currentTimeMillis();
		testAdd2(repeat, 100000);
		end = System.currentTimeMillis();
		System.out.println("add2 loop外new 桁少なめ ms:" + (end - start));

		start = System.currentTimeMillis();
		testAdd2(repeat, Long.MAX_VALUE);
		end = System.currentTimeMillis();
		System.out.println("sum2 loop外new 桁多め ms:" + (end - start));

		start = System.currentTimeMillis();
		testSub(repeat);
		end = System.currentTimeMillis();
		System.out.println("sub ms:" + (end - start));

		start = System.currentTimeMillis();
		testMul(repeat);
		end = System.currentTimeMillis();
		System.out.println("mul ms:" + (end - start));

		start = System.currentTimeMillis();
		testDiv(repeat);
		end = System.currentTimeMillis();
		System.out.println("div ms:" + (end - start));

		start = System.currentTimeMillis();
		testMod(repeat);
		end = System.currentTimeMillis();
		System.out.println("mod ms:" + (end - start));
	}

	public static BigDecimal testAdd1D(int repeat, double value) {
		BigDecimal sum = BigDecimal.valueOf(23423234.2344);
		for ( int i = 0; i < repeat; i++ ) {
			sum = sum.add(new BigDecimal(value));
		}
		return sum;
	}
	public static BigDecimal testAdd1L(int repeat, long value) {
		BigDecimal sum = BigDecimal.valueOf(23423234.2344);
		for ( int i = 0; i < repeat; i++ ) {
			sum = sum.add(new BigDecimal(value));
		}
		return sum;
	}

	public static BigDecimal testAdd2(int repeat, double value) {
		BigDecimal v = BigDecimal.valueOf(value);
		BigDecimal sum = BigDecimal.valueOf(23423234.2344);
		for ( int i = 0; i < repeat; i++ ) {
			sum = sum.add(v);
		}
		return sum;
	}

	public static BigDecimal testSub(int repeat) {
		BigDecimal sum = BigDecimal.valueOf(234342749.2342342);
		for ( int i = 0; i < repeat; i++ ) {
			sum = sum.subtract(new BigDecimal(1234234.234));
		}
		return sum;
	}

	public static BigDecimal testMul(int repeat) {
		BigDecimal d2 = BigDecimal.valueOf(1123234242.3421);
		for ( int i = 0; i < repeat; i++ ) {
			d2.multiply(new BigDecimal(122343.4));
		}
		return null;
	}

	public static BigDecimal testDiv(int repeat) {
		MathContext mc = new MathContext(20);
		BigDecimal d2 = BigDecimal.valueOf(122343412.3421);
		for ( int i = 0; i < repeat; i++ ) {
			d2.divide(new BigDecimal(12234.34), mc);
		}
		return null;
	}

	public static BigDecimal testMod(int repeat) {
		MathContext mc = new MathContext(20);
		BigDecimal d2 = BigDecimal.valueOf(1223434.123421);

		for ( int i = 0; i < repeat; i++ ) {
			d2.remainder(new BigDecimal(123423.234234),mc);
		}
		return null;
	}
}

出力：
add1 loop内new double constructor 桁少なめ ms:327
add1 loop内new double constructor 桁多め ms:625
add1 loop内new long constructor 桁少なめ ms:30
add1 loop内new long constructor 桁多め ms:90
add2 loop外new 桁少なめ ms:18
sum2 loop外new 桁多め ms:78
sub ms:411
mul ms:444
div ms:971
mod ms:1275