Scrapbox: みんなのコンピュータサイエンス(Computer Science Distilled)

みんなのコンピュータサイエンス

Chapter 1: 基礎

以下について

• 解決案
• 論理
• カウント
• 確率

1.1 解決案

• 脳の作業領域は限られているので、まず手間のかかるタスクの場合は全てのことを書き出すことから。その上で整理する。
• 人のレベルでの整理のため、フローチャートや疑似コードに起こす
  • フローチャートの可読性を高めるために、ガイドラインは守ること
  • 疑似コードは、プログラム言語に近い形で書く。ただあくまで人の理解のため
• モデルは対象の問題と特性を表現する概念から構成
  • 問題を十分に理解し、操ることを可能にする
• 数理モデルは数学的に表現されたモデルで、コンピュータの領域に順応できる
  • グラフを有する数理モデル->グラフ理論を使う
  • 方程式を有する数理モデル->代数学を使う
• コンピュータサイエンスを扱う上で、2次方程式は特に重要なので熟知しておくべき
  • 2次方程式時間の節約に有効で多くの問題を素早く解くのに役立つ

メモ

• 実装前にフローチャートや疑似コードを使いながら整理するのはいいと思いつつ、なかなか実践できていないな。ただ脳内メモリーが溢れている感は結構あるし、ちゃんと意識して継続してみたほうがいいかもしれない
• 2次方程式とか、最近は算数・数学のやり直しをしているからやってはいるがどうも苦手な意識が強い。熟知するまで継続するしかない

1.2 論理

• プログラマは論理多用するけど理解があやふやで、いい加減な使い方していることが多いからちゃんと理解しよう
• 数理理論では変数と演算子は物事の妥当性を表現する
  • 論理式はTrue/Falseの値を表現し、数値の表現ではない
• 対偶は、論理式の否定を取ること
  • 例えば、A -> Bは!B -> !Aになる
  • 全ての条件式で対偶が成り立つ
• 双条件式は、A <-> Bで、A -> BかつB -> Aが成り立つ
• 論理積(AND)は、A && Bで、AかつBが成り立つ
• 論理和(OR)は、A || Bで、AまたはBが成り立つし、両方も成り立つ
• 排他的論理和(XOR)は、A ^ Bで、AまたはBが成り立つが、両方は成り立たない
• ブール代数
  • 結合則
  • 分配則
  • ド・モルガンの法則
    • !A && !B = !(A || B)
    • !A || !B = !(A && B)
• 真理値表で論理式の真偽を確認することができるが、変数がふえるたびに指数関数的に増えるので、大きな論理式の場合は計算量が膨大になる
  • 30個の変数で真理値表は10^9行(=10億以上)になる
• 論理変数は2進数の数値で表現できるため、コンピュータでも扱える
• コンピュータでは論理ゲートを使い電流に対して論理演算を実行する
  • AND, OR, NOT, XORなど
  • これらの論理ゲートを組み合わせて複雑な論理演算を実行する
• コンピュータの高速処理を駆使するため、数値問題を2進数と論理式に変換する。ブール代数は式を単純にし、回路を単純にする
• 現代のCPUの動作原理もブール代数に依っており、情報の電流を操作する無数の超小型の電線と論理ゲートから構成される回路から成っている

メモ

• 論理とかそのあたりはX(Twitter)で結構見かけるけど、「めんどくさいこと言ってんな」と思うことも多々あるな
• ド・モルガンの法則は高校数学のやり直しの中でも出てくるけど、高校時代にやった記憶がないんだよな...(ダメ文系)
• 論理ゲートの話は、コンピュータの仕組みとかまったく知らなかったときはそこまで単純化されているのかと驚いた記憶。小さく小さく分解し、複雑なものも作れるんだなと。ただコンピュータシステムの理論と実装 ―モダンなコンピュータの作り方はちとしんどい...

1.3 カウント

• カウントと論理は離散数学と呼ばれるコンピュータサイエンスの重要分野に属する
• カウントのツール: 乗算・順列・組合せ・総和
• 乗算: 2つの集合の要素数を掛け合わせる(n x m)
• 順列: 順番を考慮した組み合わせ(n!)
  • 階乗は爆発的で、nが小さい値でも非常に大きな数を生み出す
• 組合せ: 順番を考慮しない組み合わせ(nCm)
  • nCm = n! / (m! * (n-m)!)
  • 順番を考慮しない = 順列から重複を除いたもの
• 総和: ある数列の全ての要素を足し合わせる
  • 総和の公式: n(n+1)/2
  • 等差数列の総和: n(n+1)/2

メモ

• このあたりは今やっている高校数学とかの中でもしっかりやってる。ただまあ結構忘れるし、継続して復習しつつ、実際に使いつつで頭に入れていくしかないな

1.4 確率

• 確率P = 事象の数 / 全事象の数
• 独立事象: 1つの事象が他の事象に影響を与えない
  • 2つの独立した事象が発生するのは、個々の確率の積
  • バックアップ問題
    • あるディスクの故障確率1/10億、もう1種類はコスト20%で故障確率1/2000
    • 値段が安いディスク3個使用した場合にデータが失われるのは全て障害が起こった場合 = (1/2000)^3 = 1/8億 < 1/10億で、60%のコストで高価なディスクよりもデータ消失の確率は軽減される
• 排反事象: 2つの事象が同時に発生しない
  • 2つの排反事象の確率の和は1
• 余事象: 事象Aの補集合
  • 余事象の確率は1 - Aの確率

メモ

• 確率も高校数学の中で結構しっかりやっているが、プログラマとしても日常的に使うことはほんとに多いしこの辺りの考え方はしっかりと定着させたい

Chapter 2: 計算量

以下について

• 時間計算量の算出
• Big O記法
• 指数関数的に増加するアルゴリズムの回避
• 空間計算量の算出

2.1 時間計算量の算出

