groovy ソートの平均要素移動距離 - というものらしい。 2007/08/11

きまぐれ日記: ソートの平均要素移動距離

上記の記事を読みまして、手習いがてらに、groovyで表現してみました。


シナリオ

配列をランダムにシャッフルし，ソートするした場合の要素の平均移動距離を求めてみてください。

import java.util.*;

def m_size = 1000;
def max_trial = 1000;

def ary = [];
(0..<m_size).each { i -> ary[i] = i; }

def sum = 0;
def trial = 0;

(0..<max_trial).each {
Collections.shuffle(ary);
(0..<ary.size()).each { i ->
sum += Math.abs(ary[i] - i);
++trial;
}
}
def result = sum / trial / m_size;
print "計算結果:${result}"

def result = sum / trial / m_size;

の部分は、移動した距離の総和を試行回数で割って、それを配列のサイズで割るということですね。

えーと、ソートするとソートされる要素が配列の中で、全体の距離の、３分の１を大体が移動するという理解でいいのかな。

ちなみに、上記の元ネタの記事では、数学的な証明を行っていましたよ。
僕自身、はなはだ数学がだめなので、それはパスしました。

モンテカルロ法はよく確率を近似的に求める手法として使われる。n回シミュレーションを行い、ある事象がm回起これば、その事象の起こる確率は当然ながらm/nで近似される。試行回数が少なければ近似は荒く、試行回数が多ければよい近似となる。モンテカルロ法 - Wikipedia

なるほど。