2019-10-05

CS 6.006 Lecture 12 Square Roots, Newton's Method を見る

CS 6.006 Lecture

わかったこと

Multiplicationの時間計算量

$n$ 桁どうしの掛け算を行うときの時間計算量は、 $O(n^\alpha)$ で与えられる。

naiveなアルゴリズム: $\alpha=2$
Karatsuba: $\alpha=log3=1.584$

DivisionはNewton Method + Multiplicationによって行われる

$\frac{a}{b}$ を求めたいとき、 $\frac{1}{b}*a$ と考え、 $\frac{1}{b}$ を先に求める。
$\frac{1}{b}$ を求めたいとき、 $R=2^{k}$ として、 $\lfloor{\frac{R}{b}}\rfloor$ を求める。 $\frac{R}{b}$ の結果は整数となり、扱いやすい(?)上に、 $R=2^{k}$ であればビットシフトだけで割り算ができるからである。
$\lfloor{\frac{R}{b}}\rfloor$ を求めたいとき、 $f(x)=\frac{1}{x}-\frac{b}{R}$ となる関数を考え、 $f(x)=0$ になる点を探すことで $\frac{R}{b}$ を求める。 Newton法である。このようにすると複数のMultiplicationとRによるビットシフトだけで計算が可能になる。

参照→Lecture Notes | Introduction to Algorithms | Electrical Engineering and Computer Science | MIT OpenCourseWare

$f(x)=\frac{1}{x}-\frac{a}{b}$ を直接考えれば？と思ったが、これだとaによる割り算が必要になるので、Rによるビットシフトが行えるという点が大事なのだと思う。

pythonの整数の扱い

pythonでは多倍長整数として扱われる。32bitにおさまらなくなったら、余分にメモリを確保して、まとめて一つの数字として扱えるようになっている。 pythonの思想である、プログラマはロジックに集中するべきという思想に基づくらしい。

多倍長整数の演算は、整数を格納した複数の32bitメモリをひとつなぎにして、下位の桁から計算し、carryがあった場合に上位の桁に渡すことを繰り返すようになっている。このスライドが参考になった。リンク

2019-10-03

CS 6.006 Lecture 9 Table Doubling, Karp-Rabin を見る

CS 6.006 Lecture

表記:

n: テーブルに入っている要素のサイズ

m: テーブルのサイズ

とする。

わかったこと

Table Shrinkingでは、縮めるタイミングとサイズの係数をずらすのが良い

テーブルの要素の追加・削除を繰り返し、n = m/2となったタイミングでテーブルを縮めるとする。このとき、m = m/2になるように縮めてしまうと、n = mとなり、

テーブルのサイズ = テーブル内の要素数

となる。ここで、次に要素が追加された場合、Table Doublingが起こり、m = 2mのサイズをもう一度作る。このとき、O(2m)の計算量がかかり、非効率。

そもそも、テーブルのサイズ = テーブル内の要素数はテーブルがギリギリの状態であり、よくない。これを避けるためには、 n=m/4となったタイミングでm = m/2 になるように縮めればよい。こうすると、ギリギリの状態をさけることができる。

Karp-Rabin アルゴリズム(Rolling Hash)では、modによる比較的単純なhashを使う

文字列検索のアルゴリズム。文字列 $s$ のなかから文字列 $t$ があるかどうかを返す時、以下のようなアルゴリズムを用いる。(参考: Rabin–Karp algorithm - Wikipedia)

function RabinKarp(string s[1..n], string pattern[1..m])
  hpattern := hash(pattern[1..m]);
  for i from 1 to n-m+1
    hs := hash(s[i..i+m-1])
    if hs = hpattern
      if s[i..i+m-1] = pattern[1..m]
        return i
  return not found

hashを毎回計算するときは、sha256のような複雑なものを使うと思っていたが、実際には、それだと計算量が高いので、文字列を数字に変換したものをつなげてmod p をとることでhashを計算する。ここで、pを素数にしておくと、inverse prime numberによるテクニックが使えて、大きな数に対しても比較的高速にmodが計算できる。 (参考: Modular multiplicative inverse - Wikipedia)

注意点 1.

上にのせたコードについて

s[i..i+m-1]

の部分は、純粋にpythonのリストを使ってしまうと $O(m)$ かかってしまうが、 $s[i$ , s[i+1], ...]を数字に変換したものを横に繋げた数字 $n$ を保持しておくことで、加減乗除( $O(1)$ )で $n$ が更新できる。