• 最善計算量
  • 同じ大きさの対象が最小の演算数を必要とする場合
  • ソートでは、対象がすでにソートされている場合がこれにあたる e.g) list = [1,2,3,4,5,6,7,8,9]
• 最悪計算量
  • 同じ大きさの対象が最大の演算数を必要とする場合
  • 多くのアルゴリズムにおいて、対象が逆順の場合 e.g) list = [9,8,7,6,5,4,3,2,1]
• 平均計算量
  • 対象がランダムな場合の演算数の平均
  • 一般的には最悪計算量と同じかそれよりも少し小さい
  • 通常、順不同な対象が想定 e.g) list = [3,1,2,4,5,6,7,9,8]
• 最も重要なのは最悪計算量
  • これが大きい場合、対象が大きくなると計算時間が爆発的に増加する
  • なんらかの前提がない場合は最悪計算量を使う
• 計算量の算出には、nに対して最も増加率が高い項があれば良い

メモ

• 計算量の算出はアルゴリズムの理解のために必須な部分という理解はあるが、使う機会もこれまでなかなかなかったし理解がなかなか苦戦している
• 計算量の重要性自体の理解はしているが、自分が実際に使うとなった場合に具体的な算出に苦戦している感じ。これはLeetCodeとか使いつつ実践こなしていくしかない？

2.2 Big O記法

• Big O記法は、計算量の増加率を表現するための記法
  • O(2^n): 成長率の最も高い項が2^n以下の関数
  • O(n^2): 成長率の最も高い項がn^2以下の関数
  • O(n): 成長率の最も高い項がn以下の関数
• 最悪の場合のアルゴリズムのコスト関数の支配項を表現するために使われ、時間計算量の表現として標準的に利用される
• 計算システムを設計するときは、一番頻繁に行われる操作を探し出すことで、それらの操作を行う各種のアルゴリズムのO記法でのコスト比較が可能になる

2.3 指数関数的に増加するアルゴリズムの回避

• 指数関数的に増加するアルゴリズムは、対象が大きくなると計算時間が爆発的に増加する
• 指数関数時間はあまりにも急激に成長するため、「実行不可能」とされる
• 多項式がどれだけ大きな値になっても、指数関数時間のアルゴリズムよりもはるかに効率的
• 指数関数時間のアルゴリズムよりもさらに悪いものが階乗時間のアルゴリズム
  • 階乗時間のアルゴリズムは、n!の計算を行う
  • このアルゴリズムは、nが大きくなると計算時間が爆発的に増加する
  • このアルゴリズムは、実行不可能とされる

2.4 空間計算量の算出

• 空間計算量は、アルゴリズムが実行される際に必要とされるメモリの量
• 演算をどれだけ高速に行えても、コンピュータのメモリの限界を超えるものは実行できない
• 選択ソートの空間計算量はO(1)だが、他の多くのアルゴリズムでは対象の大きさに応じたメモリが必要になる

メモ

• アルゴリズムにおいては、自分は時間計算量に意識が強くいっているが、実際のアルゴリズムの選択においては時間計算量だけでなく空間計算量も考慮した上での選択が必要になる

Chapter 3: 戦略

アルゴリズム設計の戦略について

• 反復処理
• 再帰処理
• 総当たり攻撃
• バックトラック
• 発見的解法
• 分割統治法
• 動的計画法
• 分枝限定法

3.1 反復処理

• 対象の最初から最後まで各要素に対して同じ演算を行うときに最適

3.2 再帰処理

• 再帰処理は、関数が自分自身を呼び出すこと
• 再帰処理を活用するには、自身を単位としてどのように問題を表現するかという創造性が必要
• 再帰アルゴリズムでは、基底ケースと再帰ケースを考慮する必要がある
  • 基底ケース: 再帰処理を終了する条件
  • 再帰ケース: 再帰処理を継続する条件
• 一般的には再帰アルゴリズムのプログラムは反復アルゴリズムのものより単純で短く書ける
• 再帰アルゴリズムは反復より短くかけるが実行時に多くのクローンが生まれ、さらに部分計算結果を保持するため多くのメモリを消費し、さらにCPUサイクルも費やす
• 再帰木を使うことで、視覚的にどれだけ多くの関数が呼び出しを行っているかを確認できる
• 処理速度を最優先でき上げる必要がある場合は、再帰アルゴリズムを単に反復処理に書き直すことでオーバーヘッドを回避できる

3.3 総当たり攻撃

• 問題のアリエル界の候補をすべて検査するアルゴリズム

3.4 バックトラック

• 総当たり攻撃の一種で、分岐を持つ問題で選択した経路が失敗した場合に分岐点まで戻り、別の経路を選択するアルゴリズム
• 解が選択の連続であり、選択を続けると後続の選択肢が制限さえれる問題で一番効果的

3.5 発見的解法(heuristic)

• 最高または最適であることを保証するものではないものの、ある解を導く手法
• 総当たり戦略、バックトラックなどの手法が遅すぎる場合に有効
• 欲張り戦略
  • 各段階で最善の選択しようと試みる。戻ることはしない
  • 欲張りアルゴリズムの基本(例:巡回セールスマン問題)
    • 未訪問のうち最も近いところを訪れる
    • すべての街を訪れるまで繰り返す
• 古典的アルゴリズムの代わりに発見的解法を選ぶのは妥協だが、発見的開放でも最善の解法を導くことができることもある

3.6 分割統治法

• 問題を小さな部分問題に分割し、それぞれを解くことで全体の解を導くアルゴリズム
• どんな難問でも、問題を小分けにしていくことで解決できる

3.7 動的計画法(dynamic programming)

• 動的計画法では、繰り返される部分問題を識別し、1回だけ計算するようにする
• フィボナッチの計算では、計算結果を保存し計算結果がまだ保存されていない時だけ計算することで、計算量を減らすことができる
• キャッシュやメモ化とも呼ばれる

