Table shoji 2nd. プログラマなら知ってる一覧 2019/05/18
参加者:
shojik shojik.icon
taniguchi
o_syoshiki
moritsuka(@sanfrecce_osaka)
Sven
kosuke
目標
知らないことを知る、どこで役立つか?
議題
コンピューターサイエンス学んだ人 情報系: 0
計算量
-> 数学で学べる
計算量はおさえておくと「ユーザー数が増えたらバッチが全然終わらない」なんてことになりにくいかも
クイックソート、とか
探索の例が役立つ
Hash table: O(1) データが100倍になっても(理論的には)計算時間は変わらない
rehash が O(1) の鍵
2分探索やツリーを使う O(log n) データが100倍になると時間は6倍くらい(log2で)
線形探索 O(n) - データが100倍になると時間が100倍になる
探索するプログラムのパフォーマンスに役立つ
見積もり、より良い手段が存在するかどうかの判断基準をもつことができる
データベースでは、Btreeでインデックスを貼ったり
データベースでのパフォーマンスで知識が役立つ
Btreeについて
インデックスをはらないと線形探索になる
貼ったらO(log n)とか
データ構造
スタック
pushとpopしか使っていない配列
言語処理系とかで使う
リスト
lined list
使わない(個人的見解)
関数型言語だと良く使うけどJavaとかで使うのかなあ?
ツリー
探索を早くする
キュー
最短経路探索
データを詰めてそれを詰めた順に取り出す
プライオリティキュー(優先度付きキュー)というものもある
優先度高ければそっちを先に取りだす
優先度同じなら先に詰めたものを取りだす
分散システム (Amazon Simple Queue Service とか)
アルゴリズム
数値計算
グラフ理論
理論計算機
セキュリティ・暗号化
プログラミングパラダイム
並列・非同期処理の基礎