ソフトウェアエンジニアを目指す人のブログ

ソフトウェアエンジニアになるために勉強したことを書いていきます

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アドレスのみをリストに保存する。
このとき、アクセス順にリストにつなげていく。

f:id:rikeiin:20180503183048p:plain

  • nは一定期間にアクセスがあったIPアドレスの数
  • メモリ消費量は\Theta (n)
  • L.Append, L.Top, L.Popは\Theta (1)
  • L.Find, L.Eraseは\Theta (n)
  • UpdateAccessListは\Theta (n)
  • AccessedLastHourは\Theta (n)

Hash Functions

ハッシュ関数の定義

あるオブジェクトの集合\mathcal Sm>0となる整数があるとき、関数h: \mathcal S \rightarrow \{0, 1,\dots, m-1\}ハッシュ関数と呼ぶ。

このとき、mハッシュ関数hの基数(cardinality)と呼ぶ。

ハッシュ関数の望ましい要件

  • hの計算が早い
  • 異なるオブジェクトには異なる値
  • メモリ使用量がO(m)でマップできる
  • 基数mは小さくしたい
  • もしオブジェクトの数|\mathcal S|mより大きいとき、すべてを異なる値にマップすることは不可能である

Collisions

h(o_1)=h(o_2)かつo_1\neq o_2のとき、これを衝突(collision)と呼ぶ。

Chaining

Map

マップはあるオブジェクトからあるオブジェクトへのマッピングを行う。
例えば、以下のような例がある。

  • ファイル名→ディスク上のファイルの場所
  • 学生ID→学生名
  • 契約名→契約電話番号

\mathcal Sから\mathcal VへのマップはHashKey(O), Get(O), Set(O, v)の操作を持つデータ構造である。このとき、O\in S, v \in V

Chaining

f:id:rikeiin:20180505224216p:plain

マップに関する各操作の疑似コードを以下に示す。

f:id:rikeiin:20180505225558p:plain
f:id:rikeiin:20180505225620p:plain
f:id:rikeiin:20180505225641p:plain

  • Aの最大のチェインの長さをcとすると、HashKey, Get, Setの時間計算量は\Theta(c+1)
    • c=0のときO(1)
  • nを現在のマップの異なるキーOの数、mハッシュ関数の基数とするとメモリの消費量は\Theta(n+m)

Hash Tables

Set

SetはAdd(O), Remove(O), Find(O)の操作を持つデータ構造である。
chainingを使ったSetの実装方法は二通りある。
f:id:rikeiin:20180505233025p:plain

  • SetはSからV=\{true, false\}へのマップと等しい
  • (O, v)のペアを保存する代わりにOのみを保存する

Setに対する各操作の疑似コードを以下に示す。

f:id:rikeiin:20180505233025p:plain
f:id:rikeiin:20180505233046p:plain
f:id:rikeiin:20180505233204p:plain

SetもしくはMapを用いたhashingの実装をHash tableと呼ぶ。

プログラミング言語では以下のようなクラスに実装されている。

まとめ

  • Chainingはhash tableを実装するためのテクニックのひとつである
  • メモリ消費量はO(n+m)
  • 各操作の時間計算量はO(c+1)
  • どのように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が所属する最小の要素の値を入れる

f:id:rikeiin:20180428215229p:plain
f:id:rikeiin:20180428215301p:plain
f:id:rikeiin:20180428215438p:plain

効率的な実装

  • 単純な実装のボトルネックはUnion操作である。
  • Linked listを使うことでより効率的な実装が可能。
    • 集合をLinked listで表し、listの末尾を集合のIDとして使う

f:id:rikeiin:20180428220453p:plain

f:id:rikeiin:20180428220528p:plain

  • メリット
    • Unionの実行時間がO(1)
  • デメリット
    • 末尾を探すためにリストを走査する必要があるため、Findの実行時間がO(1)
    • xのリストの末尾とyのリストの先頭を定数時間で取得できる場合のみUnionの実行時間はO(1)

木構造を用いたさらに効率的な実装

  • 集合を一つの木で表す
  • IDはその木構造のルート
  • parent[1...n]という配列を使う
    • parent[i]はiの親もしくはiがルートであるならばi自身

f:id:rikeiin:20180428223100p:plain
f:id:rikeiin:20180428223204p:plain

  • どのように2つの木をマージさせるか?
  • 片方の木をもう片方のルートノードの下にぶら下げる
    • 木を浅くしておくため、短い木をぶら下げる