3.8 分枝限定法

• 悪い選択肢を素早く特定し、破棄することで時間を稼ぐアルゴリズム
• 問題に対して解法の上限と下限を用いることで最小限の計算量で最適利得を探し出すことができる
• 分枝限定法の例
  1. 問題を複数の部分問題に分割する
  2. 部分問題の解法の上限と下限を計算する
  3. すべての枝葉の部分問題の限定を比較する
  4. 最も期待できる部分問題で1に戻る

Chapter 4: データ

以下について

• 抽象データ型

• 共同抽象概念

• メモリ上でのデータ構成

• 抽象表現 = 詳細を省略したもので、複雑すぎる物事の機能性を簡単に享受するためのインターフェース

  • ソフトウェアにおいては、手続き呼び出し(関数呼び出し)の下に処理の複雑さを隠す

• コンピュータのプログラムにおいて、データの型は実行する操作に応じて区別される

• すべてのデータ型には特定の手続きの集合が関連づけられており、型に応じて実行できる操作が異なる

4.1 抽象データ型

• 抽象データ型(Abstract Data Type: ADT)は、所定のデータ型に対する操作の集合を定義する仕様に相当し、データの配置や操作の詳細を隠蔽する
• ADTの長所
  • プログラムが単純化され、理解と修正が容易になる
  • 再利用が容易になる
  • 保守が容易になる
  • 利便性が上がる
  • 利用頻度が高く、枯れていてバグが少ない

4.2 共通抽象概念

• 基本データ型(primitive data type)
  • プログラミング言語において標準で準備され、外部モジュール不要で利用できる
  • 整数、浮動小数点数、文字列、真偽値、汎用演算等
• スタック
  • LIFO(Last-In, First-Out)のデータ構造
  • 最低限2つの操作を提供する
    • push: スタックの一番上にデータを追加
    • pop: スタックの一番上のデータを取り出し、スタックから削除する
• キュー
  • FIFO(First-In, First-Out)のデータ構造
  • 最低限2つの操作を提供する
    • enqueue: キューの一番後ろにデータを追加
    • dequeue: キューの一番前のデータを取り出し、キューから削除する
• 優先度付きキュー
  • キューの要素に優先度を付ける
  • 新しい要素は通常はキューの末尾に追加されるが、優先度が高い要素は先頭に追加される
  • 最低限2つの操作を提供する
    • enqueue(e, p): キューに要素eを優先度pで追加
    • dequeue(): キューの先頭の要素を取り出し、キューから削除する
  • OSは実行待ちプロセスを優先度付きキューで管理する
• リスト
  • 要素の集合を保持するデータ構造で、柔軟性に富んだ構造
  • 一般的に以下の操作が定義される
    • insert(i, e): リストのi番目に要素eを追加
    • remove(i): リストのi番目の要素を削除
    • get(i): リストのi番目の要素を取得
    • sort(): リストの要素をソートする
    • slice(start, end): 位置startから位置endまでの部分リストを取得
    • reverse(): リストを逆順にする
  • データ型に柔軟性が必要ない場合は、スタックあるいはキューを使うほうがデータが厳密かつ堅牢に管理される上にデータの流れも明確になる
• ソート済みリスト
  • 常にソートされた要素のリストを扱いたい場合に役立つ
  • 挿入操作ではリストは常にソートされた状態を維持し、要素の並べ直しは不可
  • 一般的に以下の操作が定義される
    • insert(e): リストの正しい位置に要素eを追加
    • remove(n): リストの位置nの要素を削除
    • get(n): リストの位置nの要素を取得
• マップ
  • キーと値のペアを保持するデータ構造
  • キーでマップを探し、対応する値を取得する
  • 一般的に以下の操作が定義される
    • set(key, value): keyにvalueを関連付けて追加する
    • delete(key): keyに関連付けられた値を削除する
    • get(key): keyに関連付けられた値を取得する
• 集合(set)
  • 重複のない要素の、順序のない集まりを表現
  • 一般的に以下の操作が定義される
    • add(e): 要素eを集合に追加する。ただし要素eがすでに集合に含まれている場合はエラーを出す
    • list(): 集合の要素をリストにする
    • delete(e): 集合から要素eを削除する

4.3 データ構造

• データ構造: データがどのように構成され、コンピュータのメモリ上でどのようにアクセスされるかを定義する
• 各種のデータ構造があるため、必要に応じて最も適したデータ構造のADT実装を選ぶことが必要
• 配列(Array)
  • コンピュータメモリ上に用をを格納する手段として最もシンプル
  • コンピュータメモリ上に連続した領域を確保し、その領域に要素を順番に書き込み、要素の列の最後として特別のNULLトークンを付けることで構成する(CS50の講義も参照すると良い)
  • 利点
    • 配列の各オブジェクトはメモリ上に同じ量の領域を占有するため、任意の要素にすぐアクセスできる
    • 配列はプログラムとしての実装が容易
    • スタックの実装に適しているが、リストやキューの実装にも利用可能
  • 欠点
    • 大量の連続した領域を確保することが難しい
    • 配列を拡張する場合に必要な空き容量が不足する可能性がある
    • データの追加・削除で非効率な処理が発生する
• 連結リスト(linked list)
  • 要素は小さいメモリ領域であるセルの連鎖に格納される。このセルは連続したメモリアドレスである必要はない
    • 各セルが連鎖による次のアドレスを示すポインタを持ち、空のポインタを持つセルが連鎖の終わりを示す
  • 利点
    • スタックおよびキューの実装に使用できる
    • 連続したメモリ領域が不要なため、リストの拡張が容易
    • データの追加・削除が効率的
      • セルのポインタの変更のみで済むため挿入・削除操作が容易
  • 欠点
    • n番目の要素へのアクセスが遅い
      • 連結リストのn番目の要素にアクセスするためには、最初の要素から順にポインタをたどる必要がある
    • 単一のセルのアドレスだけ渡された場合の挿入・削除が非効率
      • 単一のセルのアドレスのみでは連鎖の後のセルのアドレスを知れない
