Disjoint Sets (Cousera Data Structure week3)
CouseraのData Strucureコースのweek3の内容です。
www.coursera.org
前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com
Disjoint-set
Disjoint-setは以下の操作を持つデータ構造である
- MakeSet(x):集合{x}を作る
- Find(x):xを含む集合のIDを返す
- もしxとyが同じ集合に属していればFind(x)==Find(y)
- Union(x, y):xとyを含む2つの集合を結合する
単純な実装
- 集合の最も小さい値の要素をその集合のIDとして使う
- smallest[1...n]のような配列を使う
- smallest[i]にiが所属する最小の要素の値を入れる
効率的な実装
- 単純な実装のボトルネックはUnion操作である。
- Linked listを使うことでより効率的な実装が可能。
- 集合をLinked listで表し、listの末尾を集合のIDとして使う
↓
- メリット
- Unionの実行時間がO(1)
- デメリット
- 末尾を探すためにリストを走査する必要があるため、Findの実行時間がO(1)
- xのリストの末尾とyのリストの先頭を定数時間で取得できる場合のみUnionの実行時間はO(1)
木構造を用いたさらに効率的な実装
- 集合を一つの木で表す
- IDはその木構造のルート
- parent[1...n]という配列を使う
- parent[i]はiの親もしくはiがルートであるならばi自身
- どのように2つの木をマージさせるか?
- 片方の木をもう片方のルートノードの下にぶら下げる
- 木を浅くしておくため、短い木をぶら下げる
- 木の高さを素早く見つけるために各サブツリーの高さを配列rank[1...n]に保持しておく
- rank[i]はルートがiであるサブツリーの高さを表す
- 高い木の下に短い木をぶら下げることをunion by rank heuristicと呼ぶ
まとめ
union by rank heuristicを使うことでUnionとFindの実行時間がO(log n)になる
Path Compression
木の高さを短くする方法。例えば以下の図の例でFind(6)を実行する場合、ノード6からルートノードまで親を辿っていく必要があるが、その際12と3もルートノードも同時にわかるので以下の様に木を変形できる。
O(log n)の操作をn回繰り返すときの計算量をlog*nと定義する。
つまり一回の操作の時間計算量は漸近的にO(log*n)となり、実質的にlog*n < 5のときは定数時間とみなせる。
まとめ
- 各集合を木構造で表現する
- ルートノードをその集合のIDとする
- Union by rank heuristic
- 高い木のルートの下に短い木を吊り下げる
- Path Compresion heuristic
- ある特定のノードのルートを見つけるときに、走査したノードをルートの下に吊り下げる
- 償却的時間計算量はO(log*n)
- 現実的なnの値でほぼ定数時間
Priority Queues (Cousera Data Structure week3)
CouseraのData Strucureコースのweek3の内容です。
www.coursera.org
前回のweek2の内容の記事はこちら
rikeiin.hatenablog.com
Priority Queues (優先度付きキュー)
Priority Queueは通常のキューに格納されている要素に優先度がついたデータ構造である。
C++ではpriority_queue、JavaではPriorityQueue、Pythonではheapqとして実装されている。
典型的な用途としてはジョブのスケジューリングなどがあげられる。
priority queueは以下の操作を持っている。
- Insert(p):新しい要素を優先度pで挿入する
- ExtractMax():優先度が最大の要素を取り出す
オプションで以下の操作を定義することもある
単純な実装
ソートされていない配列・リスト
- Insert(e)
- 要素eを末尾に追加する
- 実行時間はO(1)
- ExtractMax()
- 配列・リストを走査する
- 実行時間はO(n)
ソートされた配列
- ExtractMax()
- 最後の要素を取り出す
- 実行時間はO(1)
- Insert(e)
- 要素eの場所を探す(二分探索でO(log n))、右の要素を一つずつづらし(O(n))、挿入する(O(1))
- 実行時間:O(n)
ソートされたリスト
- ExtractMax()
- 最後の要素を取り出す
- 実行時間:O(1)
- Insert(e)
- 要素eの場所を探し(二分探索が使えないため、O(n))、挿入(O(1))
- 実行時間:O(n)
実行時間まとめ
Priority Queues: Binary Heaps(バイナリーヒープ)
Binary max-heapの定義は子より親のほうが値が大きい場合の二分木である。
以下がヒープである例
ヒープではない例
基本的なヒープに対する操作
GetMax
Insert
新しい要素を木の末端の葉にくっつける。
この操作において子より親の値が大きくなればならないという条件を満たしていな場合、以下のSiftUpという操作を条件が満たすまで行う。
SiftUp
シフトアップは子の大きい値と親の小さい値を入れ替えるという操作であり、木がヒープの条件を満たすまで繰り返す。
実行時間はO(木の高さ)である。
ExtractMax
木の根と葉を入れ替えることで行う。
上の木に対してExtractMaxを行うと以下のようになる。
当然これはヒープの条件を満たしていないため、以下のSiftDownという操作を行う。
SiftDown
SiftDownは親の小さい値と子の大きいを入れ替えてノードを下にずらす操作である。
上の図の例では12と29を入れ替える。このとき左右の子の大きいほうと入れ替えること。
この操作をヒープの条件を満たすまで繰り返す。
もちろん実行時間はO(木の大きさ)
ChangePriority
任意のノードを任意の値に変える。その後にヒープの条件を満たすようにSiftUpかSiftDownを繰り返す。
Remove
削除したいノードの値を∞にかえる。
その後、ヒープの条件を満たすようにSiftUpを繰り返す(最終的に∞が根に来る)。
その後はExtractMaxと同じ操作を行う。
実行時間はO(木の高さ)
ヒープ操作のまとめ
- GetMaxはO(1)だが他の操作はO(木の高さ)
- 木は出来る限り浅くしたい
どうやって木を浅くするか?
Complete binary tree の定義は最後の深さ以外のノードが全て埋まっており、最後の深さのノードは左から順に埋まっていることである。
Complete binary tree の例:
Complete binary tree ではない例:
n個のノードを持つcomplete binary treeの深さは最大で
complete binary treeのメリットととして以下のように配列で表現できる。
complete binary tree をキープしておくために
- 新しい要素をInsertするときは最後の深さで左から順に挿入する
- ExtractMaxするときはルートノードと最後の葉と入れ替える
Complete Binary Tree まとめ
- すべての操作がO(log n)で動作して高速である(GetMaxはO(1))
- 配列で保持しておけるのでメモリ空間の効率がよい
- 実装が簡単
Heap Sort
Heap Sortのやり方
- ヒープ構造を作る
- ExstraMax()を繰り返す
ヒープ構造の作り方
- 下から上に向かっていくようにヒープ構造を修正していく
- 最初は深さ1のサブツリーから修正していき、ルートまでたどり着いたときにすべてのサブツリーに対してヒープ構造が保たれている
- 参考URL:Heap Sort Visualization
- SiftDownをO(n)ノードに行うため計算量はO(nlog n)
- ノードが葉に近ければShifDownは高速に行える
ヒープソートまとめ
- PriorityQueueは主にInsertとExtractMaxという操作を持つ
- リストと配列による実装は片方の操作はとても高速(O(1))だがもう片方の操作はとても遅い(O(n))
- バイナリーヒープによる実装は両方の操作がO(log n)で行え、かつメモリスペース的にも効率がよい
記事が長くなってしまったのでDisjoint Setに関する内容は別記事にします。
追記:練習がてらにpythonでヒープソートを行うコードを書いてみました。
import numpy as np import random class HeapBuilder(object): def __init__(self, array_length): self._heap = np.random.permutation(np.arange(1,array_length+1)) self.size = len(self._heap) def _parent(self, i): return (i - 1) // 2 def _leftChild(self, i): return 2 * i + 1 def _rightChild(self, i): return 2 * i + 2 def _swap(self, i, j): temp = self._heap[i] self._heap[i] = self._heap[j] self._heap[j] = temp def _siftUp(self, i): while (i > 0) and (self._heap[self._parent(i)] < self._heap[i]): self._swap(i, self._parent(i)) i = self._parent(i) def _siftDown(self, i, size): maxindex = i l = self._leftChild(i) if (l < size) and (self._heap[l] > self._heap[maxindex]): maxindex = l r = self._rightChild(i) if (r < size) and (self._heap[r] > self._heap[maxindex]): maxindex = r if i != maxindex: self._swap(i, maxindex) self._siftDown(maxindex, size) def buildHeap(self): for i in reversed(range(0, self._parent(self.size))): self._siftDown(i, self.size) def heapSort(self): self.buildHeap() n = self.size for _ in range(self.size): self._swap(0, n - 1) n -= 1 self._siftDown(0, n) def showHeap(self): print (self._heap) if __name__ == '__main__': heap = HeapBuilder(1000) heap.showHeap() heap.heapSort() heap.showHeap()
海外では「技術面接の突破法」なんて授業がある
最近Rui Ueyamaさんのturingcomplete.fmを聞いて初めて知ったんですが海外の大学では「技術面接の突破法」なんて授業があるんですね。 技術面接っていうのはいわゆるプログラミングなどコーディング面接です。 13. 自作アセンブラ、リンカの最適化、トリッキーなビット操作の楽しさ、外資系IT企業のコーディング面接対策 (hikalium)
以下はスタンフォード大学の授業のページです。スライドもすべて公開されています。 CS9: Problem-Solving for the CS Technical Interview
日本の大学ではこんなことまず教えないですよね。 いかに英語と日本語で情報格差があるかを実感させられます。
資料を軽く読んでみたので簡単に内容をまとめてみました。
履歴書について
履歴書の書き方の原則
- 自分がやったことをすべてリストアップするな。戦略的に優先順位を付けて書くべし
- 内容に嘘は書かず正直に書け
- 履歴書に書いたことはすべて話せるように準備しておこう
- 専門家であれ。あなたの履歴書は誰が読むかわからない
履歴書クイックチェック
自分の履歴書に以下の内容が入っているか確認しましょう。
- 名前と連絡先
- 目的(必要であれば)
- 学歴
- 職歴
- 過去のプロジェクト(あれば)
- スキルとプログラミング言語
以下詳細
名前と連絡先
以下のものは正確、かつ最新のものに
- 名前
- メールアドレス(へんな名前のメールアドレスは使わないように)
- 電話番号
- 住所
目的
履歴書に目的を書くことで職探しをする上であなたが何を気にするかを伝えることができる。 例えば、下記のような例がある。
- 「ソフトウェアエンジニアのサマーインターンシップを探しています」
- 「目的:大きな影響と成長の機会があるフロントエンドエンジニアのポジション」
- 「人々の生活に幸せをもたらすデザインと開発の経験」
目的は必須ではないが戦略的に使えば非常に有効である。
学歴
- 卒業大学、専攻など
- GPAが良ければ(一般的に3.5+以上)載せましょう
- 関連した専攻あれば最も重要なものの概要を載せてよい
- 高校に関しては面接で聞いてほしいことがある場合のみ書いても良い
職歴
あなたが過去に携わった仕事の概要を以下の情報とともに記載
- 会社の名前と場所
- 働いていた期間
- 仕事の名前
その後にあなたが仕事で達成したことを書く
業績について
特定の動詞を使うとよい。 "worked"や"programmed"といった動詞より"Designed", "implemented", "prototyped", "tested", "deployed", "maintained"のような動詞がよい。
- 業績は可能ならば定量的に
- 技術面接であればそこで使った技術の概要を簡潔に含めるとよい
- 簡潔に書くべし。少ない文で書くことが難しければ重要なポイントをピックアップしてみる
最初の仕事の応募の場合
最初の仕事の応募である場合は職歴は必要ない。 以下のようなことを書いてもよい。
- 他の分野で行ってきた仕事
- クラブや組織でのリーダー経験
- いままでやってきた個人的なプロジェクト(あれば)
極端に言えばあんたが「賢く」て「懸命に働く」ことが伝わればよい。
ちなみに、講義スライドでは「スタンフォード大学の学歴は非常に強い。同じ大学内の人と争う必要はない」とも言っている(笑)
過去のプロジェクト
個人的なプロジェクトを行っていればそれも書くことができる。 なくても心配しなくてOK! もし書くなら以下の情報を載せる。
- プロジェクト名
- 誰と一緒にやったか
- プロジェクトの内容
- あなたが特にやったこと
- 可能であればプロジェクトのURL
プログラミング言語とスキル
あなたが使いこなせるプログラミング言語と技術を書く。 リストアップする際の注意点
- あなたが履歴書で上げたプログラミング言語について面接で聞かれる可能性がある
- 経験したすべての言語を書くのではなくあなたが本当に使いこなせる言語を書くべし
- 「慣れている」や「いくつかの経験がある」といった書き方でもよい
履歴所については以上のような感じです。 他にもコーディング面接に関する講義資料もあったので気が向いたときに別途記事に したいと思います。
Dynamic Array (Cousera Data Structures week 2)
前回の記事に引き続き、CouseraのData Structuresコースのweek2講義のメモです www.coursera.org
前回のweek1の内容の記事はこちら
Dynamic Arrays
通常の静的な配列と異なり、Dynamic Arrayは後から配列のサイズを増やすことができる。 Dynamaic Arrayは以下の操作を持つデータ構造である。
- Get(i):インデックスiの要素を返す
- Set(i, val):インデックスiの場所にvalをセット
- PushBack(val):valを配列の末尾にセット
- Remove(i):インデックスiの要素を削除する
- Size():要素の合計数を返す
Dynamic ArrayはC++ではvector, JavaではArrayList, pythonではlistなどで実装されている。
配列にpushbackを繰り返してサイズが一杯になった場合、新たに現在の配列のサイズの2倍のサイズの新しい空間をメモリに確保する。 そして、現在の配列に入っている要素を新しい配列にコピーし、現在の配列をメモリから開放してから新しい配列にpushbackしていく。
各操作のオーダーは以下の通り。
Dynamic Arrayまとめ
- 静的な配列と異なり、Dynamic Arrayはサイズが変更できる
- 新しい要素の追加は基本的に定数時間だが、配列のリサイズが伴う場合はO(n)
- 確保したメモリ空間が無駄になることがある
Amortized Analysis
Amortized Analysisは償却解析、ならし解析とも呼ばれ、一回の実行で毎回最悪時間計算量を見積もるのではなく、 一連の操作でどのくらいの計算量になるかを解析する手法である。 例えば、上のDynamic Arrayの要素追加において時間計算量は基本O(1)だがリサイズが伴うとO(n)になるという話があった。こういったときに配列に連続して要素を追加していったときにトータルとして計算量がどのくらいになるかというのを見積もる。
ここで操作をn回連続して行ったときのAmortized costというものを導入し、以下のように計算される。
Aggreggate Method
n回の操作の平均を計算量とする手法 以下はDynamic arrayでpushbackを連続して行う例
Banker's Method
参考動画↓
Physicist's Method
- データ構造の状態を表すポテンシャル関数を定義
- ポテンシャル関数は非負であり、初期状態は0とする
- 操作tの償却コストは次のようになる
- n回の操作のコストは
- 償却コストの合計は次のようになる
Basic Data Structure (Cousera Data Structures week 1)
久しぶりのブログ更新になります。やはり仕事が忙しいなかなか勉強の時間がとれませんね。。
さて今回からcouseraのdata structures コースをやって行きたいと思います。
やはりソフトウェアエンジニアを目指すならデータ構造の知識は必須ですよね。ということで、今後から備忘録も兼ねてdata structureコースの各週の内容のサマリを書いていきたいと思います。
Week 1 Basic Data Structures
Arrays
- Array(配列)は等しいサイズの要素で構成されているメモリ上の連続した空間である
- 各要素は連続した整数でインデックスされている
- 各要素へのアクセスは定数オーダーの時間で行える
- 配列の最後への要素の追加、削除は定数オーダー時間
- 任意の場所の追加、削除は線形オーダー時間 (O(n))
Singly-Linked List
SIngly-Linked List(単方向リスト)は各要素は値となるkeyと次の要素のアドレスを示すポインタをもっている。 単方向リストに対する操作は以下のようなものがあげられる。
各操作のオーダーは以下のようになる。
ポイントはリストの頭に対する操作はO(n)の時間でできるがリストに末尾に対する操作はO(n)であること(リストの先頭から辿っていく必要があるから)。 ただし、末尾のアドレスをもつtailがあればpushbackとtopbackはO(1)でできる。
Doubly-Linked List
Doubly-Linked List(双方向リスト)の各要素は値を保持しているkeyと前後の要素のポイントを持っている。
双方向リストに対する各操作のオーダーは以下のようになる。
ポイントは単方向リストと違い、前の要素へのポイントをもっているためpopback()とAddBefore(Node, key)のオーダーがO(1)になっていること。
リストまとめ
- リストの先頭要素の挿入と削除はO(1)
- 末尾のアドレスを保持していて双方向リストである場合、末尾の要素の挿入と削除はO(1)
- 要素の検索はO(n)
- リストの要素はメモリ上で連続的である必要はない
- 双方向リストである場合、ある要素の前後の挿入、削除はO(1)
Stack
Stackは以下の操作を行うデータ構造である
- Push(key):スタックに新しいキーを追加する
- Key Top():直近のキーを返す
- Key Pop():直近のキーをスタックから削除して返す
- Boolean Empty();スタックに要素が存在するか
スタックはいわゆるLIFO(Last In Fast Out)のデータ構造であり、スタックは配列やリストで実装できる。スタックに対する操作はO(1)である。
Queue
Queueは以下の操作を行うデータ構造である。
- Enqueue(Key):キューにキーを追加する
- Key Dequeue():最後に追加されたキーを削除して返す
- Boolean Empty():キューに要素が存在するか
Queueはtailを持ったリスト、もしくは配列で実装できる。 Queueに対する操作はO(1)である。
Tree
木構造は空、もしくはキーと子のリストを持つ要素で構成されるデータ構造である。 特に二分木の場合、ノードはkeyとleft, rightを持つ。
木構造の探索方法は主に以下の2つ。
- Depth-first
- 他のサブツリーを探索する前に一つのサブツリーを完全に探索する
- Breadth-first
- 次の階層に行く前にある一階層のノードをすべて探索する。
Depth-firstにはさらに3つの探索方法がある。
- InOrderTraversal(tree)
- InOrderTraversal(tree.left)
- print(tree.key)
- In OrderTraversal(tree.right)
- PreOrderTraversal(tree)
- print(tree.key)
- PreOrderTraversal(tree.left)
- PreOrderTraversal(tree.right)
- PostOrderTraversal(tree)
- PostOrderTraversal(tree.left)
- PostOrderTraversal(tree.right)
- print(tree.key)
Breadth-firstはキューを用いて実装できる。
木構造まとめ
ubuntu14.04にGTX1080のドライバとCUDA8.0を入れてChainerを動かすまでの最速手順
もうかれこれ何回もこのセットアップ作業を行っているので手順を記しておく。
Ubuntu14.04のインストール
インストールディスクから普通にインストール。
このあとにドライバやcudaのインストールを行っていく際にGUIから離れて黒画面でコマンド操作をしていく工程がある。
しかし,グラボの関係で黒画面にはいった際に文字が表示されない問題があるので以下の記事のコマンドで解消しておく。
rikeiin.hatenablog.com
sudo sed -i -e 's/#GRUB_TERMINAL/GRUB_TERMINAL/g' /etc/default/grub sudo update-grub sudo reboot
GTX1080のドライバのインストール
NVIDIAドライバダウンロード
から自分の環境にあったドライバをダウンロードする。
ドライバをインストールする前にX-windowを殺してから作業を行う。まず「Ctrl+alt+F1」でttyに入る。
インストールは以下のコマンドで。
sudo service lightdm stop chmod +x NVIDIA-Linux-x86_64-375.20.run sudo sh NVIDIA-Linux-x86_64-375.20.run
あとは流れにそってインストールすればOK。
終わったら念のため再起動
CUDA8.0のインストール
CUDA Toolkit | NVIDIA Developer
上のリンクからCUDA8.0をダウンロードする。
自分は Linux -> x86_64 -> Ubuntu -> 14.04 -> runfile(local)
を選択した。
~/.bashrcに以下のPathを通しておく。
export PATH=/usr/local/cuda-8.0/bin${PATH:+:${PATH}} export LD_LIBRARY_PATH=/usr/local/cuda-8.0/lib64${LD_LIBRARY_PATH:+:${LD_LIBRARY_PATH}} export CUDA_HOME=/usr/local/cuda
ドライバのときと同様にXを殺してからからインストールする。
sudo service lightdm stop chmod +x cuda8.0.44_linux.run sudo sh cuda8.0.44_linux.run
あとは流れにそってインストール。終わったら念のために再起動。
コンソールで
nvidia-smi
が成功すればインストールは成功。
cudnnのダウンロード
以下の記事のやり方で。
CUDA 8.0 RCをUbuntu 16.04 LTS + GTX1080にインストール - Qiita
Chainerのインストール
以下の記事にあるような方法でpythonの仮想環境などを構築しておく。
データサイエンティストを目指す人のpython環境構築 2016 - Qiita
Chainerのインストールにはg++のようなC++コンパイラが必要なので以下のコマンドでインストール。
apt-get install g++
あとはpipでインストールするだけ。
pip install chainer
import chainer import cupy import cupy.cudnn
でエラーがでなければインストール成功!
Windows環境のTeXstudio設定メモ
TeXエディタであるTeXstudioを使うときに初期設定だと日本語環境でコンパイルがうまく行かなかったのでメモ
設定方法は上のリンクに書いてあるが、それでもうまく日本語を含むTeXファイルをコンパイルできなかった。
いろいろ調べたところ、
まず、メニューバーからオプション⇒TeXstudioの設定を開く
コマンドタブより以下を設定
DviPdf : dvipdfmx -f ptex-ipaex.map %.dvi
これで日本語環境でもコンパイルできるようになる。
2016/12/12 追記:
以上の設定だと
Couldn't open font map file "ptex-ipaex.map"
という警告がでた。このままだとフォントが正しく埋め込まれないようなので,
- DviPdf:dvipdfmx.exe %.dvi
という設定で正しくコンパイルできた。