第2章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下にmis2というフォルダを作って，そこで作業することを前提とする．作成していない時は，ターミナルから

mkdir ~/mis2

を実行する． http://opendatastructures.orgのc++ edition, c++ sources ( C++ sources(講義独自版) ) からダウンロードしたファイルをホームフォルダの下のmis2に置く．ods.cpp.tgzというファイルができた時は，

cd ~/mis2
tar zxvf ods-cpp.tgz

ods-cpp.tarというファイルができた時は，

cd ~/mis2
tar xvf ods-cpp.tar

を実行するとcppというフォルダができる．Finderからダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

演習(array)

~/mis2/cpp 以下にarrayTest.cpp というファイルができているはずである．

#include "array.h"
#include <iostream>

int main(){
  int n;
  std::cin >> n;
  ods::array<int> a(n);
  for (int i = 0; i < n; i++){
    a[i] = i * i; 
  }
  for (int m; std::cin >> m && m > 0;){
    if (m < n){
      std::cout << a[m] << std::endl;
    }
  }
  return 0;
}

これは，最初に入力した大きさの配列aを作り，n番目の中身をn*nで埋め，その後，入力されたmが正の間，aのm番目の要素を返すだけのプログラムである．これを，

cd ~/mis2/cpp
g++-5 -o arrayTest -O3 arrayTest.cpp array.cpp

でコンパイルし，

./arrayTest

で実行

のような入力を与えて実行してみる．

[演習/投票]第2章の演習のページの「演習(array)」をやってみる．

以下の入力を与えた時の出力は?

「9, 100, 1, 4」の4行
プログラムが異常終了する
「9,4」の2行
9

ヒント: 入力をファイル(たとえば array.in )に入れて，

./arrayTest < array.in > array.out

のように，出力もファイルに入れると入力と出力を区別しやすい

発展

array.h, array.cpp を読んで， arrayTest.cppの中で使われていなかった関数を探しなさい． arrayTest.cppを改造してこれらの関数を呼び出して動くことを確かめなさい．また， array.hの実装でメモリーリーク(今後，使われないのにメモリ上に存在し続ける領域) がないかどうか，実験するコードを書いてみてください．

[投票]下のプログラムの問題点は?

void add(int i, T x) {
  if (n + 1 > a.length) resize();
  for (int j = i; j < n; j++)
    a[j + 1] = a[j];
  a[i] = x;
  n++;
}

問題ない
aの範囲外にアクセスしてしまう
無限ループに入ってしまい終了しない
addしたい要素(x)が書き込まれない．
元からあった要素が失われてしまう．

[投票]以下の問いに答えよ?

if (a.length >= 3 * n) resize();

remove()のプログラムの上の行を削除して，remove()ではshrinkしないことにした時に，空のArrayStackからm回のadd, removeを任意の順序で実行した時のresizeの総実行時間は?

O(m)
O(m log n)
O(m log m)
O(m2)
O(1)

演習(ArrayStack)

~/mis2/cpp 以下にarrayStackTest.cpp というファイルができているはずである．

#include "ArrayStack.h"
#include <iostream>

int main(){
  int n = 100;
  ods::ArrayStack<int> as;
  for (int i = 0; i < n; i++){
    as.add(i, i); 
  }
  as.set(88, 199);
  as.add(87, 133);
  std::cout << as.remove(98) << std::endl;
  for (int i = 0; i < 80; i++){
    std::cout << "removed = " << as.remove(0) << std::endl;
  }
  for (int i = 0; i < as.size(); i++){
    std::cout << "as.get(" << i << ")=" << as.get(i) << std::endl;
  }
  return 0;
}

cd ~/mis2/cpp
g++-5 -o arrayStackTest -O3 arrayStackTest.cpp ArrayStack.cpp

でコンパイルし，

./arrayStackTest

で実行

発展

addやremoveはiによって，実行時間のオーダが違う． ~/mis2/cpp 以下にarrayStackSpeed.cpp というファイルができているはずである．

cd ~/mis2/cpp
g++-5 -o arrayStackSpeed -O3 arrayStackSpeed.cpp

でコンパイルし，

./arrayStackSpeed

で実行する．プログラム中のnの値を1000, 10000 に変更してからコンパイル実行してみる．

[演習]第2章の演習のページの「演習(ArrayStack) 」を発展までやってみる．

n=100 という行をn=10000 に変更した時に実行サイクルは何倍位に変わるか最も近い(桁が合う程度)ものを選びなさい

cycle(1), cycle(2)共に変わらない
cycle(1), cycle(2) 共に約100倍
cycle(1)は約100倍，cycle(2)は約1000倍
cycle(1)は約100倍，cycle(2)は約10000倍

演習(FastArrayStack)

~/mis2/cpp 以下にarrayStackTest.cpp というファイルができているはずである．FastArrayStackを使うように書き換えて fastArrayStackTest.cpp というファイルを作成する．

cd ~/mis2/cpp
g++-5 -o fastArrayStackTest -O3 fastArrayStackTest.cpp