• 双方向連結リスト(double linked list)
  • 拡張版の連結リスト
  • 各セルが前後のセルのアドレスを持つ
  • 長所
    • 連結リストと同様に連続したメモリ領域の確保が不要
    • 前後のセルのアドレスも保持しているので、特定のセルの移動や挿入、削除が効率的。単一のセルのアドレスだけ渡された場合でも削除が可能
  • 短所
    • 連結リストと同様にn番目の要素へのアクセスが遅い
    • 各セルに2つのポインタを格納するためプログラムの複雑さとデータ格納のために要するメモリ使用量が増加する
• 配列 vs. 連結リスト
  • 連結リスト > 配列のケース
    • 非常に早く要素の挿入・削除を行いたい
    • データへのランダムで順不同なアクセスは必要ない
    • リストの中ほどに要素を挿入・削除したい
    • リストのサイズを正確に評価する必要がない
  • 配列 > 連結リストのケース
    • 頻繁にデータへのランダムで順不同なアクセスが必要
    • 要素へのアクセス性能は特に優れている必要がある
    • 実行中、要素数が変わることはなく、コンピュータメモリ上の連続領域に容易に割り当てることができる
• 木(tree)
  • オブジェクトの格納にメモリセルを用い、セルは別のセルへのポインタを持つ
  • 連結リストと異なりセルとポインタは線形の連鎖としてではなく樹状構造に配置される
  • ノード(node): Treeにおける各セルのこと
  • エッジ(edge): あるセルから別のセルへのポインタのこと
  • ルート(root): 木の最上位のセル
  • 葉ノード(leaf node): 他のノードへのエッジを持たないノード
  • パス(path): あるノードから別のノードへのエッジとノードの集合
  • レベル(level): ルートからの距離。ルートノードへのパスの数
• 二分探索木(binary search tree)
  • 効率的に検索できる木構造
  • 2つを上限に子を持つことができる
  • 左の子は親より小さく、右の子は親より大きい
  • 二部探索木に多くのノードを挿入すると大半のノードが1つの子しか持たず高い木になり検索効率が低下する。この場合はノードを再配置し高さを調整する(木の平衡)
  • 二分探索木の検索はO(log n)であるため、非常に効率的
  • 木の平衡を保つ処理にはすべてのノードをソートする必要があり、また要素の挿入・削除のたびに木の平衡をとると操作速度が大幅に低下する
  • 二分探索木の平衡を効率的に保つために、平衡二分探索木(self-balancing binary search)が考案された
    • 要素を挿入・削除するための手続き自体が木の平衡状態にあることを保証する
    • 代表的な平衡二分探索木としては、AVL木、赤黒木、B木、B+木、B*木などがある
• 二分ヒープ(binary heap)
  • 最大または最小の要素を即座に探し出すことができる特殊な二分探索木
  • 優先度付きキューの実装に特に有効
  • ヒープでは最大または最小の要素の取得はその要素が常に木のルートノードであるため常にO(1)で行うことができる
  • 親ノードは両子ノードよりも大きい(最大ヒープ)または小さい(最小ヒープ)という追加制約を持つ
• グラフ(graph)
  • 木に類似しているが、子ノードと親ノードいう関係がなく、従ってルートノードが存在しない
  • データはノードおよびエッジで自由に配置できるため、このデータ構造は最も柔軟で、ほとんどすべてのデータを表現するのに使用できる
• ハッシュ表(hash table)
  • 要素の探索をO(1)で行うことができるデータ構造
  • 配列と同様に大きめの連続したメモリ領域を確保する必要があるが、要素の格納位置はハッシュ関数によって決定する
  • ハッシュ関数が別々の2つのキーに対して同じメモリ位置を返してしまうことを「ハッシュ衝突(hash collision)」という
  • マップと集合の実装によく使用され、木構造のデータ構造より挿入・削除が高速だが、正常な動作のためには非常に大きな連続したメモリ領域を必要とする

Chapter 5: アルゴリズム

重要なアルゴリズムについてのみ、ピックアップして解説する

以下について

• ソート
• 探索
• グラフ
• オペレーションズサーチ

5.1 ソート

• 選択ソート
  • 最小値を見つけ、それをリストの最初の要素と交換する
  • 残りのリストをソートする
  • O(n^2)の計算量
• バブルソート
  • 隣接する要素を比較し、順番が逆であれば交換する
  • リストの最後まで繰り返す
  • O(n^2)の計算量
• 挿入ソート(insert sort)
  • リストをソート済み部分と未ソート部分に分割し、未ソート部分の先頭要素をソート済み部分に挿入する
  • 入力のデータの並びが計算量に大きく影響
  • O(n^2)の計算量だが、データがすでにソートされている場合はO(n)で済む
• マージソート(merge sort)
  • リストを半分に分割し、それぞれをソートする
  • 2つのソート済みリストをマージする
  • O(n log n)の計算量
• クイックソート
  • ピボットを選択し、それを基準にリストを2つに分割する
  • それぞれのリストを再帰的にソートする
  • O(n log n)の計算量

メモ

• ソートアルゴリズムは過去に何度も実装しているけれど、実務でなかなか直接使うことは少なくて抜けていっている気がしている

5.2 探索

• 逐次探索
  • リストの先頭から順に要素を比較し、目的の要素を見つけるまで続ける
  • O(n)の計算量
• 二分探索
  • 要素がソート済み配列上に構成されている場合は、二分探索を使えばO(log n)で目的の要素を見つけることができる
  • 各段階で探索領域の1/2が対象から除外される
• ハッシュ探索
  • ハッシュ表に要素を格納することでO(1)で目的の要素を見つけることができる

メモ