f:id:rikeiin:20180428225415p:plain

  • 木の高さを素早く見つけるために各サブツリーの高さを配列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もルートノードも同時にわかるので以下の様に木を変形できる。

f:id:rikeiin:20180428232818p:plain

O(log n)の操作をn回繰り返すときの計算量をlog*nと定義する。
f:id:rikeiin:20180430161203p:plain

f:id:rikeiin:20180430161247p:plain

つまり一回の操作の時間計算量は漸近的に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():優先度が最大の要素を取り出す

オプションで以下の操作を定義することもある

  • Remove(it):イテレータitでポイントされた要素を削除する
  • GetMax():要素のセットは変えずに優先度が最大の要素を返す
  • ChangePriority(it, p):イテレータitでポイントされた要素の優先度をpに変える

単純な実装

ソートされていない配列・リスト

f:id:rikeiin:20180415135651p:plain

  • Insert(e)
    • 要素eを末尾に追加する
    • 実行時間はO(1)
  • ExtractMax()
    • 配列・リストを走査する
    • 実行時間はO(n)

ソートされた配列

f:id:rikeiin:20180415140333p:plain

  • ExtractMax()
    • 最後の要素を取り出す
    • 実行時間はO(1)
  • Insert(e)
    • 要素eの場所を探す(二分探索でO(log n))、右の要素を一つずつづらし(O(n))、挿入する(O(1))
    • 実行時間:O(n)

ソートされたリスト

f:id:rikeiin:20180415141534p:plain

  • ExtractMax()
    • 最後の要素を取り出す
    • 実行時間:O(1)
  • Insert(e)
    • 要素eの場所を探し(二分探索が使えないため、O(n))、挿入(O(1))
    • 実行時間:O(n)

実行時間まとめ

f:id:rikeiin:20180415141825p:plain

Priority Queues: Binary Heaps(バイナリーヒープ)

Binary max-heapの定義は子より親のほうが値が大きい場合の二分木である。
以下がヒープである例
f:id:rikeiin:20180415142706p:plain

ヒープではない例
f:id:rikeiin:20180415142741p:plain

基本的なヒープに対する操作

GetMax

f:id:rikeiin:20180415142940p:plain

Insert

新しい要素を木の末端の葉にくっつける。
f:id:rikeiin:20180415143357p:plain

この操作において子より親の値が大きくなればならないという条件を満たしていな場合、以下のSiftUpという操作を条件が満たすまで行う。

SiftUp

シフトアップは子の大きい値と親の小さい値を入れ替えるという操作であり、木がヒープの条件を満たすまで繰り返す。
実行時間はO(木の高さ)である。

ExtractMax

木の根と葉を入れ替えることで行う。
f:id:rikeiin:20180415144715p:plain

上の木に対してExtractMaxを行うと以下のようになる。
f:id:rikeiin:20180415144819p:plain

当然これはヒープの条件を満たしていないため、以下のSiftDownという操作を行う。

SiftDown

SiftDownは親の小さい値と子の大きいを入れ替えてノードを下にずらす操作である。
上の図の例では12と29を入れ替える。このとき左右の子の大きいほうと入れ替えること。
この操作をヒープの条件を満たすまで繰り返す。
もちろん実行時間はO(木の大きさ)

ChangePriority

任意のノードを任意の値に変える。その後にヒープの条件を満たすようにSiftUpかSiftDownを繰り返す。

Remove

削除したいノードの値を∞にかえる。
f:id:rikeiin:20180415150027p:plain

その後、ヒープの条件を満たすようにSiftUpを繰り返す(最終的に∞が根に来る)。
その後はExtractMaxと同じ操作を行う。
実行時間はO(木の高さ)

ヒープ操作のまとめ

  • GetMaxはO(1)だが他の操作はO(木の高さ)
  • 木は出来る限り浅くしたい

どうやって木を浅くするか?

Complete binary tree の定義は最後の深さ以外のノードが全て埋まっており、最後の深さのノードは左から順に埋まっていることである。

Complete binary tree の例:
f:id:rikeiin:20180417172103p:plain:w500

Complete binary tree ではない例:
f:id:rikeiin:20180417172155p:plain:w500

n個のノードを持つcomplete binary treeの深さは最大でO(log n)
complete binary treeのメリットととして以下のように配列で表現できる。

f:id:rikeiin:20180417174103p:plain:w600

complete binary tree をキープしておくために

  • 新しい要素をInsertするときは最後の深さで左から順に挿入する
  • ExtractMaxするときはルートノードと最後の葉と入れ替える

f:id:rikeiin:20180417174658p:plain:w200

