英語の勉強にMITの講義でも Lec 5 | MIT 6.046J / 18.410J Introduction to Algorithms

English

タイトル微妙に変えました。少しづつ進めて行きます。

今回もsortingっぽいが、sortingがアルゴリズムの基本であることは、前回までの講義で明らか。

How first can we sort?

  • 僕としては、n log nかなと。曖昧だな。
    • Often correct.らしい。
  • It depends.

Depends on Model

  • of what you can do with the elements.
  • Can we do better than Θ(n log n)?
    • Yes or No?
    • おぉ。主題に迫ってきた感。

Comparison sort

  • お、初めて聞くアルゴリズム。と思ったら、「モデル」についての話だった。
    • と、気付くまでに相当の時間を要した。
  • Comparison sort - Wikipedia
  • 比較ソートは全て決定木で表すことが出来る。
    • 再帰も、forで表せば決定木だな。
  • リストの順列はn!あるので、決定木の葉の数はそれ以上になる。決定木の高さh=計算量である。決定木が持てる最大の葉の数は2^h。つまり、n! <= 2^h , h >= lg n!、スターリングの公式より(It's a magic!)・・・= Ω(n log n)になる？スターリングの公式がわからん。
    • 決定木の全体像はとんでもなくでかい。
  • だいぶ迷走したが、ようやく感覚的に理解できた。数学的には詰める所がいっぱいあるな。
  • 途中でアルゴリズムを切り替える手もアリ。

Sorting in linear time

  • 来ました。
  • How first can we sort? → n log n. → Often correct. "It depends."

Counting sort

  • 度数分布を使う方法。
  • 頭いいな。
  • とりあえず考察。
    • 予めデータの範囲がわかっている必要がある。
    • 初期化(キーの範囲 k)とカウント n、再配置(k + n)で済むな。= 2(k + n) = Θ(k + n)→早い？→kがでかいと初期化、位置計算で泣ける。→kに依存する。
    • ヒープを使えば、データの範囲を除外出来る→早くね？→ヒープ作成に最大n log nのコストがかかるな・・・→重複が多い事が条件か・・・
    • 結論：データの値に強く依存する。→"It depends."
  • ま、聞くべ。
    • おぉっと、僕の考えていた方法と講義と再配置の方法がちょっと違った。
    • 予め戻る位置を計算しておけば、元のデータをもう一度走査しながら、付随する情報もソートできるのか。→Counting sortは安定ソート。
      • 考察を修正：初期化 k →カウント n →オフセットの計算 k → 配置 n なるほど！！
  • アルゴリズムの選択は重要だな。
  • 考察したことを解説。

Stable sort

  • 同じ値だった場合、元の順序を保つなら、stable

Radix Sort

  • とりあえず考察編。
    • 基数ソート - Wikipedia
    • Counting sortの欠点を補い、データの範囲が広くてもまぁまぁ対応できそう。
    • 基数ソートの各要素に、Counting sortを使ってみると、
    • 8ビットなら、2(n + 2) x 8 = 16n + 32
      • データ数が少ないとパフォーマンスが出ない。データ数nが2^16 + 32 = 65536 + 32以上なら比較ソートより早い？
    • あぁ、8ビットだと0〜255個の範囲なので、10進数だと、2(n + 10) x 3 = 6n + 60か。
      • データの範囲と、nによって最適な基数は変化しそうだ。最適な基数は・・・。
    • 条件次第だが、n log nを凌ぐパフォーマンスが出せそうだ。→"It depends."
  • 聞く。
    • パンチカードに関する貴重な話。
    • 並べ替えてみると、安定ソートを上手く使ってるなぁ。
    • 最適な基数は・・・。の答えが出てたありがたいｗ
    • という事で、O(bn / log n)っと。
  • 続きはnext fallか。聞けるかな・・・。

まとめ

  • ソートの理論限界はΘ(n log n)は間違いで、「比較ソートの理論限界はΘ(n log n)」である。
  • 条件によっては、もっと早いアルゴリズムを選択することも出来る。

ふと思ったこと

  • 挿入ソートの高速化について。
    • 挿入ソートの挿入時にバイナリサーチすれば、ちょっと早くなるな。
      • 固定配列だとずらしが必要で、連結リストだとバイナリサーチが苦手。
      • →却下。
    • 連結リストならば比較だけで、交換処理が不要なので、Θ(n^2)変わらないけど、ちょっと高速化出来るのか。
    • 連結リストだと、バイナリサーチしにくい。ならデータをヒープにしちゃえばいいよね→ヒープソート。
    • ありがとうございました。
  • Interactive transcript
    • いまさら気付いたけど、超便利。
    • 字幕で好きな所まで飛べる。
    • 辞書で調べるのが楽。

単語

comparison n
the process of comparing two or more people or things 比較、対照
restriction n
a rule or law that limits what you can do or what can happen 制限、制約 limitとは若干違う。
internal adj
connected with the inside of something 内部の
implement v
to make something that has been officially decided start to happen or be used 履行する、要件を満たすように実行する
permeation n
to spread to every part of an object or a place 浸透、普及
radix n
1. the base of a number system or of logarithms 基数

お詫び

Fedoraインストール〜2012/10/23までの記事でリンク先に誤りがありました。