• あまり意識していなかったが、前職で取り組んでいた開発ではハッシュ探索相当のものを使った実装をしていた。アプリケーション内部でインメモリ領域に数千~数万件のデータを保持してそれを高頻度に読み出すようなものだったので、ハッシュ探索を使っていた

5.3 グラフ

• グラフはノードとエッジの集合で構成される
• SNSや電話網などのデータ表現に広く使われている
• グラフ構造自体が探索のためのなんらかの機能を準備している場合もあるが、通常は目的の要素に遭遇するまでグラフの各ノード全てにアクセスする必要がある
• グラフの探索戦略
  • 深さ優先探索(depth-first search: DFS)
    • エッジに従い、グラフを深掘りしていく
    • 新しいノードへのエッジがないノードに到達すると、上のノードにもどり、新しいノードを探す
    • 探索の足跡を残すためにスタックを用いて、ノードの探索を行った時にスタックにノードをプッシュし、戻る必要がある時にスタックからノードをポップする
      • バックトラック戦略はこの流れで行われる
  • 幅優先探索(breadth-first search: BFS)
    • グラフのレベルごとに、最初は開始ノードの隣のノード、次にその隣のノードと幅優先に探索していく
    • 探索の記録にはキューを用いて、ノード探索時に一旦子ノードすべてをエンキューし、あとで次のノードを探索する時にデキューする
• 深さ優先探索(DFS)と幅優先探索(BFS)の違いは、次に探索するノードをスタックに格納するか、キューに格納するか
  • 深さ優先探索は現在のノードへ至る親ノードたちを格納するだけで済み、実装が単純でメモリ消費も節約できる
  • 幅優先探索は、次の探索領域をキューに格納し、探索対象をデキューしながら探索するため、メモリ消費が大きい
    • 例えば2階層目に大量にノードがある場合、幅優先探索はそのノードを全てキューに格納するため、メモリ消費が大きくなる
• 経路探索
  • ノード間の最短経路の探索
  • 最短経路の探索アルゴリズムではダイクストラのアルゴリズムが有名で最も効果的
  • ダイクストラのアルゴリズム
    • BFSは補助にキューを使うが、ダイクストラのアルゴリズムは補助に優先度付きキューを使う
    • ノード探索の際に、該当するノードから接続されたものが優先度付きキューに追加され、開始ノードからのエッジの重みによって優先度が決まる
    • 探索はノード開始地点から常に最も近くにあるノードから行われる
    • 宛先ノードをみつけられず、永遠に循環する場合があるため注意する
• 双方向探索
  • 2つのノードから同時に探索を行い、それらが出会う地点を探す
  • 2つの探索が出会う地点が最短経路の地点となる
  • 2つの探索が同時に行われるため、通常の探索よりも高速に目的地点を見つけることができる
• ページランク
  • Googleの検索エンジンのアルゴリズム
  • ウェブページの重要性を評価するためのアルゴリズム
  • あるWebページが別の重要度の高いページから多くのリンクを受けている場合はそのページも重要度が高いと推定し、そのページのランクを上げる

5.4 オペレーションズリサーチ

• オペレーションズサーチは、複雑なシステムやプロセスを最適化するための手法
• 何かを「最大化したい」「最小化したい」という目的を定義することもオペレーションズリサーチの対象
• 線形計画問題
  • 線型方程式(1次多項式)を使って、目的と制限のモデルを作成できる問題のこと
  • 例) ある面積のオフィスと予算がある状態において、ファイル収納容量を最大にするためのキャビネットの配置
  • 線形計画問題はプログラムせず、シンプレックス法などのアルゴリズムを使って解く
• ネットワークフロー問題
  • ネットワーク上のリソースの流れを最適化する問題
  • 線型方程式で書くことができ、シンプレックス法でとくことができる
• シンプレックス法を用いることで、グラフ、コスト、フローなど多数の線形計画問題を簡単に解くことができる

Chapter 6: データベース

• リレーショナル
• 非リレーショナル
• 分散データベース
• 地理情報
• シリアライゼーション

6.1 リレーショナルデータベース

• 現在最も活用されている形式のデータベース
• 重複した情報とデータの不一致を容易に排除できる
• リレーショナルデータベースの構造
  • テーブル: データの集合
  • レコード: テーブル内の1行
  • カラム: テーブル内の1列(field)
  • キー: テーブル内のレコードを一意に識別するためのカラム
  • 外部キー: 2つのテーブル間の関係を示すカラム
  • スキーマ: fieldとそのfieldに対する制限の定義のこと
• リレーションシップ
  • テーブル間の関係
  • 主キー: テーブル内のレコードを一意に識別するためのカラム(primary key)
  • 外部キー: 別の表のIDへの参照が記録されるフィールド(foreign key)
  • 主キーと外部キーを使ってテーブル間の関係を構築する
  • 正規形: データベースが重複した情報が一切ないように構成されている状態(normalized)
  • 正規化: データベースを重複がない状態に変換する手続き(normalization)
• スキーママイグレーション
  • データベースの構造(スキーマ)を変更する必要がある場合にはスキーママイグレーションスクリプトを作成・実行する
    • このスクリプトにより、スキーマを変更し、既存のデータも適宜変換される
  • スキーママイグレーションはデータベースのバージョン管理にも利用される
• SQL
  • リレーショナルデータベースを操作するための標準的な言語
  • DDL(Data Definition Language): データベースの構造を定義するための言語
    • CREATE: テーブルやインデックスを作成
    • ALTER: テーブルの構造を変更
    • DROP: テーブルやインデックスを削除
  • DML(Data Manipulation Language): データを操作するための言語
    • SELECT: データを取得
    • INSERT: データを追加
    • UPDATE: データを更新
    • DELETE: データを削除
  • DCL(Data Control Language): データベースの権限を管理するための言語
    • GRANT: ユーザに権限を付与
    • REVOKE: ユーザの権限を取り消す
  • JOINによる表の結合はRDBの最大の長所であるが、計算コストは高価であるため目立った短所でもある