でコンパイルし，

./fastArrayStackTest

で実行する．

発展

addやresizeはiによって，実行時間のオーダが違う． ~/mis2/cpp 以下にfastArrayStackSpeed.cpp というファイルができているはずである．

cd ~/mis2/cpp
g++-5 -o fastArrayStackSpeed -O3 fastArrayStackSpeed.cpp

でコンパイルし，

./fastArrayStackSpeed

で実行する．プログラム中のnの値を10000 に変更してからコンパイル実行してみる．

[演習]第2章の演習のページの「演習(FastArrayStack)」を発展までやってみる．

n=10000 とした時，ArrayStackと比べると実行時間(r2)はどの位短いか? 近いものを答えなさい(実行環境によるので正解はない)

ほぼ同じ
2/3程度
1/2程度
1/4程度
1/8程度
1/16以下

演習(ArrayQueue)

~/mis2/cpp 以下にarrayQueueTest.cpp というファイルができているはずである．

#include "ArrayQueue.h"
#include <iostream>

int main(){
  int n = 10;
  ods::ArrayQueue<int> aq;
  for (int i = 0; i < n; i++){
    aq.add(i); 
  }
  for (int i = 0; i < n * 10; i++){
    std::cout << aq.remove() << std::endl;
    aq.add(i * i); 
  }
  return 0;
}

cd ~/mis2/cpp
g++-5 -o arrayQueueTest arrayQueueTest.cpp ArrayQueue.cpp

でコンパイルし，

./arrayQueueTest

で実行する．

演習(ArrayDeque)

~/mis2/cpp 以下にarrayDequeTest.cpp というファイルができているはずである．

#include "ArrayDeque.h"
#include <iostream>

int main(){
  int n = 10;
  ods::ArrayDeque<int> aq;
  for (int i = 0; i < n; i++){
    aq.add(i, i); 
  }
  for (int i = 0; i < n; i++){
    aq.add(i, -i); 
    aq.remove(0);
    aq.set(i, i * i);
  }
  for (int i = 0; i < aq.size(); i++){
    std::cout << aq.get(i) << std::endl;
  }
  return 0;
}

cd ~/mis2/cpp
g++-5 -o arrayDequeTest arrayDequeTest.cpp ArrayDeque.cpp

でコンパイルし，

./arrayDequeTest

で実行する．

演習(DualArrayDeque)

~/mis2/cpp 以下にarrayDequeTest.cppを，DualArrayDequeを使うように書き換えて dualArrayDequeTest.cpp というファイルを作成する．

cd ~/mis2/cpp
g++-5 -o dualArrayDequeTest dualArrayDequeTest.cpp DualAraryDeque.cpp

でコンパイルし，

./dualArrayDeque

で実行する．

[投票]以下の問いに答えよ?

DualArrayDequeで，add, removeの後にbalance()を全く呼び出さない実装にした時に，効率が悪くなるような呼び出しの列はどれか? 最初に，空の要素が入っているとする．

add(0, x), add(1, x), ..., add(n, x), remove(n), remove(n-1),...,remove(0)
add(0, x), add(1, x), ..., add(n, x), remove(0), remove(0),...,remove(0)
add(0, x),remove(0),add(0, x), remove(0), ..., add(0, x), remove(0)
add(0, x),add(1, x),remove(0),remove(1),add(0, x),add(1, x),remove(0),remove(1),......

演習(RootishArrayStack)

~/mis2/cpp 以下のarrayStackTest.cppを，RootishArrayStackを使うように書き換えて rootishArrayStackTest.cpp というファイルを作成する．

cp arrayStackTest.cpp rootishArrayStackTest.cpp

を実行した後，作成されたrootishArrayStackTest.cpp をエディタで編集し，

#include "ArrayStack.h"
->
#include "RootishArrayStack.h"
-----
  ods::ArrayStack<int> as;
->
  ods::RootishArrayStack<int> as;

の書きかえをおこない，

g++-5 -Wall -O3 -o rootishArrayStackTest rootishArrayStackTest.cpp

でコンパイル．

./rootishArrayStackTest

で実行する．

次にRootishArrayStack.hの先頭に

#include <iostream>

を入れ，以下の赤字の2行を加えてみる．

template<class T>  
void RootishArrayStack<T>::grow() {
  std::cerr << "grow() is called" << std::endl;
    blocks.add(blocks.size(), new T[blocks.size()+1]);
}
template<class T>
void RootishArrayStack<T>::shrink() {
  std::cerr << "shrink() is called" << std::endl;
    int r = blocks.size();
    while (r > 0 && (r-2)*(r-1)/2 >= n) {
            delete [] blocks.remove(blocks.size()-1);
            r--;
    }
}

[演習]第2章の演習のページの「演習(RootishArrayStack)」をやってみる．

rootishArrayStackTest を実行した時に，grow, shrinkは何回呼ばれるか?

0, 0
4, 8
8, 4
7, 14
14, 7