文字列を数字に変換するときは、文字を0~255で表現すればよい。char型の文字は 1Byte = 8bit = 256通りの文字を表すという事実を知っていれば、普通出てくるような文字(キリル文字とか漢字は除く)は0~255のどれかで表すことができる。

2019-09-17

CS 6.006 Lecture 8 Hashing with Chaining を見る

CS 6.006 Lecture

わかったこと

ディクショナリはハッシュ表、Binary Search Treeの上位概念

Pythonでお馴染みのディクショナリ。ディクショナリは

insert
delete
search

を行うもので、具体的な実装方法としてハッシュ表、Binary Search Treeがある。ディクショナリとハッシュ表を同じレイヤのものだと思っていたが、あくまでディクショナリが上位の概念。

ディクショナリの利用例

文字頻度のカウント
コンパイラにグローバル変数を保存する (Pythonの古い実装)
ネットワークのルータ (IPアドレスとホストの対応づけ?)

PrehashとHashの違い

Pythonでimmutable(値を後から変更できない)な任意のオブジェクトをディクショナリのキーに突っ込めるのは、Prehashのおかげ。 Prehashはオブジェクトから適切なintegerを返す関数で、Hashとは違う位置付け。オブジェクトのidが使われる(?)が、クラス内のhashメソッドを自分で実装することもできる。が、自前で実装することはあまりお勧めされていない。講義中でもDon't mess with itと言われている。これは、オブジェクトの内部の値などが変わってしまった時にhashの計算結果が変わってしまうことで、オブジェクトから計算されるキーの値が変わってしまうから。 mutableなオブジェクト(値をあとから変更できるオブジェクト)をキーにすることができないのはこのためで、値が変わってしまい、キーが変わってしまう恐れがあるから。 Pythonだと、set, list, dictがimmutableなオブジェクトとしてあげられる。

参考： medium.com

2019-09-05

CS 6.006 Lecture 7 Counting sort, radix sort, lower bounds for sortingを見る

CS 6.006 Lecture

トピック

Insertion Sort
Merge Sort
Heap Sort
Counting Sort
Radix Sort

わかったこと

Insertion, Merge, Heap Sortは要素同士の大小関係の判定(Comparison)を行うが、これを行なっている限り最低でも $nlogn$ の計算量がかかる。

理由

最低かかる計算量は、決定木の高さに等しい。答えのパターンを葉としてもつ決定木を考える。例えば、10個の要素がある配列のソートした時の答えとして、

A[0]<=A[1]<= ... <=A[9] とか

A[3]<=A[6]<=...A[2]

というパターンが考えられる。 (もちろん正しいのは一つのみ。)

とすると、答えのパターンは全部で $n!$ 通りあるので、決定木の木の高さは $log(n!)$ である。(底は2) 決定木の高さ=最低限必要な計算量なので、log(n!)の下限を求めることで、 $\Omega(nlogn)$ がわかる。

Counting SortはStableにソートすることができる。

今までの自分のCounting Sortの認識

a = [4, 2, 0, 3, 1, 3]をソートするとき。

各数字の出現数をメモしたいので、0, 1, 2, 3, 4の出現数を記録するための配列cntを作る。(長さは5になる) cnt = [0, 0, 0, 0, 0]
aをスキャンして出現数をカウントする。 cnt = [1, 1, 1, 2, 1]
cntをスキャンして、sorted_aに要素を入れる。

sorted_a = [0 for _ in range(len(a))]
target_ix = 0
for i in range(len(cnt)):
  value = i
  count = cnt[i]
  while count:
    sorted_a[target_ix] = i
    count -= 1
    target_ix += 1

問題点

Stableなソートができなくなる。Stableとは、ソートの前後で同じキーを持つ要素の順番が変わらないことを言う。上の例では、キーはaに出て来る数字そのものとしたが、aが例えばHumanオブジェクトの配列で、身長順に並べたい時、同じ身長のオブジェクトの順序が保証されなくなる。

Alice = Human(身長150, 体重40) Bob = Human(身長160, 体重50) Charlie = Human(身長150, 体重70) のとき、AliceとCharlieは同じ身長なので、順序はどちらでも良いと思うかもしれない、が、常に出現した順を保ってソートしたいという状況がある。これを実現するのがStable Sortである。

