思いつき
帰りの電車の中での思いつき。 反発力の計算は二乗のオーダーだけど、空間分割を入れると軽くなるよね。 空間分割を入れるのもいいけど、xの値でソートしておいてその順で一定範囲いないかどうかのチェックを行えば、xの差が限界半径を超えたらもうその先には半径以内の点は存在しないのでbreakできる。頂点数が少ないとき＆密度が高いときにはメリットが薄いけど、そもそも反発力の計算が二乗のオーダーであるせいで重たくなるのは頂点数が多いとき。頂点数が少ないときにはソートもさほど時間がかからないし、入れてみる価値はあるかも知れない。また、この「順序」は基本的に直前の結果とあまり変わらないので、「ほぼソートされているデータのソート」になりますね。挿入ソートがいいのかな。
せっかくだからパフォーマンスの比較をきちんとやってみよう。1万頂点くらいで。