• インデックス作成
  • 即座にデータ取得を行うためにDBMSの補助的に作成される
  • 平衡二分探索木で実装されている
  • 主キーで作成されるほか、任意のフィールドでも作成できる
  • 一意制約
    • 重複を許さない制約
    • 一意制約を設定すると、インデックスが作成されることが多い(多くのDBMSで)
  • ソート
    • インデックスはインデックス付きフィールドでのソート済みの順序で行を取り出すのにも役立つ
      • 例えば「name」フィールドにインデックスがあると、特別の計算なしに名前でソートされた行を取得できる
    • 複合インデックスを使うことで複数のフィールドでソートされた行を取得できる
  • 性能
    • インデックスの作成はディスク領域も占有する上に、データの更新・挿入・削除で高い計算コストが発生するため必要なもののみで行う
    • データベースを構成のに調整するには、どのインデックスを保持し、どのインデックスを破棄するかを把握することが重要
      • 読み出しばかりで更新が滅多になければ、多めにインデックスを保持することが妥当
    • 効果があると「思われる」フィールドにインデックスを貼るのではなく、効果があると「明らか」なフィールドのみにインデックスを貼る
• トランザクション
  • データベースの操作をまとめて処理するための仕組み(不可分操作)
  • ACID特性
    • Atomicity(原子性): トランザクションは全て成功するか全て失敗するかのどちらか
    • Consistency(一貫性): トランザクションの実行前後でデータベースの整合性が保たれる
    • Isolation(独立性): トランザクションは他のトランザクションと独立して実行される
    • Durability(永続性): トランザクションが成功すると、その変更はデータベースに永続的に保存される

6.2 非リレーショナル

• SQL以外のクエリ言語を使用するため、NoSQLデータベースとも呼ばれる
• ドキュメントストア
  • 最も広く知られているNoSQLデータベース
  • データ要素はアプリケーションで必要とされる通りに保持する
  • 情報を必要に応じて関連する場所にコピーすることを善しとするため、重複したデータを一貫性を保って更新することは難しい
  • ドキュメントストアは柔軟性に強みを持つ
    • 行を結合する必要があない
    • 固定スキーマが不要
    • 各データ要素は独自のフィールド構成をもてる
  • ドキュメントストアには「表」「行」がなく、代わりに「ドキュメント」としてまとめられ、関連するドキュメントは「コレクション」としてまとめられる
  • 主キーのフィールドがありドキュメント間のリレーションも可能だが、JOINは非推奨または非サポートの場合も多いので、複数のドキュメントが関連するデータを扱う場合にはそのデータは各ドキュメントにコピーを作成する方が良いケースも多い
  • ドキュメントストアでも主キーのフィールドのインデックスを作成する
  • 追加のインデックスの作成も可能
• キーバリューストア
  • 整理済みの永続データストレージの単純版で、キャッシュ用途での利用が多い
• グラフデータベース
  • データ要素はノードとして、リレーションシップはエッジとして格納される ノードは固定スキーマに束縛されず、柔軟にデータを格納できる
  • 最も自由度が高いデータベース
  • データがネットワーク上のようであれば、グラフデータベースが適している
• ビッグデータ
  • データの量(Volume)、発生頻度(Velocity)、多様性(Variety)に関して極めて挑戦的であるデータ処理を意味する
    • ハドロン衝突型加速器(LHC)のように何千テラバイトにも及びデータを処理するなど
  • ビッグデータが指す発生頻度とは、何百万回の書き込みを円滑に、また数十億回の読み出しも円滑に行うことを指す
  • ビッグデータは柔軟性が必要になるため、RDBを使うことは現実的ではない
• SQL vs. NoSQL
  • リレーショナルデータベース: データ構造を最大限に活用し、重複を取り除く
  • 非リレーショナルデータベース: アプリケーション中心で、必要に応じてアクセスと活用を手助けする
    • NoSQLデータベース: 大規模、揮発性、非構造のデータを素早く、効率的に保存できる
    • 自由な分、データの一貫性などはプログラマの責務となる

6.3 分散データベース

• 分散データベースは複数のデータベースを1つのシステムとして扱う
• データ量が膨大な場合、一秒あたりのクエリ数が多い場合、単独のDBに頼るのリスクが高いシステムの場合には複数のDBを用いて分散データベースを構築する
• シングルマスターレプリケーション
  • 1つのデータベースがマスターとして機能し、他のデータベースがスレーブとして機能する
  • 各スレーブにはDBの複製が存在し、マスターは書き込みを受け取るとこのクエリをスレーブにも転送して同期を維持する
  • マスターがダウンした場合、スレーブの1つをマスターに昇格させることでシステムを維持する
• 多重マスターレプリケーション
  • DBが非常に多くの同時書き込みクエリを処理する必要がある場合に、複数のコンピュータから構成されるクラスタのすべてのコンピュータをマスターに設定して負荷を分散する
  • 各コンピュータはクラスタの全マシンに接続され、それらの間で書き込みクエリが伝搬される。そのため全マシンで同期が維持され、各コンピュータがDB全体の複製を持つ
• シャーディング
  • 複数のコンピュータにDBを分割して配置することで、負荷を分散する
  • DBが大量のデータの書き込みクエリを多数受け取った場合にクラスタのあらゆるDBに同期を行うことは困難で、さらにストレージ領域が不足する可能性もある場合にも用いられる
  • 各マシンにDBの一部(シャード)を所有し、クエリルータが関連するマシンにクエリを転送する
  • 超大規模データベースの読み書きクエリを多数処理できるが、クラスタのいずれかのマシンに障害が発生した場合はそのマシンが担当するデータが利用できなくなる
    • レプリケーションと組み合わせることでこのリスクを軽減できる
