マージ

２つのソート済み配列を一つの配列にマージし，ソートするコードは以下の通り．厳密にはマージソートと全く異なるので注意．

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

void dump(const vector<int> v) {

 vector<int>::const_iterator iter;
 for( iter = v.begin(); iter != v.end();iter++ )
  cout << *iter << ' ';
 cout << endl;

}

void merge(const vector<int>& arr1, const vector<int>& arr2, vector<int>& merged) {

 int i,j;
 i = j = 0;
 while( i < arr1.size() && j < arr2.size() ) {
  if( arr1.at(i) <= arr2.at(j) )
   merged.push_back( arr1.at(i++) );
  else
   merged.push_back( arr2.at(j++) );
 }
 while( i < arr1.size() )
  merged.push_back( arr1.at( i++ ) );
 while( j < arr2.size() )
  merged.push_back( arr2.at( j++ ) );

}

int main() {

 vector<int> v1;
 vector<int> v2;
 vector<int> merged;
 v1.push_back(3);
 v1.push_back(5);
 v1.push_back(7);
 v2.push_back(1);
 v2.push_back(2);
 v2.push_back(3);
 v2.push_back(7);
 v2.push_back(9);
 merge(v1,v2,merged);
 dump(merged);

}

マージソート

マージソートを書いてみてください，というのは私が面接官をするときに必ず聞いている質問の一つ．というわけでマージソートである．

最初からソートした２つの配列を１つにする答えをもらえれば，及第点ではあるが，以下のようにソートされていない１つの配列を文字通りソートするアルゴリズムの答えであれば，満点である
．

#include <iostream>
#include <array>
#include <cmath>
using namespace std;

#define ARRAY_SIZE 8

void init(array<int,ARRAY_SIZE>& a) {

 a[0] = 10; a[1] = 5; a[2] = 3; a[3] = 6;
 a[4] = 6; a[5] = 9; a[6] = 15; a[7] = 1;
}

void dump(array<int,ARRAY_SIZE>& a) {

 for( int i =0;i < a.size();i++ )
  cout << a.at(i) << ' ';
 cout << endl;
 
}

void mergesort(array<int,ARRAY_SIZE>& arr) {
 
 int divider = 2;
 int compartment;
 int t;
 while( divider <= ARRAY_SIZE ) {
  compartment = ARRAY_SIZE / divider;
  for( int i = 0;i < compartment;i++ ) {
   for( int j = i * divider;j < divider;j++ ) {
    for( int k = j + 1;k < divider;k++ ) {
     if( arr[j] > arr[k] ) {
      t = arr[j];
      arr[j] = arr[k];
      arr[k] = t;
     }
    }
   }
  }
  divider *= 2;
 }
}

int main() {
 array<int,ARRAY_SIZE> arr;
 init(arr);
 dump(arr);

 mergesort(arr);
 dump(arr);
}

実行結果は以下の通り

10 5 3 6 6 9 15 1
1 3 5 6 6 9 10 15

vectorのリサイズによるアドレスの変更？

SafeC++にはvectorに要素が多く積み込まれると，リサイズ(デフォルトサイズは恐らく１６)により，ベクタは他のメモリアドレス上にコピーを作りそこにデータをコピーする，とあった．それが本当であるならば，コンポジションクラス中のvector参照メンバ及びポインタメンバはリサイズが発生した場合，無効になるわけである．

本当だろうか？検証してみた．

以下のコードはvector参照メンバ v をクラスにセットして，vにデータを積み込む単純なコードである．データ積み込みの前と後で番地の値を取得し，かつsize()を呼んでいる．

結果はデータ積み込み前と後でアドレスは一緒，size()も無事動作した．
ちなみにg++は4.7.3, OSはFedora18. Visual Studioは2010, OSはWindows7 32bit．

#include <vector>
#include <iostream>
using namespace std;

class MyClass {
private:
 vector<int>& v;
public:
 MyClass(vector<int>& vParam) : v(vParam) {}
 const vector<int>& GetV() { return v;}
 
 void Init() {

  for(int i = 0;i < 10;i++ ) {
   v.push_back(i);
  }
 }
 
