みんなのコンピュータサイエンス
みんなのコンピュータサイエンス
「コンピュータに対するコンパクトな知識地図」
ohbarye.icon 個々を詳解しているわけではないので用語を知るにとどまる
9章にあった「優れたプログラマであれば知っているべきコンピュータサイエンスに関する最小限の知識」というのが全て
理解のためには別途掘り下げる必要がある
1章〜5章は離散数学、計算量、データ構造、アルゴリズムの基礎知識の説明
3章 戦略
反復や再帰まずはブルートフォースして徐々にA* algorithmのようなヒューリスティック手法や分割統治法で改善していく、みたいなアプローチの紹介
バックトラックや動的計画法、最適化問題の分枝限定法にも触れている
5章 アルゴリズム
オペレーションズリサーチ
線形計画問題
6章 データベース
ohbarye.icon RDBMSについては読み飛ばした
NoSQLでは以下に触れている
MongoDBのようなドキュメントストア
Redis、Memcachedのようなキーバリューストア
Neo4jのようなグラフデータベース
SQL vs. NoSQL
リレーショナルデータベースはデータ中心
データがどのように必要とされるかに関わらず、データ構造を最大限に活用し、重複を取り除く
非リレーショナルデータベースはアプリケーション中心
必要に応じてアクセスと活用を手助けする
NoSQLデータベースを使うことで、大規模、揮発性、非構造のデータを素早く、効率的に保存することが可能
固定スキーマとスキーママイグレーションを気にすることなく開発できる
ただしプログラマの責任が増す
分散データベース
可用性やパフォーマンスのために分散データベースシステムを構成する
レプリケーション、シャーディング、一貫性、結果整合性に触れている
地理情報システム(GIS)
クエリエンジンがGIS拡張に対応していればデータベースで対応できる
Databaseで利用できるindexの種類には地理情報を扱えるものもある
シリアライゼーション
CSV, JSON, XML, SQL dumpなど
7章 コンピュータ
ohbarye.icon CPUの創りかたやコンピュータシステムの理論と実装でやった内容
プレイステーションのCDをPCで実行できないのは、CPUアーキテクチャが違うから
書かれている命令を解釈できない
現代ではx86がある程度一般的
エミュレータ
チューリング完全
コンパイラ
末尾最適化
逆アセンブルによるリバースエンジニアリング
CPU、RAMまわり
時間的局所性
あるメモリアドレスにアクセスされた直後、高確率で同じアドレスへのアクセスが発生する
空間的局所性
あるメモリアドレスにアクセスされた直後、高確率で隣接するアドレスへのアクセスが発生する
L1キャッシュ
CPU組み込みの補助メモリ
レジスタよりちょっと遅いぐらい
50KB以上にするにはコストがかかる
L2キャッシュ
L1よりやや低速だが容量を確保できる
200KB
L3キャッシュ
L1~L3キャッシュは重要なのでCPUのシリコン空間の大部分を占める
スラッシング
コンピュータが常にRAMからデータを取り込んでいる状態
プログラムが処理するデータとプログラムがRAMに収まらずRAMが不足すると、コンピュータは常にディスクとRAM間でデータを転送することになるので性能が著しく低下する
9章
ohbarye.icon オブジェクト指向を取り上げていなかったのは意外