« ルー語変換を MeCab だけで実現 | メイン | 父親になった »

2007年02月07日

ソートの平均要素移動距離

配列をソートする際に各要素の平均移動距離はどれくらいになるか問題が同僚の間で話題になった. 結論から言ってしまえば，サイズ n の配列の場合平均移動距離は n/3 になるらしい．

サイズ n の場合, 最右の要素は [0 .. n-1] に等確率で移動するので，直感的に考えると n/2 のような気がする．しかし，真ん中の要素は両側に移動するので，その距離は小さくなる．平均移動距離は n/2 より小さい値になるはずだ.

頭で考えるより手を動かしたほうが楽なので，モンテカルロサンプリングしてみた. 配列をランダムにシャッフルし，ソート済みの配列と比較して各要素の平均移動距離を求める．これを 1000 回繰り返し平均値を計算する. 

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
static const size_t size = 1000;
static const size_t max_trial = 1000;
int main() {
  std::vector<int> ary(size);
  for (int i = 0; i < size; ++i) ary[i] = i;
  size_t sum = 0;
  size_t trial = 0;
  for (int n = 0; n < max_trial; ++n) {
    std::random_shuffle(ary.begin(), ary.end());
    for (int i = 0; i < size; ++i) {
      sum += std::abs(ary[i] - i);
      ++trial;
    }
  }
  std::cout << static_cast<float>(1.0 * sum / trial / size) << std::endl;
}


ivy:~% c++ -O3 foo.cpp
ivy:~% ./a.out
0.33348
すばらしい．確かに 1/3 というのは正しいようだ.

まだしっくりこないので，数学的に証明してみる.

サイズ n の配列のインデックス [0, 1, 2 ... k, ... n-2, n-1] を考える．各要素は等確率 1/n で別の要素に移動する．インデックス k の平均移動距離は左側と右側で場合わけしてかんがえると
左側の要素 L(k) = k/n + (k-1)/n + ... + 1/n + 0/n = k * (k + 1) / 2n
右側の要素 R(k) = 1/n + 2/n + .... + (n - k - 1)/n = (n - k - 1) * (n - k) / 2n
となる.

平均移動距離は k を 0..n-1 まで動かして足し合わせて，n で割ればいい． (平均移動距離 = [\sum_{k=0..n} L(k) + R(k)] / n). ここでは漸近的な振る舞いだけ分かればいいので，R(k) + L(k) の最大次数の項だけみて級数和を積分で置き換えてもかまわない.

[R(k) + L(k)]/n の最大次数は L(k)/n の k^2 / 2n^2, R(k)/n の k^2 / 2n^2 を足し合わせて k^2 / n^2 となる． これを k = 0..n の区間で積分すればいいので，n^3/3(n^2) = n/3 になる． (∵∫x^2 dx = (x^3)/3) これは n → ∞ の漸近的な振る舞いなので，n が小さいときは余剰項の影響をうける．

ということでスッキリ!

投稿者 taku : 2007年02月07日 22:43

トラックバック

このエントリーのトラックバックURL:
http://chasen.org/~taku/blog/mt-tb.cgi/219

このリストは、次のエントリーを参照しています: ソートの平均要素移動距離:

» 副収入総合サイト from 副収入総合サイト
副収入総合サイトのことなら、副収入道で一番活気のあるサイトにお任しアレ。 みるみるうちに、収入アップ！ なるほど、こりゃあ間違いなしだ。。。 [続きを読む]

トラックバック時刻: 2007年02月15日 19:16

» 魁!!副収入道〜アフィリエイとで副収入 from 魁!!副収入道〜アフィリエイとで副収入
魁!!副収入道〜アフィリエイとで副収入 脱サラするなら、まずは要点を理解し、働きがならできる事から着実に実行していきましょう！ [続きを読む]

トラックバック時刻: 2007年02月26日 03:05

» このビデオを見逃した人は他にいませんか？ from 速報！究極の在宅ワーク情報！初心者でも簡単に不労所得を手にする方法！
お知らせです。先日、参加費３９万８千円の世界で最も有名なインターネットマーケターであるヤニクシルバーのビデオが無料.で公開されている事をお知らせしました。... [続きを読む]

トラックバック時刻: 2007年03月03日 08:06

» ◆ＦＸ常勝バイブル◆外国為替証拠金取引で、貴方も、お金のゆとりと最高の幸せをＷｉｎ！ from ◆ＦＸ常勝バイブル◆外国為替証拠金取引で、貴方も、お金のゆとりと最高の幸せをＷｉｎ！
「FX常勝バイブル」は、FX-外国為替証拠金取引で、投資資金を決して減らすことなく、 １００％の勝率で、月間２５％の利益率を得られるノウハウが収められ... [続きを読む]

トラックバック時刻: 2007年03月09日 01:46

» アフィリエイト　問題の解決策 from アフィリエイトしよう！アフィリエイト情報館
アフィリエイト　問題の解決策 ブログを共同運営していくとアフィリエイトを絡めてい... [続きを読む]

トラックバック時刻: 2007年03月09日 22:44

» 在宅ワーク　Happy Mail from 在宅ワーク、パソコン、内職、完全攻略、主婦でもＯＫ！
在宅ワーク　Happy Mail 女性に人気の在宅ワークであるメールレディを募集... [続きを読む]

トラックバック時刻: 2007年03月12日 22:14

» 【１６日１４時３０分~発売開始！】【２９時間限定発売】菅野×加藤×進藤×宮川×原田×蝶乃のスペシャルパッケージ【特典ＤＶＤ４枚組付】その名も・・・インターネットボンバイエ！ from チョイワル親父の無料レポート
●チャンスは２９時間しかありません。実は、たった２９時間しかチャンスのない特別なお知らせがあります。先日、都内某所で月１０００万を稼ぎ出す６名が対談を行い... [続きを読む]

トラックバック時刻: 2007年03月13日 16:47

» 誰も公開しなかった月収１００万円ネット成功マニュアル from 育児・子育てへの育児・子育て情報クラブ
驚愕！誰も公開しなかった月収１００万円越えのネット起業自動成功マニュアル（再販権付）これは成功できなかった人のためノウハウなのです。あなたは大変な努力と時... [続きを読む]

トラックバック時刻: 2007年03月15日 17:55