まっつーのブログ

本の感想や振り返りなど雑多に書いてます

第9章 仮想メモリ

仮想メモリの特徴 キャッシュの構成 ページ・テーブル アドレス変換 Linux の仮想メモリ・システム 共有オブジェクト コピー・オン・ライト 動的メモリ・アロケータ 断片化(フラグメンテーション) ガーベジコレクション 感想 9章について この章では、メモリマッ…

第8章 例外的な制御フロー

例外的な制御フローって? 例外 プロセス 平行と並列 コンテクスト・スイッチ システム・コールにおけるエラー・ハンドリング プロセスの生成と終了 シグナル 非局所的ジャンプ 感想 8章について この章では、制御フローについて学んでいきます。 例外的な制御…

第7章 リンク

リンクとは? 静的リンク オブジェクト・ファイル シンボル マングリング ライブラリが必要な理由 再配置 共有ライブラリって? ポジション非依存コード(PIC) インターポジショニング 感想 7章について この章では、そもそもリンクとはなんだろう?ということ…

植山類さん講演会 (並行プログラミング)

先週に引き続き、リンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者である植村類さんの講演会に参加しました。 今回は並行プログラミングを主題として、効率化の仕組みや類さんが自作されているリンカmoldについても教えていただきました。 …

第6章 メモリ階層

メモリ階層 ストレージの技術 DRAMの種類 メイン・メモリへのアクセス ディスク・ストレージ 半導体ディスク (SSD) 局所性 キャッシュ ライトに関する問題 キャッシュ・パラメタの性能への影響 感想 6章について この章では、メモリ階層ごとの特性や回転ディス…

競プロ典型90問 050(★3) DP

050 - Stair Jump(★3) 問題 N 段の階段 があり、一歩で 1 段か L 段上がれる。 0 段目からN 段目までたどり着く移動方法何通りか、109 + 7 で割った余りを求める。 解法 そこまでに行ける通り数をDPで下から計算する。 答えは大きくなるので常にmodを取り…

競プロ典型90問 048(★3) 貪欲法

048 - I will not drop out(★3) 問題 N 問, K 分間, 満点 A 点, 部分点 B 点(部分点は満点未満, 半分より大きい) つまり を満たす。 1分で部分点, 2分で満点が取れる。 K 分間で得られる最大得点を求める。 解法 得点方法は2パターン。 B 点取る or B 点取…

植山類さん講演会

植山類さんの講演会に参加してきました。 植山さんは、高速なリンカlldのオリジナル作者かつ現メンテナで、Cコンパイラ8ccの作者でもあります。 そのため今回は特にリンカについて詳しく教えていただきました。 リンカの役割から動的リンクの仕組みまで前提…

第5章 プログラム性能の最適化

プログラムの最適化 最適化コンパイラ コードレベルの最適化 スーパースカラ 投機実行 レジスタ関連 ループ・アンローリング 条件付き移動 write/read依存 性能向上の4つのテクニック 感想 5章について この章では、コードの性能を向上させる数多くのテクニッ…

競プロ典型90問 046(★3) 組合せの問題

046 - I Love 46(★3) 問題 3つの長さ N の数列 A, B, C が与えられる。 が46の倍数となるの選び方の総数を求める。 解法 3つの数列が最大105と制約が厳しいため全探索ではTLEになってしまう。 そのため、最初にmodを取ることで、0〜45の46種類に絞る。 463…

第4章 プロセッサ・アーキテクチャ

ISA(命令セット・アーキテクチャ) プログラマ・ビジブルって? ハードウェア設計 レジスタファイル シーケンシャルなプロセッサ(SEQ) 処理ステージの説明 パイプライン処理 効率低下の要因 パイプライン・ハザードとは? 例外処理 感想 4章について この章では…

競プロ典型90問 038(★3) オーバーフロー

