第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++-5 -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++-5 -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