• データの一貫性
  • レプリケーションによる分散データベースでは、同期の完了まで時間がかかるため、データの一貫性を保つことが難しい
  • データベースシステムでは、クラスタ全体でデータの一貫性を保証するクエリを発行できるものもあるが、データの一貫性を保証するとデータベースシステムの性能が低下する
    • 特にトランザクションでは、重度の性能問題を引き起こす可能性がある
  • 結果整合性
    • クエリが強引にデータの一貫性を取ろうとせず、結果としては一貫性のあるデータが保証される状態のこと
    • いくつかの書き込みクエリの適用が遅れ、いくつかの読み出しクエリでは古い情報が返される可能性がある

6.4 地理情報

• 地理情報システム(GIS)
  • 地理情報を管理するためのシステム
  • 空間情報インデックスを利用しているため、空間的近接による探索効率が非常に優れている
  • 汎用DBMSの多くはGIS拡張をサポートしている

6.5 シリアライゼーション

• 複数のシステム間での相互運用を実現するために、データを直列化する手続き
• データをエンコードフォーマットに変換することで、エンコードフォーマットに対応したあらゆるシステムで解読できるようになる

Chapter 7: コンピュータ

• アーキテクチャ
• コンパイラ
• 記憶階層

7.1 アーキテクチャ

• コンピュータの2大構成要素: プロセッサ、メモリ
  • メモリ(= Random Access Memory: RAM)
    • 命令を書き込む場所で、操作対象のデータも格納される
  • プロセッサ(= Cenral Proccesing Unit: CPU)
    • メモリから命令及びデータを読み込み、それを実行する
• メモリ
  • 多くのセルから構成され、各セルは微量のデータを格納。各セルごとにアドレスを持つ
  • メモリのデータの読み書きは一度に1つのセルに対する操作で行われる
• CPU
  • レジスタ(register)と呼ばれる内部メモリセルを持ち、そこに格納された数値で基本的な算術演算を実行できる
  • CPUが実行できる全命令の集合 = 命令セット
  • コンピュータのプログラムコードは本質的にはCPUの命令を示す一連の数値であり、それらの命令は数値としてRAM上に格納される -プログラムコード、入出力データ、処理中のデータのすべてがRAM上に格納される
  • CPUクロック: CPUの一秒あたりの実行サイクル数
    • クロック数が高いほどCPUの処理速度が速い
  • CPUアーキテクチャ: プロセッサの設計構造。CPU命令セットが異なるため、PCとスマホで同じコードでも動作しないなどの問題が発生する
  • 32-bit vs. 64-bit アーキテクチャ
    • 世界初のCPUは4-bitアーキテクチャで作られた Intel4004
      • 1つのCPU命令で最大4桁の2進数に対して加算・比較・移動といった演算ができた
      • その後8-bitアーキテクチャ、16-bitアーキテクチャ、32-bitアーキテクチャ、64-bitアーキテクチャと進化していった
  • ビッグエンディアン vs. リトルエンディアン
    • ビッグエンディアン: 最上位バイトからデータを格納
    • リトルエンディアン: 最下位バイトからデータを格納
    • 今日のほどんとのCPUではリトルエンディアンが採用されている
  • エミュレータ
    • 対象のコンピュータを模倣するプログラムで、模倣対象のコンピュータと同じCPU,RAM,ハードウェアのように振る舞う

7.2 コンパイラ

• プログラミング言語: コンピュータに対する指示をより自然でコンパクトに表現する
• コンパイラ: プログラミング言語で書かれたコードをCPUが理解し実行できるCPU命令に翻訳する
• チューリング完全
  • あるプログラミング言語がチューリング完全であるとは、その言語で書かれたプログラムがチューリングマシンと同じように任意の計算を実行できることを意味する
• オペレーティングシステム
  • コンパイル済みのソースコードは本質的には一連のCPU命令であり、それらの命令はCPUが理解できる形式で格納される
  • コンパイル済みのプログラムは特定のCPUやOSを指定する形で生成されるため、CPUアーキテクチャやOSが異なると実行できない場合がある
• スクリプト言語
  • 機械語コードへのコンパイルなしに、プログラムを実行する(JavaScirpt, Python, Rubyなど)
  • これらの言語はCPUによって直接実行されるのでなく、プログラムを実行しているコンピュータにインストールされたインタプリタ(interpreter)がプログラムを実行する
  • インタプリタはプログラムを1行ずつ読み込み、その都度CPU命令に変換して実行するため実行速度は遅いが、コンパイルを挟まないためすぐに実行できる

7.3 記憶階層

• コンピュータはCPUが単純命令を実行することで動作するが、その命令が格納されるCPUレジスタは通常1000バイト未満に制限されている。そのためCPUレジスタは常にRAMとの値だでデータを転送している
• つまりメモリアクセスが遅い=メモリにデータを読み書きする速度がそのままコンピュータの性能に直接関わってくる
  • メモリの速度を上げれば、CPUの速度を上げるのと同じくらいコンピュータの速度を押し上げる
• プロセッサとメモリの差
  • CPUレジスタのデータはCPUから1CPUサイクルでアクセスできるが、RAMのデータはCPUから約1000CPUサイクルかかる
• RAMアクセスを最小限に留めるための2つの性質
  • 時間的局所性(temporal locality): あるメモリアドレスがアクセスされた後に、高確率で再び同じアドレスがアクセスされる
  • 空間的局所性(spatial localoty): あるメモリアドレスがアクセスされた直後に、高確率でそのアドレスの近くのアドレスがアクセスされる
• L1キャッシュ(第1次キャッシュメモリ)
  • このメモリからデータをレジスタに取得するのは、レジスタ自体からデータを取得するよりも少し遅い程度(約10CPUサイクル程度)
• L2キャッシュ(第2次キャッシュメモリ)
  • L1キャッシュを約50KB以上にするのは非常にコストがかかるため、追加のメモリキャッシュとしてL2キャッシュが用いられる
    • 最新のCPUには約200KBのL2キャッシュが搭載されているものもある