 void Expand() {

  for(int i = 0;i < 50000;i++ ) {
   v.push_back(i);
  }
 }
 
 int size() {
  return v.size();
 }

};

int main() {

 vector<int> v;
 v.resize(20);
 
 MyClass m(v);
 m.Init();
 cout << &(m.GetV()) << m.size() << endl;
 m.Expand();
 cout << &(m.GetV()) << m.size() << endl;

}

結果

0x22ac5430
0x22ac5450030

C/C++のタイマー

#include <iostream>
#include <ctime>
#include <unistd.h>
using namespace std;

int main() {

 clock_t st = clock();
 for( long l = 0;l < 100000000;l++ );
 clock_t end = clock();
 cout << st << ":" << end << endl;
 cout << "elapsed - " << (end - st) * 1000 / CLOCKS_PER_SEC << endl;
 return 0;

}

自作クラスの比較オペレータを効率的に定義する方法

以下のアイデアはSafe C++で紹介されている．

#include <iostream>
using namespace std;

class MyClass {
private:
 int price;
public:
 explicit MyClass(int priceParam) : price(priceParam) {}
 int CompareTo(const MyClass& a) const {
  if( price == a.price )
   return 0;
  else if( price < a.price )
   return -1;
  else
   return 1;
 }

#define CMP(Class) \
 bool operator < (const Class& that) const { return CompareTo(that) < 0; } \
 bool operator > (const Class& that) const { return CompareTo(that) > 0; } \
 bool operator == (const Class& that) const { return CompareTo(that) == 0; } \
 bool operator <= (const Class& that) const { return CompareTo(that) <= 0; } \
 bool operator >= (const Class& that) const { return CompareTo(that) >= 0; } \
 bool operator != (const Class& that) const { return CompareTo(that) != 0; }

 CMP(MyClass);


};

int main() {

 MyClass A(32),B(60),C(32);
 if( A == C )
  cout << "A == C" << endl;
 if( B > A )
  cout << "B > A." << endl;
 if( A < B )
  cout << "A < B." << endl;
 if( A != B )
  cout << "A != B." << endl;

}

gcc/g++でスレッドをスリープさせる

#include <pthread.h>
#include <unistd.h>
#include <cstdio>

void *run(void *p) {
 int t = *(static_cast<int*>(p));
 printf("sleeping %d seconds..\n",t);
 sleep(t); // unit is msec
 pthread_exit(NULL);
}

int main() {

 pthread_t th;
 void* th_result;
 int duration = 2;
 pthread_attr_t attr;
 pthread_attr_init(&attr);
 pthread_attr_setdetachstate(&attr,PTHREAD_CREATE_JOINABLE);
 pthread_create(&th,&attr,run,&duration);
 pthread_attr_destroy(&attr);
 pthread_join(th,&th_result);
 pthread_exit(NULL);

}

Pthread

Ptheadとmutexのサンプルコードを書いてみた．．

#include <iostream>
#include <sstream>
#include <pthread.h>
#include <cstdlib>
#include <unistd.h>
using namespace std;


class Account {
private:
 long _balance;
 pthread_mutex_t mutex;
public:
 explicit Account(long balance): _balance(balance) { pthread_mutex_init(&mutex,NULL); }
 virtual ~Account() { pthread_mutex_destroy(&mutex);}
 void Deposit(long val);
 long Withdraw(long val);
 friend ostream& operator << (ostream& os, const Account& acct);
};

inline ostream& operator << (ostream& os, const Account& acct) {
 os << acct._balance;
 return os;
}

typedef struct {
 Account* a;
 Account* b;
} Accts;

void Account::Deposit(long val) {

 pthread_mutex_lock(&mutex);
 _balance += val;
 pthread_mutex_unlock(&mutex);

}

long Account::Withdraw(long val) {

 pthread_mutex_lock(&mutex);
 _balance -= val;
 pthread_mutex_unlock(&mutex);
 return val;

}

void* PerformDrawer(void* param) {

 Accts* acct = static_cast<Accts*>(param);
 long l = 0;
 for( int i = 0;i < 50;i++ ) {
  cout << "[W" << i << "]:Draw money 300 from A and deposit the money into B.. " << endl;
  l = acct->a->Withdraw(300);
  acct->b->Deposit(l);
  cout << "current balances - A:" << *(acct->a) << ",B:" << *(acct->b) << endl;
  sleep(1);
 }
 
}