[Alice, Charlie, Bob]であればStable Sort, [Charlie, Alice, Bob]の可能性があるならUnstable Sortである。

Counting Sort + Stable Sortを行うには？

上に書いた3.のステップをこのように書き換える。

3'. cntを直接スキャンする前に、前処理を加える。 cnt =「各数字の出現数」だが、各数字の、「その数字より小さい要素の個数」を表すように変形する。 cnt = [1, 1, 1, 2, 1]であれば、 cnt = [0, 1, 2, 3, 5]である。ここで、それぞれの数字は、ソートされた配列に入るべきインデックスを表している例えば、cntの4番目の要素cnt[4]は、5である。これは、4という数字はソートされたら5番目にくる、ということを表している。

4'. aをスキャンし、cntを元に、sorted_aに要素を入れる。

sorted_a = [0 for _ in range(len(a))]
for num in a:
  target_ix = cnt[num]
  sorted_a[target_ix] = num
  cnt[num] += 1

ここで、最後の行でcnt[num] += 1しているのは、もう一度同じ数字が出てきたときに、同じインデックス(target_ix)に入らずに、次のインデックスに入れるようにするためである。

このようにして、stableなソートが実現できる。

Counting Sortの計算量などは、動画で十分説明されているし、よくわかったので省略します。

2019-09-03

CS6.006 Problem Set 2を解く

CS 6.006 Problem Set

問題はこちら

今回は大問2のコーディングの部分のみ。時間あったら大問1のrecursion treeの話も追記します。

Pythonプロファイラを使ってボトルネックを特定する問題。プロファイラを使う点で実用的。プライオリティキューが実装されていて、最小値をとってくる関数がO(n)の線形探索として実装されているので、 heapを使って正しくO(1)の操作に直しましょうという問題。

ヒープはPythonのListで実装してある。実装するべきメソッドは、

find_min()
append()
pop()

である。

append()した時、pop()した時にListをきちんとheapify(ヒープ化)する必要があるが、 - 前者はappendされた要素を親と入れ替えるように、(上にむかって木を登るイメージ) - 後者はpop()されたrootに末尾の要素を入れ、その末尾と子供を比較して入れ替えるように(下に向かって木を降りるイメージ) の2通りでheapifyする必要がある。 (これ賢くしたら一元化できるのでしょうか？)

上に向かうheapifyは親要素と比べて入れ替えることを再帰で繰り返せば良いので簡単。下に向かうheapifyは、右の子がOutOfIndexのとき(つまりまだ無いとき)を場合分けして記述しないといけないので注意。

正解実装だと、heapを表すListの先頭にNoneが入っていて、インデックスを1から始めるようにしている。こっちのほうが親インデックスなどを求める時楽なのだろうか？

2019-09-02

DB/トランザクションについて勉強してみる

ISUCON8のPythonプログラムで、 db.autocommit(false)なる行が何をしているのか調べる。コミット？トランザクション？よくわからない言葉がでてくる。トランザクションについてはzd6ir7さんのQiita記事がわかりやすかった。

トランザクション

「複数の処理をまとめた、一つの大きな処理」がトランザクションである。

「トランザクション」が成功 → 「コミット」することでデータベース更新「トランザクション」が失敗 → 「ロールバック」することでデータベースをトランザクション前の状態に戻す。

MySQLとトランザクション

SET autocommit = 1

で各SQL文が実行されるごとにデータベースを永続化(更新)する。デフォルトではこの設定になっている。

Multiplicationの時間計算量

DivisionはNewton Method + Multiplicationによって行われる

pythonの整数の扱い

Table Shrinkingでは、縮めるタイミングとサイズの係数をずらすのが良い

Karp-Rabin アルゴリズム(Rolling Hash)では、modによる比較的単純なhashを使う

ディクショナリはハッシュ表、Binary Search Treeの上位概念

ディクショナリの利用例

PrehashとHashの違い

Insertion, Merge, Heap Sortは要素同士の大小関係の判定(Comparison)を行うが、これを行なっている限り最低でもの計算量がかかる。

理由

Counting SortはStableにソートすることができる。

今までの自分のCounting Sortの認識

Counting Sort + Stable Sortを行うには？

MySQLとトランザクション

Insertion, Merge, Heap Sortは要素同士の大小関係の判定(Comparison)を行うが、これを行なっている限り最低でも $nlogn$ の計算量がかかる。