第1章の演習

演習の環境について

ソースのダウンロード

mkdir ~/mis2

cd ~/mis2
tar zxvf ods-cpp.tgz

cd ~/mis2
tar xvf ods-cpp.tar

演習(C++プログラムの速度計測)

void f(std::vector<int> &v, int n){
  for (int i = 0; i < n; i++) v.push_back(i);
  for (int i = 0; i < n; i++) v.pop_back();
}

 
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <vector>

uint64_t cputime(){
  unsigned int ax,dx;
  asm volatile("rdtsc\nmovl %%eax,%0\nmovl %%edx,%1":"=g"(ax),"=g"(dx): :"eax","edx");
  return (uint64_t(dx)<<32)+uint64_t(ax);
}

void f(std::vector<int> &v, int n){
  for (int i = 0; i < n; i++) v.push_back(i);
  for (int i = 0; i < n; i++) v.pop_back();
}

int main(int ac, char **ag){
  int n = 1000;
  if (ac > 1) n = atoi(ag[1]);
  std::vector<int> v;
  clock_t clk1 = clock();
  uint64_t cpu1 = cputime();
  f(v, n);
  uint64_t cpu2 = cputime();
  clock_t clk2 = clock();
  std::cout << "cycle : " << cpu2 - cpu1 << std::endl;
  std::cout << "clock : " << clk2 - clk1 << std::endl;
  std::cout << "sec   : " << (double)(clk2 - clk1)/CLOCKS_PER_SEC << std::endl;
}

g++ -O2 -o vector_speed vector_speed.cpp

./vector_speed 100000

cycle : 2296824
clock : 658
sec   : 0.000658

time ./vector_speed 100000

real	0m0.011s
user	0m0.001s
sys	0m0.002s

• atoi 「char *」型のCの文字列から，整数(int)に変換するC言語の関数．
• clock
  OSの内部のclockの間隔(CLOCKS_PER_SEC, /usr/include/time.hに定義されている．MacOSのセンターに入っているバージョンでは1,000,000なので，1/1000000秒に1回増える)に基いたプロセス起動からの実行時間．OSによって計測の細かさが変わる．
• cputime()
  アセンブリ言語命令 rdtsc(read time scamp counter) を用いて，CPU1サイクルにつき1カウントアップされるカウンタを読み出す．

自習問題

1. 上のプログラムを自分の環境で実行してみて，fに与えるnの値をどう変化させるかによって，実行時間がどう変わるかを考えて見て下さい．
   • プログラムをみるとわかるように，コマンドラインの ./vector_speed の後ろに与える数字「例 100000」がfに与えるnになります．プログラムを修正して再コンパイルしなくても，この数字を変更して実行するだけで試すことができます
   • 数字を変化させて，繰り返し実験するにはコマンドライン上でプログラムをおこなう bash の機能で簡単に実行できます．以下は，nを10 - 1000000 まで変化させています．

     for n in 10 100 1000 10000 100000 100000 1000000; do echo $n; ./vector_speed $n; done
     

2. 自分の環境で実行してみて，clockとcycleの関係から，CPUの速度が何GHzなのかを1秒あたりの実行サイクル数で推計してみてください．
3. vectorに変えて，list, dequeを使うプログラムに書き換えてみて(プログラム中に出現する3つの"vector"を"list"あるいは"deque"に置き換える)，同様に実行時間を計測してみてください．
   • vector_speed.cpp を書き換えてしまうのは抵抗はあると思うので，

     cp vector_speed.cpp list_speed.cpp
     cp vector_speed.cpp deque_speed.cpp
     

     などとコピーして，list_speed.cpp, deque_speed.cpp を好きなテキストエディタで編集したあとで(vector_speed.cpp をテキストエディタで開いて，別名で保存しても同じです)，

     g++ -O2 -o list_speed list_speed.cpp
     ./list_speed 100000
     

     g++ -O2 -o deque_speed deque_speed.cpp
     ./deque_speed 100000
     

     などと実行してみます．

[投票]Priority QueueがあればFIFO, LIFO を実装できるか?

1. 両方実装できる
2. FIFOは実装できるがLIFOは実装できない
3. LIFOは実装できるがFIFOは実装できない
4. 両方実装できない

[投票]queueの中でスタック(stack)と呼ばれるのは?

1. FIFO (first-in-first-out) queue
2. Priority queue
3. LIFO (last-in-first-out) queue

[投票]次の中でUSet でなくSSet を使う必要があるのは?

1. 0から2⁶³-1までの数の集合について，ある数が集合の要素に含まれるかどうかを調べる．
2. 0から2⁶³-1までの数の集合について，最小の数を求める．
3. 0から2⁶³-1までの数の集合について，要素数を求める．

[投票]以下のうち正しいのは?

1. O(2n²) ⊆ O(n²)
2. O(1.01ⁿ) ⊆ O(n¹⁰⁰)
3. O(n^2.001) ⊆ O(n² log n)
4. O(n² log² n) ⊆ O(n² log n)

[投票]次の関数 f(n)について最も適切なO-記法で表わせ

1. O(n²)
2. O(n² log n)
3. O(n³)
4. O(n³ + n² log n)
5. O(n³ log n)

[投票]次の関数 f(n, m)について最も適切なO-記法で表わせ

1. O(n²)
2. O(n² log m)
3. O(n² log m + m)
4. O(n² log m + m + m log n)
5. O(n² log m + m log n)

[投票]確率変数X, Y に対してE[X * Y] = E[X] * E[Y] は成り立つ?

1. 成り立つ
2. 成り立たない
3. 一般には成り立たないが X, Y が独立なら成り立つ

[投票]次の環境のうちw-bit RAMのw=64と仮定するのが適当なものを選べ(正解複数)

1. iMac端末のWindows環境
2. iMac端末のMac環境
3. iPhone SE
4. 任天堂Switch
5. Apple Watch