void* PerformDepositter(void* param) {

 Accts* acct = static_cast<Accts*>(param);
  for( int i = 0;i < 50;i++ ) {
  cout << "[D" << i << "]:Deposit money 500 into A.. " << endl;
  acct->a->Deposit(500);
  cout << "current balances - A:" << *(acct->a) << ",B:" << *(acct->b) << endl;
  sleep(1);
 }
}

void InitThreadAttr(pthread_attr_t* attr) {
 pthread_attr_init(attr);
 pthread_attr_setdetachstate(attr,PTHREAD_CREATE_JOINABLE);
}

int main() {

 pthread_t depositter;
 pthread_t withdrawer;
 void *status_depositter;
 void *status_withdrawer;
 
 Account A(4000);
 Account B(2000);
 Accts accts;
 accts.a = &A;
 accts.b = &B;
 pthread_attr_t attr;

 InitThreadAttr(&attr);
 
 pthread_create(&depositter, &attr,PerformDepositter,(void *)&accts);
 pthread_create(&withdrawer, &attr,PerformDrawer,(void *)&accts);
 pthread_attr_destroy(&attr);
 pthread_join(depositter, &status_depositter);
 pthread_join(withdrawer, &status_withdrawer);
 
 cout << "A:" << A << endl;
 cout << "B:" << B << endl;

 pthread_exit(NULL); 

}

実行結果は以下の通り
(途中略)

[D46]:Deposit money 500 into A..
current balances - A:13700,B:15800
[W46]:Draw money 300 from A and deposit the money into B..
current balances - A:13400,B:16100
[D47]:Deposit money 500 into A..
current balances - A:13900,B:16100
[W47]:Draw money 300 from A and deposit the money into B..
current balances - A:13600,B:16400
[D48]:Deposit money 500 into A..
current balances - A:14100,B:16400
[W48]:Draw money 300 from A and deposit the money into B..
current balances - A:13800,B:16700
[D49]:Deposit money 500 into A..
current balances - A:14300,B:16700
[W49]:Draw money 300 from A and deposit the money into B..
current balances - A:14000,B:17000
A:14000
B:17000

プチクイズ 6 - コンストラクタの例外

Q. 何故コンストラクタが例外を送出するのは良くないのか，理由を述べよ．

A. もしコンストラクタの処理最中で例外が送出された場合，デスクトラクタは呼ばれない．その結果メモリリークが発生する可能性がある．

ただし，safe C++ではスマートポインタを使って，更にデストラクタを空にしたならば，むしろコンストラクタから例外を投げることも悪くはないと述べている．

プチクイズ 4 - std::vectorの要素アクセス

Q. std::vectorのat()とオペレータ[]の違いを述べよ

A. オペレータ[]での要素アクセスのほうが早いがout_of_range例外を投げない．
一方at()はout_of_range例外を投げる．

C++ - 自作クラスをcoutに<<オペレータで出力

自作のクラスを cout に<<オペレータで出力できると色々便利である．

以下のコードでそれを実現できるが，コンパイラによっては以下のコードはコンパイル出来ない．例えばg++はOKだがvc++10ではコンパイルに失敗する．

#include <iostream>
#include <string>
using namespace std;

class MyClass {
private:
 string name;
public:
 MyClass(const string s): name(s){}
 friend ostream& operator << (ostream& os, const MyClass& obj);

};

inline ostream& operator <<(ostream& os, const MyClass& obj) {
 os << obj.name;
 return os;
}

int main() {

 MyClass m("otter");
 cout << "Dump myclass -- " << m << endl;
 return 0;
}

UNIXコマンド One liner 5

過去に実行したg++を実行する ( !xxx ではなく．かなり意味なし )

touch temp;history|egrep -E '.*g\+\+ -o'|\
awk -e {'print $2,$3,$4,$5'}|tail -1 > ./temp;\
chmod 755 ./temp;./temp;rm ./temp

プチクイズ 3 - C++の列挙型

