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分木が与えられる。ノードは数値を持っていて以下の条件で数値の和が最大の値を見つける問題。
条件
- 直接つながれている隣同士のノードは取る事ができない。
解き方
それぞれのノードについて、そのノードの値を和に含めるか否かの2パターンを試し、最大値となる和を取得する。その際、同じ条件での探索が複数存在するのでメモ化することで計算量を抑えることができる。
ソースコード
My Simple and Clear Java Solution With Using Memoization | LeetCode Discuss
Serialize and Deserialize BST in LeetCode
Insert Delete GetRandom O(1) - Duplicates allowed
問題
通常のHashTableの機能に加え、テーブル内の要素をランダムで返すメソッドを実装されているデータ構造を作る。データ構造内の要素は重複が許されており、重複した要素の数はランダムな要素を返す関数に影響する。