jenkinsとgithubを連携して自動テストをする
web上にいろいろ情報が錯綜していていろいろハマったので成功したやりかたをメモしておく
やりたいこと
- githubに新しいcommitがpushされるごとにそのソースコードをビルドしてテストする
- テスト結果をgithub上から確認できるようにする
github側の設定
- ビルドしたいレポジトリにwebhookを設定する
- settings -> webook
- pyload url
- content type
- application json
- Which events would you like to trigger this webhook?
- "Just the push event." or "Send me everything."
- settings -> webook
- access tokenの設定
- 個人アカウントのsettings -> developer settings -> personal access token
- generate new token
- repoとadmin:repo_hookをチェック
- 個人アカウントのsettings -> developer settings -> personal access token
jenkins側の設定
fastaiのバージョン0.7をインストールする
fastaiという無料でディープラーニングについて学べる講座がありますが、その講義の中でfastaiというライブラリが使われています。 github.com
このライブラリはpytorchのラッパーのような形になっており、実際にディープラーニングをする上でのベストプラクティスが簡単に適用できることが特徴のようです。
実際に最適な学習率の初期値を見つけてくれる関数や[1506.01186] Cyclical Learning Rates for Training Neural Networksのような手法が簡単に使えるようになっています。
fastaiのライブラリは現在v1.0が公開されていますが、講義で使われてものやkaggleのkernelで使われているのはv0.7が多いようでv1を使っているとそのままでは動かないスクリプトが多数あります。 Githubにあるcondaやpipをつかってインストールすると最新版が入ってしますのでv0.7を使いたい場合は別の方法でインストールする必要があります。
fastaiのforumにはcondaの仮想環境を使ってv0.7のインストール方法がありますが、私の場合はどうもエラーが出てうまくいかなかったので別の方法をとりました。
v0.7のコードはfastaiレポジトリの old/fastai
に移されているのでここにpythonのパスを通すことで使うことにします。
まず適当なディレクトリに移動してfastaiのレポジトリからクローンしてきます。
cd /tmp/ git clone https://github.com/fastai/fastai cd fastai/old/
その後、pythonのスクリプトでパスを通すことでimport できるようになります。
import sys sys.path.append("/tmp/fastai/old") # on windows use \'s instead import fastai
fastaiは裏でpytorchやtorchvisionを呼び出しているので別途インストールしておいてださい。
conda install pytorch torchvision cuda92 -c pytorch
Hash Tables (Cousera Data Structure Week 4)
CouseraのData Strucureコースのweek4の内容です。
www.coursera.org
前回のweek3の内容の記事はこちら
rikeiin.hatenablog.com
Week4の内容はHash Tablesです。
Hashingの応用例
IP Addresses
あるWebサーバにアクセスしてきた各IPアドレスが過去一定期間にアクセスがあったか判定するという問題を考える。
単純に配列を使った実装の場合、考えうるIPアドレス数の長さの配列を用意し、該当するIPアドレスに対応するインデックスの要素をインクリメントする方法がある。
このとき、
- アクセスリストを更新する操作は(UpdateAccessList)は一つのログにつきO(1)
- 一定期間にアクセスがあったか判定する操作(AccessedLastHour)はO(1)
- IPv4でも2の32乗のメモリが必要
- IPv6では2の128乗であり、もはやメモリに乗らない
配列を使った実装はメモリを多く消費するため、リストを使った実装を考える。
List-based Mapping
過去一定期間にアクセスしてきたIPアドレスのみをリストに保存する。
このとき、アクセス順にリストにつなげていく。
- nは一定期間にアクセスがあったIPアドレスの数
- メモリ消費量は
- L.Append, L.Top, L.Popは
- L.Find, L.Eraseは
- UpdateAccessListは
- AccessedLastHourは
Hash Functions
ハッシュ関数の望ましい要件
- の計算が早い
- 異なるオブジェクトには異なる値
- メモリ使用量がでマップできる
- 基数は小さくしたい
- もしオブジェクトの数がより大きいとき、すべてを異なる値にマップすることは不可能である
Collisions
かつのとき、これを衝突(collision)と呼ぶ。
Chaining
Map
マップはあるオブジェクトからあるオブジェクトへのマッピングを行う。
例えば、以下のような例がある。
- ファイル名→ディスク上のファイルの場所
- 学生ID→学生名
- 契約名→契約電話番号
からへのマップはHashKey(O), Get(O), Set(O, v)の操作を持つデータ構造である。このとき、
Chaining
マップに関する各操作の疑似コードを以下に示す。
- の最大のチェインの長さをとすると、HashKey, Get, Setの時間計算量は
- のとき
- を現在のマップの異なるキーの数、をハッシュ関数の基数とするとメモリの消費量は
Hash Tables
Set
SetはAdd(O), Remove(O), Find(O)の操作を持つデータ構造である。
chainingを使ったSetの実装方法は二通りある。
- Setはからへのマップと等しい
- のペアを保存する代わりにのみを保存する
Setに対する各操作の疑似コードを以下に示す。
SetもしくはMapを用いたhashingの実装をHash tableと呼ぶ。
各プログラミング言語では以下のようなクラスに実装されている。
まとめ
- Chainingはhash tableを実装するためのテクニックのひとつである
- メモリ消費量は
- 各操作の時間計算量は
- どのようにmとcの両方を小さくするか?
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回の操作のコストは
- 償却コストの合計は次のようになる