Q.

以下のC++コードのリファクタリングすべき点を述べよ．

enum { ELEM1, ELEM2 } ENUM_1;
enum { SUN, MON, TUE, WED, THU, FRI, SAT };

void ShowEnumVal(int e) {
    cout << e << endl;
}

A.

列挙体に関しての2つのDON'Tを直す必要がある．
１つはplain vanilla enumを使用している点，２つは関数がEnum型ではなくintを引数の型としている点である．
上記コードはコンパイルもランタイムも問題なく動くが，非常にリスクの大きいコードである．
なぜなら関数ShowEnumVal()は本来，オブジェクトとして全くことなる(として扱うべき)２つのEnumを受け入れてしまう点である．各enumはtypedefを用いてコンパイルに明示的に違う型のように扱ってもらうべきであり，関数ShowEnumVal()も，その関数が扱うべきenumオブジェクトだけを受け入れるべきである．
上記２点を修正したコードは以下の通り．

typedef enum { ELEM1, ELEM2 } ENUM_1;
typedef enum { SUN, MON, TUE, WED, THU, FRI, SAT } DAY_OF_WEEK;

void ShowEnum1Val( ENUM_1 e ) {

 cout << e << endl;

}

アルゴリズム問題を解く 12 - 最頻単語のリスト

問題

You are reading a sequence of strings separated by white
space from a very large stream. You are allowed to read the stream twice.
Devise an algorithm that uses only O(k) memory to identify all the words
that occur more than [n/k] times in the stream, where n is the length of the stream.
( Algorithms for interviewsより引用)

ヒント

今度は最頻出する複数の単語を調べる必要がある．しかも決められた O(k) メモリ しか利用できない．固定長のディクショナリがいいだろう．

解答

ヒントで述べたとおり，固定長のディクショナリを使う．固定長ゆえ，閾値 k 以上のエントリが入ってきた場合は最も少ない出現数のエントリをスイープする．
以下の解答は出現回数も表示するが，必ずしも正しい数字ではない．なぜなら，最終的に最頻となったエントリが計算中にスイープされている可能性があるからである．
もしO(k)メモリの縛りがなければ，スイープ無しにディクショナリを構築後，頻度の多い順にソート，上からm番目までを表示するといいだろう．ちなみに計算量はO(N)の定数時間である．

入力ファイル，入力ファイル読み込みのロジックは前回と同じ．
追加したコードは以下の通り．

void Sweep(map<string,int>* dict) {

 set<string> toRemove;

 map<string,int>::iterator iter;
 for( iter = dict->begin(); iter != dict->end();iter++ ) {
  iter->second--;
  if( !iter->second ) 
   toRemove.insert(iter->first);
 }
 set<string>::iterator sIter;
 for( sIter = toRemove.begin(); sIter != toRemove.end(); sIter++ ) {
  if( dict->find(*sIter) != dict->end() )
   dict->erase(*sIter);
 }

}

void GetPopularWords(const vector<string> v, map<string,int>* dict, int k) {

 cout << "GetPopularWords()" << endl;
 
 vector<string>::const_iterator iter;
 for( iter = v.begin(); iter != v.end();iter++ ) {
  
  if( dict->find(*iter) != dict->end() ) {
   if( dict->size() > k )
    Sweep( dict );
   else
    (*dict)[*iter] = (*dict)[*iter] + 1;
  }
  else
   (*dict)[*iter] = 1;
 }

}

アルゴリズム問題を解く 11 - 最頻単語の検索

問題

You are reading a sequence of words from a very long
stream. You know a priori that more than half the words are repetitions of
a single word W but the positions where W occurs are unknown. Design
an efficient algorithm that reads this stream only once and uses only a
constant amount of memory to identify W.
( algorithms for interview より引用)

ヒント

"A priori"を自分に有利なように解釈するのもテクニックのひとつ．

解答

ここではWの出現条件が以下を満たすものとする

• Wが最初から現れることもある
• Wがストリームスナップショットの半分以上を占める