Complete Binary Tree まとめ

  • すべての操作がO(log n)で動作して高速である(GetMaxはO(1))
  • 配列で保持しておけるのでメモリ空間の効率がよい
  • 実装が簡単

Heap Sort

Heap Sortのやり方

  1. ヒープ構造を作る
  2. 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の内容の記事はこちら

rikeiin.hatenablog.com

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していく。

各操作のオーダーは以下の通り。 f:id:rikeiin:20180407173703p:plain

Dynamic Arrayまとめ

  • 静的な配列と異なり、Dynamic Arrayはサイズが変更できる
  • 新しい要素の追加は基本的に定数時間だが、配列のリサイズが伴う場合はO(n)
  • 確保したメモリ空間が無駄になることがある

Amortized Analysis

Amortized Analysisは償却解析、ならし解析とも呼ばれ、一回の実行で毎回最悪時間計算量を見積もるのではなく、 一連の操作でどのくらいの計算量になるかを解析する手法である。 例えば、上のDynamic Arrayの要素追加において時間計算量は基本O(1)だがリサイズが伴うとO(n)になるという話があった。こういったときに配列に連続して要素を追加していったときにトータルとして計算量がどのくらいになるかというのを見積もる。

ここで操作をn回連続して行ったときのAmortized costというものを導入し、以下のように計算される。

\frac{\mathrm{Cost(}n \mathrm{\ operations)}}{n}

Aggreggate Method

n回の操作の平均を計算量とする手法 以下はDynamic arrayでpushbackを連続して行う例 f:id:rikeiin:20180410194129p:plain

Banker's Method

  • コストの低い操作にチャージを掛け、トークンとしてデータ構造に保存する。
  • コストの高い操作にトークンを使用する

参考動画↓

Amortized Analysis - YouTube

f:id:rikeiin:20180410195619p:plain

Physicist's Method

  • データ構造の状態を表すポテンシャル関数\Phiを定義
  • ポテンシャル関数は非負であり、初期状態は0とする
  • 操作tの償却コストは次のようになる
    • c_t + \Phi(h_t) - \Phi(h_{t-1})
  • n回の操作のコストは \sum_{i=1}^n(c_i)
    • 償却コストの合計は次のようになる

f:id:rikeiin:20180410205623p:plain

f:id:rikeiin:20180410205848p:plain

f:id:rikeiin:20180410205913p:plain

Basic Data Structure (Cousera Data Structures week 1)

久しぶりのブログ更新になります。やはり仕事が忙しいなかなか勉強の時間がとれませんね。。

さて今回からcouseraのdata structures コースをやって行きたいと思います。

www.coursera.org

やはりソフトウェアエンジニアを目指すならデータ構造の知識は必須ですよね。ということで、今後から備忘録も兼ねてdata structureコースの各週の内容のサマリを書いていきたいと思います。

Week 1 Basic Data Structures

Arrays

  • Array(配列)は等しいサイズの要素で構成されているメモリ上の連続した空間である
    • 各要素は連続した整数でインデックスされている
  • 各要素へのアクセスは定数オーダーの時間で行える
  • 配列の最後への要素の追加、削除は定数オーダー時間
  • 任意の場所の追加、削除は線形オーダー時間 (O(n))

Singly-Linked List

f:id:rikeiin:20180402000221p:plain

SIngly-Linked List(単方向リスト)は各要素は値となるkeyと次の要素のアドレスを示すポインタをもっている。 単方向リストに対する操作は以下のようなものがあげられる。

f:id:rikeiin:20180402000734p:plain

各操作のオーダーは以下のようになる。

f:id:rikeiin:20180402001120p:plain

ポイントはリストの頭に対する操作はO(n)の時間でできるがリストに末尾に対する操作はO(n)であること(リストの先頭から辿っていく必要があるから)。 ただし、末尾のアドレスをもつtailがあればpushbackとtopbackはO(1)でできる。

Doubly-Linked List

f:id:rikeiin:20180402001627p:plain

Doubly-Linked List(双方向リスト)の各要素は値を保持しているkeyと前後の要素のポイントを持っている。

双方向リストに対する各操作のオーダーは以下のようになる。 f:id:rikeiin:20180402002047p:plain

ポイントは単方向リストと違い、前の要素へのポイントをもっているため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はキューを用いて実装できる。 f:id:rikeiin:20180402181818p:plain

木構造まとめ

  • 木構造はキーと子を持つ
  • 木の探索方法はDFS(pre-order, in-order, post-order)とBFSがある
  • 木の探索は一般的に再帰的なアルゴリズムで実装される。