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
という設定で正しくコンパイルできた。
【感想・書評】世界でもっとも強力な9のアルゴリズム
今日、至る所にコンピュータが浸透し、また私達自身もスマホという名にコンピュータを日常的に使っている。そして、我々は何気につかっているコンピュータやインターネットでどのようなアルゴリズムが動いているかを全く意識せずに使うことができる。
今回紹介するこの「世界でもっとも強力な9のアルゴリズム」という本は、私達が全く意識せずに使っているが、世界に多大なる影響を与えたアルゴリズムを非常にわかりやすく、情報系の勉強をしていない人でも理解できるように説明してくれている。
この本では無数にあるアルゴリズムの中でも9つに絞って説明しているが、その選定基準は、①普通のコンピュータユーザが毎日使っている②現実世界の具体的な問題を解決うするアルゴリズムであること③主としてコンピュータ科学理論に関係するアルゴリズムであること、である。
紹介されているアルゴリズムを挙げると以下の9つである。
この中でも特に目からウロコだったのは公開鍵暗号法とデジタル署名の説明だった。この２つのアルゴリズムは情報系の大学生ならセキュリティの授業で習うと思うが、私はこの２つのアルゴリズムが何回説明されてもいまいちピンと来なかった。しかしこの本では「絵の具を混合する」という誰でもわかる例を使って説明してくれるので雷が落ちたような気分になった。いままで大学の授業で「巨大な素数どうしの因数分解は困難だから〜」のような説明ばかりされていたからである。
というわけで、この本を読むだけで情報系の大学生がならうことの大部分を理解できてしまった。この本は情報系ではない一般の人だけでなく、情報工学を学んでいる大学生にもオススメできる。
野村総合研究所選考体験記(2017卒)
3月15日 NRI career cafe
このイベントは座談会形式の説明会でした。小さな会議室に就活生は25人ほど集められ、社員の方は司会含めて7人いました。
まず最初に簡単な会社説明と社員の自己紹介をスライドを使って30分ほど説明がありました。
NRIの事業は主に経営コンサルとITソリューションに分かれますがこのイベントに来ていた社員は全員ITソリューションの方でした。だいたい入社して5、6年の方が多いように感じました。
説明の後はグループに分かれて社員さんを囲んでざっくばらんに質問する、といった形式です。一回が20分で区切られており、それを3回行いました。
それが終わったあとはアンケートを記入して終わりです。
ゴールドマン・サックス選考体験記(2017卒)
ゴールドマン・サックスは言わずと知れた外資系投資銀行の一つですね。ここは部門別選考を行っており、併願もできます。今回私はテクノロジー部門の選考を受けてきました。GSの特徴はトレーディングのシステムから社内のチャットツールまでほぼ全て自分たちで作っているということです。そのため証券会社にひとつのIT企業がまるまる入ってるという感じです。ワークショップに行ったときも「GSにはWe build」の精神があると言っていました。
4/16（土）
9:00-13:00
場所は六本木ヒルズ本社。
テスト40分。論理的思考力やアルゴリズムの理解を問う問題。４問中２問回答する形式。
1:1の面接を30分×３回
一人目：日本人と。主にテストに内容について聞かれる。なぜその問題を選んだのか。なぜそのよに考えたか。もっと良い方法はないか。逆質問。
二人目：外国人と英語で面接。主に研究、プログラミング経験を聞かれた。研究内容の説明。研究でどういうプログラムを書いているか。チームでのプログラミング経験。どのようなプログラムか紙に書きながら説明。何が難しかったか。好きな言語と理由。最近学んだこと。紙にフィボナッチ数列を出力する関数を書く。逆質問。
三人目：中国人と日本語で面接。研究内容。テクノロジー部の志望理由。サークルではどういう役割か。複数人のチームで意思決定をするとき、あなたがリーダーならどうするか、多数決とか。プレッシャーがある中で成果を出した経験は。ロールプレイング。紙にコインをおいてどのように勝つかのストラテジーを考える。逆質問。
面接官の手の内を知りたい方はこちらの記事もどうぞ。
ソニー選考体験記(2017卒)
技術ジョブマッチング
4/16
品川本社。大量の就活生がいた。広い部屋にブースが作られており、そこで１：１で面談。
ホワイトボードで研究の説明。志望動機。ソニーに入ってなにがやりたいか。最近興味を持っている技術分野。なぜそれに興味があるか。他にどういう会社を見ているか。
かなり和やかな雰囲気でほぼ雑談みたいな感じ。
２週間以内に選考結果を電話かメールで伝えると言われて終了。