以上の前提に基づくと，W最初からストリームスナップショットの最後まで50%以上の確率で現れることになるので，ストリームの最初からある任意の位置Mまでサンプリングを行えばほぼ確実にWを推定できる．以下のコードのAssumeMajority()はより正確性を求め，ストリームスナップショット全体をサンプリングする - O(N)．一方AssumeMajority2()は先頭から５番目の要素までサンプリングをする - O(5)．

#include <iostream>
#include <fstream>
#include <string>
#include <cstring>
#include <vector>
using namespace std;

static const string FILE_PATH = "C:\\tmp\\data\\rec.txt";

void ReadFile(string& buf, string path) {

 ifstream fin(path.c_str());
 char ch;
 while( fin.good() ) {
  fin.get(ch);
  if( fin.good() )
   buf += ch;
 }
 cout << "Data loaded from " << FILE_PATH << endl;
 
}

void tokenize(vector<string>& v,const string str) {

 char *pch;
 pch = strtok(const_cast<char*>(str.c_str())," ");

 while( pch != NULL ) {
  
  v.push_back( pch );
  pch = strtok(NULL," ");

 }

}

string* AssumeMajority(const vector<string>& v) {

 cout << "@AssumeMajority()" << endl;
 int count = 0;
 vector<string>::const_iterator iter;
 string* cand = new string();
 for(iter = v.begin(); iter != v.end();iter++) {
  if( !count ) {
   *cand = *iter;
   cout << "current candidate is " << *cand << endl;
   count = 1;
  }
  else if( *iter == *cand )
   count++;
  else
   count--;
 }
 
 return cand;
 
}

string* AssumeMajority2(const vector<string> v) {

 cout << "@AssumeMajority2()" << endl;
 const int sampleMax = 5;
 int count = 0;
 string *cand = new string();
 for(int i = 0;i < sampleMax;i++ ) {
  if( !count ) {
   *cand = v[i];
   cout << "current candidate is " << *cand << endl;
   count = 1;
  }
  else if( v[i] == *cand )
   count++;
  else
   count--;
 }

 return cand;

}

void dump(const vector<string>& v) {

 vector<string>::const_iterator iter;
 for(iter = v.begin(); iter != v.end();iter++) {
  cout << *iter << " ";
 }
 cout << endl;

}

int main() { 

 string s;
 ReadFile(s,FILE_PATH);
 vector<string> v;
 tokenize(v,s);
 dump(v);
 string* pch = AssumeMajority(v);
 cout << "Majority would be .. " << *pch << endl;
 delete pch;
 pch = AssumeMajority2(v);
 cout << "Majority would be .. " << *pch << endl;
 delete pch;

 return 0;
}

入力ファイル 中身

202 200 200 200 404 200 200 200 200 200 404 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 200 404 200

アルゴリズム問題を解く 10 - ハッシュで検索

問題

Given an array A of integers, find an integer k that is not present in A.
Assume that the integers are 32-bit signed integers.
( Algorithms for Interviews より引用 )

ヒント

ハッシュの写像．

解答

#include <iostream>
#include <vector>
using namespace std;

static const int MAX = 100;

void InitList(vector<int>& v) {

 v.push_back(32);
 v.push_back(55);
 v.push_back(11);
 v.push_back(42);
 v.push_back(98);
 v.push_back(51);
 v.push_back(80);
 v.push_back(6);

}

void BucketSort(vector<int>& dest, const vector<int>& src) {

 dest.resize(MAX);
 for( int i = 0;i < MAX;i++ )
  dest[i] = false;
 for( vector<int>::const_iterator iter = src.begin();iter != src.end();iter++ ) {
  dest[*iter] = true;
 }
}

bool found(const vector<int> A, int k) {

 vector<int>::const_iterator iter;
 return A[k];
 
}

int main() {

 vector<int> v;
 vector<int> sorted;
 InitList(v);
 BucketSort(sorted,v);
 cout << found(sorted,42) << endl;
 cout << found(sorted,44) << endl;

 return 0;
}

プチクイズ2 - コンポジションクラスの初期化

Q

const修飾子のついたメンバ，参照指定のメンバ，オブジェクトメンバ．これらをJavaの方法と同様な初期化をコンストラクタ中で行うことはできるか？

A

