2017-03-08

ALDS1_6 Quick Sortを解く話

情報系の学生ならみんな知っているクイックソートを解く．

自分は学部時代にやったはずだが，まったく覚えていなかった．

特徴

配列を分割統治でソートするアルゴリズム
配列を2つに分割する際におおまかにソート（Partitionアルゴリズム）
分割した配列を引数にそれぞれ再帰的にQuicksortを呼び出し
補助的な配列を必要としない（マージソートは必要）in-placeなアルゴリズム
Pivot（Partitionの閾値）の選び方によって様々な種類が存在．沼が深そうなので今回は配列の最後尾をPivotとするLomuto partition schemeを実装．

アルゴリズム

ALDS1_6-B Partitionを関数内で利用．

Quicksort(A, l, r)
If l >= r
return
p = Partition(A, l, r)
Quicksort(A, l, p - 1)
Quicksort(A, p + 1, r)

計算量

最悪ケースではPartitionに $O(n)$ 必要．また，配列の要素数が $n$ のときPartitionでの2分割は $O(log_2(n))$ 回実行. よって全体の計算量は $O(nlog_2(n))$ .

実装

gistba1b8bbf64e8d297a504469b5b3f3c6b

感想

Partitionが理解できていれば問題なし．配列の最後尾をPivotとして選ぶのは今まで知らなかった．なんとなくクイックソートは真ん中で分割していくやつかー，とかずっと思ってた．

2017-03-06

ALDS1_6-B　Partitionを解く話

AOJ

クイックソートで使うPartitionを実装する．

特徴

・閾値以下か，それより大きかで配列を分割するアルゴリズム．

・閾値で分けるだけなので全体はソートされない．

アルゴリズム

Partition(A, l, r)
threshold = A[r]
i = l - 1
for j = l to r - 1
if A[j] <= threshold
i = i + 1
exchange(A[j], A[i])
i++
exchange(A[i], A[r])
return i

計算量

最悪ケースではjが増えるたびに交換するので $O(n)$ .

実装

gist6642213dcdfec5d8dbf6d23f0436e01b

感想

とにかくクイックソートのために必要なアルゴリズムという印象．

クイックソートで使用するときは最後にi + 1を閾値の位置として返す．

2017-03-02

ALDS1_5_B Merge Sortを解く話

AOJ

AOJのマージソートを実装する問題です．

特徴

・分割統治と再帰を上手く使ったソーティングアルゴリズム

・配列を1要素になるまで分割してくっつき直すときに比較．

アルゴリズム

Mergesort(array, left, right)

要素数が1ならソート済みなのでreturn．（実装では left + 1 < right)
配列を半分にする．
左半分をMergesortに渡す（実装では再帰を使う）．
右半分をMergesortに渡す（同じく再帰）．
マージ．

計算量

マージがn回，分割が $log(n)$ 回なので計算量は $O(nlog(n))$ ．

実装

分割した配列の末尾に番兵を配置するのに注意．

gist46eccdb4e29c4cc01cc448b894cf8814

感想

マージソートに対する僕のイメージは全結合していないニューラルネット．

入力層にこれからソートする配列を渡す．
層を進むにつれて配列は分割され次の層へ．
一番真ん中の層が配列が1要素数になるまで分割された状態．
この後の層では比較とマージをする．

てな感じ．これで覚えておけばそらで書けるかな．

2017-02-28

ALDS_1_1_A: Insertion Sortを解く話

AOJ

挿入ソートを実装する．

特徴

未ソート部とソート済み部に分けてソート
トランプの手札を並べ替える感じ
挿入ソートの改良版がシェルソート

アルゴリズム

これ．

www.youtube.com

二重ループの外側と内側の進む向きが違うので注意．

計算量

内側のループのたびに要素が移動する最悪のケースを考えると

$1 + 2 + ... + N - 1 = (N^2 - N) / 2$

最大次数の項以外は無視するので，挿入ソートの計算量は

$O(N^2)$

実装

gist9bc97b8b935211285ee025a9312ee372

感想

直感的でわかりやすいアルゴリズムだと思う．

先日，友人と大富豪をやったときも手札の並べ替えに挿入ソートを意識していた．

2017-02-10

「国際会議論文の読み方・書き方」を読んだ話

研究

http://www.phontron.com/slides/neubig15nlptutorial.pdf

グラムニュービック先生が書いたチュートリアルスライドである．

とても良い．

最近は論文を読むときに，このスライド通りに書かれているか自分の頭の中でチェックしている．たまにチェック項目を忘れるので，全部のページを印刷したくらい気に入っている．

グラム先生はNLP分野の方で「自然言語処理の基本と技術」という本も書いている．

ちなみに一か月前くらいにこの本を読んだが，ビタビアルゴリズムが漢字変換にどう使われているのか等，なるほどなぁと思う部分が多かった本である．

www.shoeisha.co.jp

「国際会議論文の読み方・書き方」は主にNLPの会議を例として説明が進む．

良い論文とは？，論文執筆のプロセス，論文の各章の役割と書き方，ダメ例，執筆後にやること，が書かれており「国際会議」に限った話ではなく，B4や修士など論文を書き始める人に役に立つはずだ．

特にこのスライドが良いと思った理由は，普段自分がわかりやすいなぁと感じる論文がこのスライド通りに書かれていることに気づいたからだ．

「問題の定式化」を明確に書いているか，いないかの違いはわかりやすさに大きな影響を与える．問題を定式化することで，読者は提案法がベストな解決手段なのか判断しやすくなるし，「こうゆう手法でも解けるのでは？」と読者に新しいアイディアを想起させやすくなると思う．

また，

完成された研究なんてない．書いてみよう！

この部分を読んで，問題点を見つけるための実験と，手法を評価するための実験は区別しなきゃなぁ，と自分は感じた．実験をすれば用いた手法の粗などすぐ見つかるし，ましてや修士レベルでは実験をする前から粗があるのが分かっている場合もあるだろう（もちろんダメ例であるが，実験をしない限り結果が出ないわけで修論が書けないのである）と思うのであった．

ちなみに参考文献にあるSimon先生の論文の書き方

www.microsoft.com

も読んだ（Youtubeに講義ビデオもある）．

だいたいグラム先生と同じ主張をしているが，abstractの4文の内容が若干異なる．自分はSimon先生のほうがしっくりくるかなぁ．これも時間があったら感想を書こう．