マツシタのお勉強

キャッシュメモリの書き込み方式

キャッシュメモリの書き込み方式

キャッシュメモリへの書き込み方式には、ライトスルー方式ライトバック方式がある.

ライトスルー方式

プロセッサがメモリにデータを書き込む際、キャッシュと主記憶に同時に書き込む方式。 書き込み処理は高速化できない。

メリットとしては、キャッシュと主記憶の一貫性を保つことができる。

ライトバック方式

書き込みデータをキャッシュに一旦加え、あとでまとめて主記憶に書き込む。 メリットとして、主記憶へのアクセス頻度が減るので、書き込み時のメモリアクセスが高速化できる。

MIPS計算

MIPS計算

MIPSとは、プロセッサが1秒間に実行する命令数を百万単位(106)で表したもの。

問題

動作クロック周波数が700MHzのCPUで、目入れ実行に必要なクロック数及び、その命令の出現率が表に示す値である場合、このCPUの性能は約何MIPS

命令の種別 命令実行に必要なクロック数 出現率(%)
レジスタ間演算 4 30
メモリ・レジス間演算 8 60
無条件分岐 10 10

クロック(クロック周波数)とは

CPUが命令を処理する時のテンポのようなもの。クロック周波数が高ければ高いほど、一度に多くこのことができる。つまり性能が良いことになる。 今回の問題では、クロック周波数が700MHzのCPUなので、1秒間に700 * 106回クロックが打たれることになる。言い換えると1回のクロックは1/700*106秒で発生することになる。

表を見てみると、レジスタ間演算という命令を実行するのに必要なクロック数は4つ。これが30%の確率で行われる。今回は3つの命令が存在するので、このCPUでの命令実行に必要なクロック数の平均を出してみる。

命令実行に必要なクロック数の平均 = 4 * 0.3 + 8 * 0.6 + 10 * 0.1 = 7 クロック

今回の問題で問われていることは、このCPUが1秒間で何回の命令を実行できるかである。1回の命令で平均7クロック発生するので、クロック数が700MHzのCPUでは、

MIPS = 700 * 106 / 7 = 100 * 106 = 100MIPS

となる。

筋肉をつけるために

最近

細マッチョになりたくて筋トレをはじめました。 近所の市民ジム的な所でいそいそとやっています。

プロテインも買いました。ついでにシェーカーも。 牛乳で割ると案外美味しい。

スポーツドリンクの役割は水分補給だけじゃない

最近はじめて知ったのですが、スポーツドリンクの役割って水分補給だけじゃないらしいです。 たんぱく質とか入っているので、筋肉形成に繋がるらしいのです。

Binary Search Tree Iterator in LeetCode

問題

Binary Search Treeにおけるイテレータを実装する問題。next()メソッドで取得できる値は現時点での最小値となる。

Binary Search Tree Iterator - LeetCode

ソースコード

House robber ⅲ in LeetCode

問題

2分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。

条件

  • 直接つながれている隣同士のノードは取る事ができない。

House Robber III - LeetCode

解き方

それぞれのノードについて、そのノードの値を和に含めるか否かの2パターンを試し、最大値となる和を取得する。その際、同じ条件での探索が複数存在するのでメモ化することで計算量を抑えることができる。

ソースコード

My Simple and Clear Java Solution With Using Memoization | LeetCode Discuss

Insert Delete GetRandom O(1) - Duplicates allowed

問題

通常のHashTableの機能に加え、テーブル内の要素をランダムで返すメソッドを実装されているデータ構造を作る。データ構造内の要素は重複が許されており、重複した要素の数はランダムな要素を返す関数に影響する。

leetcode.com

ソースコード