出来ない．コンパイラからお叱りをうけるだけである．
以下のコードはコンパイルでも実行時でも問題ない．

#include <iostream>
#include <sstream>
using namespace std;


class InnerObject { 
private:
 int id;
public:
 InnerObject(int paramId):id(paramId){ cout << "InnerObject init " << id << endl; }
 int GetId() { return id; }
};

class MyClass {
private:
 const char* str;
 int& r;
 InnerObject in;
public:
 MyClass(const char* paramStr, int& paramR, InnerObject paramIn ):
  str(paramStr),r(paramR),in(paramIn) {
   cout << "MyClass init " << endl;
  }
 void dump();
};

void MyClass::dump() {

 ostringstream os;
 os << "str:" << str << " ";
 os << "r:" << r << " ";
 os << "In's Id:" << in.GetId() << endl;
 cout << os.str().c_str() << endl;
 
}


int main() {

 InnerObject in(20);
 string s("neko");
 int r = 3;
 MyClass m("abc",r,in);
 m.dump();

 return 0;

}

Algorithm問題を解く 9 - 複数タグのマッチ判定

問題

You are building a social networking site where each user specifies a set of attributes. You would like to pair each user with another unpaired user that specifies exactly the same set of attributes. Specifically, you are given a sequence of users where each user has a unique key, say a 32-bit integer and a set of attributes specified as a set of strings. As soon as you read a user, you should pair it with another previously read user with identical attributes who is currently unpaired, if such a user exists. If the user cannot be paired, you should keep him in the unpaired set.

(Algorithms for interviewsより引用)

ヒント

文字列の一致でハッシュを使うのは，原則的にはご法度である．アナグラムのケースがあった場合プログラムは誤作動してしまう．

解答

#include <iostream>
#include <string>
#include <map>
#include <list>
#include <algorithm>
using namespace std;

class User {
private:
 int id;
 list<std::string> attrs;
 list<int> matchedIds;
 const std::string GetFullTag();
public:
 User() {}
 User(int paramId,list<std::string>& paramAttr) : id(paramId),attrs(paramAttr) {};
 virtual ~User() {};
 bool match(User& user);
};

const std::string User::GetFullTag() {

 string s = "";
 attrs.sort();
 list<std::string>::iterator iter;
 for(iter = attrs.begin();iter != attrs.end();iter++) {
  s.append( *iter );
 }
 return s;

}

bool User::match(User& user) {

 if( std::find(matchedIds.begin(), matchedIds.end(), user.id) == matchedIds.end() ) {
  
  if( GetFullTag() == user.GetFullTag() ) {
   matchedIds.push_back(user.id);
   return true;
  }
  else
   return false;

  return false;

 }
 else {
  // already matching
  cout << "already in your list!!" << endl;
  return true;
 }
 return true;
}

int main() {
 
 list<string> my;
 my.push_back("C++");
 my.push_back("Java");
 User s( 10, my );
 list<string> you;
 you.push_back("Java");
 you.push_back("C++");
 User u( 20, you );
 cout << "you and me - " << s.match( u ) << endl;
 list<string> t;
 t.push_back("C++");
 t.push_back("Java");
 User th( 30, t );
 cout << "someone and me - " << s.match( th ) << endl;
 list<string> b;
 b.push_back("Python");
 b.push_back("Java");
 User br( 40, b );
 cout << "brother and me - " << s.match( br ) << endl;

 return 0;
}

プチクイズ1 .. JavaのUnsigned型

プチクイズ1


Q.

Javaでの唯一のUnsignedの型は？

A.

char. Byteでさえもsignedである．Javaの設計者はunsignedなんて必要ないと言い切った．正直あったらあったで便利だし，なくても全くなんとかなっているのが個人的な実情である．

Algorithm問題を解く 8 - ハッシュ2

問題

You are required to write a method that takes two text documents: an anonymous letter L and text from a magazine M. Your method is to return true if L can be written using M and false otherwise.
(if a letter appears k times in L, it must appear at least k times in M. )
(Algorithm for interviewsより引用)

ヒント

マガジンMから部分文字列Lを取り出せという問いではないことに注意．

解答

#include <string>
#include <iostream>
#include <map>
using namespace std;

