第5章の演習

ソースのダウンロード

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

mkdir ~/mis2

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

cd ~/mis2
tar zxvf ods-cpp.tgz

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

cd ~/mis2
tar xvf ods-cpp.tar

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

配付プログラムの ChainedHashTable.h は

template
void ChainedHashTable<T>::resize() {
	d = 1;
	while (1<<d <= n) d++;
    n = 0;
	array<List> newTable(1<<d);
	for (int i = 0; i < t.length; i++) {
		for (int j = 0; j < t[i].size(); j++) {
			T x = t[i].get(j);
			newTable[hash(x)].add(x);
		}
	}
	t = newTable;
}

のように'n = 0' という謎の1行が含まれている．

template
void ChainedHashTable<T>::resize() {
	d = 1;
	while (1<<d <= n) d++;
//    n = 0;
	array<List> newTable(1<<d);
	for (int i = 0; i < t.length; i++) {
		for (int j = 0; j < t[i].size(); j++) {
			T x = t[i].get(j);
			newTable[hash(x)].add(x);
		}
	}
	t = newTable;
}

のように，この行はコメントアウトして使うこと．

演習(ChangedHashTable)

~/mis2/cpp 以下にchainedHashTest.cpp というファイルを作成する．これは，エラトステネスのふるいを使って，1000までの素数の集合を求めるプログラムである．なお，1000までの素数を保持するためのデータ構造としては，ハッシュよりもboolの配列，あるいはビットベクターを用いた方が空間効率，時間効率が良いので，お勧めはしない．　

#include "ChainedHashTable.h"

int main(){
  ods::ChainedHashTable<int> primes;
  for(int i = 2; i < 1000; i++){
    primes.add(i);
  }
  // primes = {2,3,4,...,999}
  for(int i = 2; i < 1000; i++){
    if(primes.find(i) == i){
      std::cout << i << std::endl;
      for(int j = i + i; j < 1000; j += i) primes.remove(j);
    }
  }
  // primes = {2,3,5,7,11,...,997}
}

これを，

cd ~/mis2/cpp
g++-mp-4.9 -Wall  -o chainedHashTest chainedHashTest.cpp utils.cpp

でコンパイルし，

./chainedHashTest

で実行する．
(注) 配布プログラムのChainedHashTableの実装では，要素が含まれていない時に，は，ChainedHashTableのメンバ変数nullを返すが，これがprotectedで保護されているため，比較することができない(実装を見ると，INT_MINを代入しているので(Tがint以外の場合はいろいろと困ったことになるはず)，これと比較することは可能だが)．上のプログラムでは，find(i)の結果がiの時は要素が含まれていると判断しているが，iがINT_MINの時には判断できない．

演習(LinearHashTable)

~/mis2/cpp 以下にlinearHashTest.cpp というファイルを作成する．

#include "utils.h"
#include "LinearHashTable.h"

int main(){
  const int null = -1;
  const int del = -2;
  ods::LinearHashTable<int> primes(null, del);
  for(int i = 2; i < 1000; i++){
    primes.add(i);
  }
  // primes = {2,3,4,...,999}
  for(int i = 2; i < 1000; i++){
    if(primes.find(i) != null){
      std::cout << i << std::endl;
      for(int j = i + i; j < 1000; j += i) primes.remove(j);
    }
  }
  // primes = {2,3,5,7,11,...,997}
}

これを，

cd ~/mis2/cpp
g++-mp-4.9 -Wall  -o linearHashTest linearHashTest.cpp LinearHashTable.cpp utils.cpp

でコンパイルし，

./linearHashTest

で実行する．
(注) 配布プログラムのLinearHashTableの実装では，型Tの中で明示的にnull, del に使う値を指定することができるようになっている．上のプログラムでは，要素がすべて正であることを利用して，nullを-1, delを-2にしている．

このプログラムを改造して，1000以下の素数の数を求めなさい．1000以下の素数はいくつになるか?

89
168
230
231
1000