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

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

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がある
  • 木の探索は一般的に再帰的なアルゴリズムで実装される。

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

python

import chainer
import cupy
import cupy.cudnn

でエラーがでなければインストール成功!

Windows環境のTeXstudio設定メモ

TeXエディタであるTeXstudioを使うときに初期設定だと日本語環境でコンパイルがうまく行かなかったのでメモ

TeXstudio/設定 - TeX Wiki

設定方法は上のリンクに書いてあるが、それでもうまく日本語を含むTeXファイルをコンパイルできなかった。

いろいろ調べたところ、

まず、メニューバーからオプション⇒TeXstudioの設定を開く

コマンドタブより以下を設定

DviPdf : dvipdfmx -f ptex-ipaex.map %.dvi

これで日本語環境でもコンパイルできるようになる。

2016/12/12 追記:

以上の設定だと

texコンパイルの際に

Couldn't open font map file "ptex-ipaex.map"

という警告がでた。このままだとフォントが正しく埋め込まれないようなので,

  • DviPdf:dvipdfmx.exe %.dvi

という設定で正しくコンパイルできた。

 

【感想・書評】世界でもっとも強力な9のアルゴリズム

今日、至る所にコンピュータが浸透し、また私達自身もスマホという名にコンピュータを日常的に使っている。そして、我々は何気につかっているコンピュータやインターネットでどのようなアルゴリズムが動いているかを全く意識せずに使うことができる。

今回紹介するこの「世界でもっとも強力な9のアルゴリズム」という本は、私達が全く意識せずに使っているが、世界に多大なる影響を与えたアルゴリズムを非常にわかりやすく、情報系の勉強をしていない人でも理解できるように説明してくれている。

この本では無数にあるアルゴリズムの中でも9つに絞って説明しているが、その選定基準は、①普通のコンピュータユーザが毎日使っている②現実世界の具体的な問題を解決うするアルゴリズムであること③主としてコンピュータ科学理論に関係するアルゴリズムであること、である。

紹介されているアルゴリズムを挙げると以下の9つである。

  1. 検索エンジンのインデキシング
  2. ページランク
  3. 公開鍵暗号
  4. 誤り訂正符号
  5. パターン認識
  6. データ圧縮
  7. データベース
  8. デジタル署名
  9. 決定不能性

この中でも特に目からウロコだったのは公開鍵暗号法とデジタル署名の説明だった。この2つのアルゴリズムは情報系の大学生ならセキュリティの授業で習うと思うが、私はこの2つのアルゴリズムが何回説明されてもいまいちピンと来なかった。しかしこの本では「絵の具を混合する」という誰でもわかる例を使って説明してくれるので雷が落ちたような気分になった。いままで大学の授業で「巨大な素数どうしの因数分解は困難だから〜」のような説明ばかりされていたからである。

というわけで、この本を読むだけで情報系の大学生がならうことの大部分を理解できてしまった。この本は情報系ではない一般の人だけでなく、情報工学を学んでいる大学生にもオススメできる。

 

世界でもっとも強力な9のアルゴリズム

世界でもっとも強力な9のアルゴリズム