class Dict {
private:
 map<char,int> mD;
 void AddOrIncrement(char ch);
public:
 Dict() {};
 bool Analyze(string l,string m);
};

void Dict::AddOrIncrement(char ch) {
 if( mD.find(ch) != mD.end() )
  mD[ch]++;
 else
  mD[ch] = 1;
}

bool Dict::Analyze(string l, string m) {

 mD.clear();

 for( unsigned int i = 0;i < m.size();i++ ) {
  AddOrIncrement(m.at(i));
 }
 for( unsigned int i = 0;i < l.size();i++ ) {
  mD[l.at(i)]--;
  if( mD[l.at(i)] < 0 )
   return false;
 }
 return true;

}


int main() {

 Dict d;
 cout << d.Analyze("wanco", "wanchan coco ni oide") << endl;
 cout << d.Analyze("nyanco", "wanchan coco ni oide") << endl;

 return 0;

}

Algorithm問題を解く 7 - Hashキーで検索

問題

Let A be a sorted array of integers and S a target integer.

Design an efficient algorithm for determining if there exist
a pair of indices i,j (not ncessarily distinct) such that A[i] + A[j] = S.
( Algorithms for interview より引用 )

ヒント

sorted array .. ２分探索？２分探索でも勿論解ける．しかしバイナリサーチより効率の良いアルゴリズムは？

解答1

適当にループで回してもO(N^2)で解を出すことはできるが，もう一工夫．
バイナリサーチで検索の範囲を狭めれば良くてO((N/2)^2)，悪くてO(N^2)となる．

#include <iostream>
#include <vector>
#include <map>
using namespace std;

void init_vector(vector<int>& v) {
 v.push_back( 5 );
 v.push_back( 8 );
 v.push_back( 12 );
 v.push_back( 20 );
 v.push_back( 33 );
 v.push_back( 45 );
 v.push_back( 53 );
 v.push_back( 64 );
 v.push_back( 80 );

}

int search_max(const vector<int>& v, int s) {

 int min = 0;
 int max = v.size() - 1;
 int mid;
 int midval;
 bool found = false;
 
 // pre .. if s is less than v[0], no way to find pair.
 if( s <= *(v.begin()) )
  throw "not qualify pre-requisite";
  

 while( min <= max ) {
  mid = (min + max) / 2;
  midval = v.at(mid);
  if( s == midval ) {
   found = true;
   break;
  }
  else if( s > midval) {
   min = mid + 1;
  }
  else {
   max = mid - 1;
  }
 }

 return found ? mid : max;
}

bool search(const vector<int>& v, int s) {
 
 int max;
 try {
  max = search_max(v,s);
  cout << "max for search:" << max << endl;
 }catch(const char* msg) {
  cerr << "errmsg:" << msg << endl;
  return false;
 }

 for( int i = 0;i < max;i++ ) {
  for( int j = i;j < max;j++ ) {
   if( v[i] + v[j] == s ) 
    return true;
  }
 }

 return false;

}

void dump(const vector<int>& v) {
 
 for( vector<int>::const_iterator iter = v.begin();iter != v.end();iter++ ) {
  cout << *iter << endl;
 }

}


int main()
{
 vector<int> v;
 init_vector(v);
 dump(v);
 try {
  cout << search(v,3) << endl;
 } catch( const char* err) {
  cerr << err << endl;
 }

 cout << search(v,55) << endl;
 cout << search(v,53) << endl;

 return 0;
}

解答2

プログラムは長くなった割に得たものは少ない．ならばアプローチを変えよう． 目的の数Sからループ中の要素v[i]を引いてcを得る．そのcがハッシュテーブルにあれば(O(1)オーダで検索可)，v[i]+v[j]=Sを満たすのである． プログラムは非常にすっきりするし，オーダもO(N)である．

bool search2(const vector<int>& v, int s ) {
 map<int,int> m;
 vector<int>::const_iterator iter;
 int c;
 int i;
 for(i = 0,iter = v.begin();iter != v.end();iter++,i++) {
  c = s - v[i];
  m[v[i]] = i;
  if( m.find( c ) != m.end() )
   return true;
 }
 return false;

}