4/7 イントロダクション(Introduction)



講師紹介 成績評価

教科書


参考書/参考資料


授業日程
4/7
イントロダクション(Introduction)
4/14
イントロダクション(Introduction)(2)
4/21
配列ベースのリスト(Array-Based Lists)(1)
4/28
配列ベースのリスト(Array-Based Lists)(2)
5/12
連結リスト(Linked Lists)
5/19
スキップリスト
5/26
ハッシュテーブル(Hash Tables)
6/9
二分木(Binary Trees)
6/16
赤黒木(Red-Black Trees)
6/23
ヒープ(Heaps)
6/30
総合情報学特論と時間帯が重なるため休講
7/7
ソートのアルゴリズム(Sorting Algorithms)
7/14
グラフ,その他

講義スライド

講義で使ったスライド(PDF形式)はITC-LMSで公開予定.


リンク集

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

この演習では,Mac OS上で行なう.Windows環境が得意な人は,そちらで おこなっても良いが,サポートはしない(Visual C++よりも,cygwinのg++を 使った方がそのまま実施しやすいかもしれない). 以下の関数fは整数(int)を要素にするvectorにn回要素を追加(push_back)してn回要素を削除する何もしない関数(何もしないが,コンパイラの最適化で削除されることはないように工夫して いる)である.
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();
}
さまざまな,nを与えた時の実行時間を測るためのプログラム vector_speed.cpp をコンパイル実行してみる. なお,今後の演習では,ホームフォルダの下にmis2というフォルダを作って, そこで作業することを前提とする.
#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;
}
ターミナルを起動し,
cd ~/mis2
g++ -O2 -o vector_speed vector_speed.cpp
を実行し,「コンパイル」する.「-O2」は最適化のオプションで,速度計測を目的とする場合は,こ の程度の最適化レベルを用いる.コンパイルに成功したら,
./vector_speed 100000
を実行すると
cycle : 2639753
clock : 916
sec   : 0.000916
のように,表示される.なお,プログラム中で,時間を計らなくても,
time ./vector_speed 100000
のようにしても,
real	0m0.006s
user	0m0.001s
sys	0m0.003s
のように表示されるが,計測の精度は落ちるし,プログラムの一部のみを計測することはできない. プログラムの説明をする.

自習問題

  1. 上のプログラムを自分のMacで実行してみて,fに与えるnの値をどう変化させるかによって,実行時間がどう変わるかを考えて見て下さい.
  2. 自分のMacで実行してみて,clockとcycleの関係から,CPUの速度が何GHzなのかを推計してみてください.
  3. vectorに変えて,list, dequeを使うプログラムに書き換えてみて,同様に実行時間を計測してみてください.