038 - Large LCM(★3) 問題 A, Bの最小公倍数を求める。 を超える場合は Large と出力する。 解法 最小公倍数は で表される。 そのまま計算すると でオーバーフローすることがあるので、式を変換する。 であれば が成り立つので正しく答えが求まる。 ちなみ…

第3章 プログラムのマシン・レベルの表現

高水準言語と低水準言語 マシン・レベル・コード 符号拡張 データ移動 ジャンプ命令 データ転送と制御転送 プロシージャ ポインタ演算 配列の格納 構造体と共用体 アラインメント制約 バッファ・オーバーフロー セキュリティ対策 感想 3章について この章では、…

競プロ典型90問 032(★3) 順列全探索

032 - AtCoder Ekiden(★3) 問題 N人の駅伝選手。 コースは 1からN区まであり、選手 i が j 区までかかる時間は M 個のルールがあり、 と はたすきの受け渡しができない。 ゴールまでにかかる時間の最小値を求める。 解法 制約が N ≤ 10 と小さいため最大で…

競プロ典型90問 020(★3) 浮動小数点の誤差

020 - Log Inequality(★3) 問題 < が成り立つか。 解法 愚直に log() を使って求めると誤差が出てしまう。 そのため全て整数で処理をする必要がある。 対数 log は 底が同じ値の場合、log が外せるので、 は と表せる。 そして累乗の場合は、 が成り立つ。…

競プロ典型90問 018(★3) 三角関数

018 - Statue of Chokudai(★3) 問題 平面 x = 0 上に、高さ L の T 分で一周する観覧車がある。 xy 平面が水平で z が垂直。 0 分後の座標は 分後の座標は 分後の座標は 分後の座標は 銅像が にある。 以下の形式の質問が Q 個与えられるので順に求める。 …

競プロ典型90問 016(★3) 全探索

016 - Minimum Coins(★3) 問題 A円、B円、C円と硬貨が3種類ある。 それぞれ0枚以上使ってちょうどN円を支払うとき、使う硬貨の枚数の最小値を求める。 解法 そのまま全探索すると になり、TLEする。 そのためループを3重から2重へと減らす必要がある。 xと…

競プロ典型90問 014(★3) 貪欲法

014 - We Used to Sing a Song Together(★3) 問題 N人。家は にある。 学校は N校あり、 にある。 全員別の学校に通わせる。 学生 i の家から学校までの距離 , 不便さは距離の総和 である。 位置 u から位置 vまでの距離は 不便さの最小値を求める。 解法 …

競プロ典型90問 007(★3) 二分探索

007 - CP Classes(★3) 問題 N個のクラス、Q人の生徒。 クラスのレーティングは , 生徒のレーティングは と表す。 不満度は対象レーティングと自分のレーティングの差の絶対値。 各生徒の不満度の最小値を求める。 解法 Aをソートして 以上と未満の値の2つ…

競プロ典型90問 002(★3) next_permutation

002 - Encyclopedia of Parentheses(★3) 問題 長さNの正しいカッコ列を出力する。 条件 () は正しい。 Sが正しいとき、 ( + S + ) は正しい。 S,Tが正しいとき、文字列 S + T は正しい。 ( の方が ) よりも辞書順で早いものとする。 解法 まず奇数の場合は…

第2章 情報の表現と操作

データ・サイズ エンディアンとは? 論理処理とシフト演算 符号付きと符号なしキャスト 加算 乗算と除算 浮動小数点 IEEE浮動小数点表現 浮動小数点演算 感想 2章について この章では、コンピュータ上における数値の扱い方について詳しく書かれていました。 I…

第1章 コンピュータ・システム・ツアー

そもそもCSAPPとは? コンピュータ・システムとは? .cファイルからa.outを作成する システムのハードウェア構成 キャッシュの重要性 オペレーティング・システム 平行性と並列性 抽象化って? 感想 そもそもCSAPPとは? コンパイラやリンカ、メモリの仕組み…