2014年4月12日土曜日

Minimum spanning tree経過-描画方法の変更とベンチマーク

SVGからCanvasへ描画方法の変更

SVGで描画処理をするのは重すぎたのでCanvasに切り替えてみた。

描画するだけなら500個を数秒で描画できたので、比べるまでもなくCanvasの勝ち。

ただし、描画するだけならCanvasが有利だが、クリックしたりドラッグしたりするようなアクションを求める場合はSVG。

Firefoxは線描が苦手?

Fill

Stroke

点の描画をFillからStrokeに変更したところ、フレームレートが半分程度に落ちてしまった。ChromeではこうならないのでFirefoxは苦手としているのだろうか?

プリム法かクラスカル法か

2,000個の点(1,999,000本の辺)でベンチマークをした結果。

プリム法(単純な集合探索と隣接行列)

prim    76,443 ms
total   81,217 ms 

クラスカル法+素集合データ構造

weight  12,324 ms(辺の長さを計算する処理)
sort    27,929 ms(ソートはクラスカル法に含まれる処理)
kruskal     62 ms
total   42,068 ms 

現時点ではクラスカル法が圧倒的に見えます。
※プリム法は最適化を全く行っていない(たぶんアルゴリズムも未熟)、なのでプリム法が悪いとは決めていません。

クラスカル法はソートの改善方法が分からないのでこれが限界みたいです。

参考までに、1,000個でベンチマークをした時は双方10秒前後でした。

ベンチマークの結果で驚いたのは、描画処理が思いの外速かったことです(数100msで終わっている)。遅いのは描画処理のせいだと思い込んでいたのは間違いでした。