• CPUはL1キャッシュを最初に検索し、そこにデータがない場合はL2キャッシュを検索する。L2キャッシュにもデータがない場合はRAMを検索する

Chapter 8: プログラミング

• 言語学
• 変数
• パラダイム

8.1 言語学

• プログラミング言語 = 情報操作のために存在
• プログラミング言語のものつ情報操作のための3つの基本構成要素
  1. 値
  2. 式
  3. 文 +α: 演算子
• 値
  • プログラミング言語において極めて重要で、第一級市民民(first-class citizen)と呼ばれるもの
  • 言語は値に対してあらゆる種類の操作を許可する
  • 実行時に作成でき、引数として関数へ渡すことも、関数から返すこともできる
• 式
  • 値を表現するために使用され、一連の演算子とオペランドの組み合わせで、単一の値を生成するもの
  • コンピュータが単一の値にまで計算できるように書いたもので、最終的には指揮はどれだけ複雑であっても常に単一の値にまで評価できる
• 文
  • コンピュータに何かすることを指示するために使用される
    • e.g) print(hello world)
    • 式は値を表現するために使われるもの
  • if文、for文、while文などがある

8.2 変数

• 変数は、名前と値の間の名前束縛(name binding)を表し、値が格納されているメモリアドレスに名前を結びつけたaliasとして機能する
• 変数の型付け
  • 変数には整数や文字列など型を割り当てる必要がある。この型によってプログラムはその変数をどう解釈すべきか認識する
  • 型チェックの実行は静的・動的の２種類存在する
    • 静的型付け: 事前に宣言することで、コンパイル時に型チェックを行う
    • 動的型付け: 実行時に型チェックを行う
• 変数の有効範囲(scope)
  • ほどんどの言語において、変数の有効範囲は変数が定義された関数の内側だけ
  • 現在のコンテキスト(context)または環境(environment)とは、プログラムの所定の箇所で使用可能な名前束縛の集合のこと
  • 実行の流れがコンテキストから離れると、そのコンテキスト内で定義された変数は使用できなくなり、コンピュータのメモリも解放される
  • 常にどこからでアクセスできるものをグローバル変数と呼ぶ
  • どこからでも使用できるすべての名前の集合は、プログラムの名前空間(namespace)に集約される
    • できる限り小さくなるようにすること
    • 名前空間に必要のない名前を追加すると、「名前空間汚染」と呼ばれる問題が発生する

8.3 パラダイム

• パラダイム: 科学分野を定める概念と実践の特定の集まりで、問題への取り組み方と、使用するテクニックと解法の構造を導く
• プログラミングパラダイム: プログラミング領域での視点で、コーディングスタイルとテクニックを指す
  • プログラミングパラダイムでは、命令型・宣言型・論理型の3種類が代表的
  • 多くのプログラマは1つのパラダイムのみしか経験しないが、3種類すべて学ぶことはプログラミングから最大限の恩恵を受けるためにも重要
• 命令型プログラミング
  • プログラムは特定の命令を使用して、各段階で厳密に何をするのかをコンピュータに対して指示するもの
  • 各命令はコンピュータの情報を変更する
  • プログラムは一連の命令から構成され、それらの命令は順番に実行される
  • 命令型プログラミングは、アルゴリズムを記述するための最も基本的な方法
  • 手続き型プログラミング: 命令型プログラミングの一種
    • プログラムコードを手続き(procedure)として構成し、それらの手続きを順番に実行する
    • プログラムコードの複製を回避し、再利用性を上げることができる
    • 手続き型を使うことで、関連するプログラムコードをまとめ、論理的に別々に分けることができるようになった
• 宣言型プログラミング
  • 目的に到達するための全ての手順を事細かに示さずとも、期待する結果だけを宣言できる
  • プログラムは、何をしたいかではなく、何を期待しているかを記述する
  • 関数型プログラミング
    • このパラダイムにおいて、関数は複数要素間の関係を表現するなど手続き以上の役目を果たす
    • 文字列や数値といった基本データ型と同様に第一級市民として扱われる
    • 関数は引数として別の関数を受け取り、関数を戻り値として返すことができる(= 高階関数(high-order function))
      • 多くのプログラミング言語でもこの高階関数の仕組みを取り入れている
    • 糖衣構文(syntactic sugar): 関数型プログラミング言語は、関数を記述するための特別な構文を提供することが多い
      • 例えば、map関数はリストの各要素に関数を適用する
    • 高階関数は引数として関数を受け取る以外に、戻り値として新しい関数を生成できる
      • 戻り値として生成する関数の中に、値への参照を閉包(closure)として保持することができる
      • クロージャを有する関数は何かものを記憶し、閉包された値の環境へアクセスできる
      • クロージャを使って複数の引数を受け取る関数の実行をいくつかの段階に分割したものをカリー状態あるいはカリー化(currying)と呼ぶ

        // カリー化の実装例
            function add(x: number): (y: number) => number {
                return function(y: number): number {
                    return x + y;
                }
            }
            const add2 = add(2);
            const sum = add2(3); // 5
        

      • グローバル変数を用いると名前空間を汚染するが、クロージャを使うことで名前空間の汚染をせず関数の内部状態の管理などが可能になる
    • パターンマッチング
      • 関数型プログラミング言語では、パターンマッチングを使ってデータ構造を分解することができる
      • 関数の場合は引数の値に応じて異なる処理を行うことができる

        // 命令型プログラミングの場合
        function factorial(n: number): number {
            if(n === 0) {
                return 1;
            } else {
                return n * factorial(n - 1);
            }
        }
        // 関数型プログラミングのパターンマッチング例
        function factorial(n: number): number {
            return match n {
                0 => 1,
                _ => n * factorial(n - 1)
            }
        }