第5章の演習

ソースのダウンロード

今後の演習では，ホームフォルダの下に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からダブルクリックしてもアーカイブユーティリティが立ち上がり展開されるので，そちらでも良い．

[投票]ハッシュテーブルを知っていた?

  1. 名前をこの講義で初めて知った
  2. 名前は聞いたことがあるが，どのようなものかは知らない
  3. どのようなものかは知っているが使ったことはない
  4. 他の人が作ったライブラリを使ったことがある．
  5. 自分で実装したことがある

[投票]次の中でハッシュテーブルを使って実装されているものは?(正解は複数)

  1. C++のmap
  2. C++のunordered_map
  3. Rubyの配列
  4. Pythonのdictionary(辞書)
  5. Javascriptのオブジェクト

演習(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++-8 -Wall  -o chainedHashTest chainedHashTest.cpp utils.cpp
でコンパイルし， 
./chainedHashTest
で実行する．
(注) 配布プログラムのChainedHashTableの実装では，要素が含まれていない時に， は，ChainedHashTableのメンバ変数nullを返すが，これがprotectedで保護されて いるため，比較することができない(実装を見ると，INT_MINを代入しているの で(Tがint以外の場合はいろいろと困ったことになるはず)，これと比較すること は可能だが)．上のプログラムでは，find(i)の結果がiの時は要素が含まれていると判断しているが，iがINT_MINの時には判断できない．

[投票]zに偶数を選ぶとどうなるか?

hash(x)=((z・x) mod 2w) div 2w-d
  1. hash(x)の値が常に同じ値になる
  2. hash(x)の値が常に偶数になる
  3. dがwと等しい時にhash(x)の値が常に偶数になる

演習(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++-8 -Wall  -o linearHashTest linearHashTest.cpp LinearHashTable.cpp utils.cpp
でコンパイルし， 
./linearHashTest
で実行する．
(注) 配布プログラムのLinearHashTableの実装では，型Tの中で明示的にnull, del に使う値を指定することができるようになっている．上のプログラムでは，要素がすべて正であることを利用して，nullを-1, delを-2にしている．
このプログラムを改造して，1000以下の素数の数を求めなさい．1000以下の素数はいくつになるか?
  1. 89
  2. 168
  3. 230
  4. 231
  5. 1000