Fedora18にChromeをインストール

Missing Security Signatures

Googleからchromeのrpmをダウンロードしてインストールしようとしても，Fedora１８ではMissing Security Signaturesというエラーが出てインストールできない．

仕方がないので以下のサイトからrpmをrpmコマンドから直にダウンロードしてインストールする．

rpm -ivh https://dl.google.com/linux/direct/google-chrome-stable_current_i386.rpm

C++ - Voidポインタを活用

Voidポインタの役割

Voidポインタはあらゆる型でありえるメモリロケーションを指し示すポインタである．Genericポインタは指定された型Tのみをストアできるポインタできるという点でVoidポインタでは異なる．
Voidポインタは非常に便利だが，Voidポインタを多用しているならばそれはかなり投げやりなインターフェースデザインか，かなり極端なグランドデザインに走っていると考えたほうが良い．

つかいどころ

相当程度に万能な関数を定義する際に使うことがあるだろうか．相当緩やかな契約を提供してもよいストラテジーパターンを取るときも使ってもよいだろう．voidポインタが使われている最も有名なところはpthreadのパラメータ．

サンプル

上述したとおり，付き合い方のツボをきちんと押さえていれば，voidポインタは非常に強力なあなたの味方である．以下の例はvoidパラメータをとる異なる２つの関数をポインタ経由で呼び出している例．

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

void ShowIntVal(void* param);
void ShowValFromVector(void* param);

void (*pShowValFunc)(void* param);

int main() {

 // int val
 pShowValFunc = ShowIntVal;
 int val = 32;
 pShowValFunc((void*)&val);
 vector<int> v;
 v.push_back(-20);
 v.push_back(-2000);
 pShowValFunc = ShowValFromVector;
 pShowValFunc((void*)&v);

 return EXIT_SUCCESS;

}

void ShowIntVal(void* param){

 int* pIntVal = static_cast<int*>(param);
 cout << "ShowIntVal:" << *pIntVal << endl;

}

void ShowValFromVector(void* param){

 vector<int> *pV = static_cast<vector<int>*>(param);
 vector<int>::iterator iter;
 cout << "ShowValFromVector:";
 for( iter = pV->begin(); iter != pV->end();iter++)
  cout << *iter << ' ';
 cout << endl;

}

C++でデザインパターン1 - シングルトン

デザインパターン

といえばやはりJava，となるのはやはりJavaが成し得たオブジェクト指向言語としての洗練さゆえか．ここではあえてC++でデザインパターンを実装していってみようと思う．

シングルトン - 適用例

最初の例はシングルトンである．ご存じの通り，あるリソースへのアクセスを制御したい時にシングルトンデザインを取る場合もある．ただし，シングルトンはユニットテストとの相性の悪さやマルチスレッド環境化において並列実行性能を低下させることもある為，敬遠されることが多い．

例の留意点

この例ではID生成シングルトンクラスを示している．この例はわかりやすさを優先しているため，実用の点から見て全くクオリファイしないことを念頭に置いてほしい．

コード

#include <iostream>
#include <ctime>

using namespace std;

class IDGenerator;

class IDGenerator {
private:
 int max;
 IDGenerator(long,int);
public:
 static IDGenerator& GetInstance(long,int);
 ~IDGenerator();
 int Next();
};

IDGenerator::IDGenerator(long seed,int maxVal):max(maxVal) {
 srand(seed);
}

IDGenerator::~IDGenerator(){}

IDGenerator& IDGenerator::GetInstance(long seed,int maxVal){
 static IDGenerator gen(seed,maxVal);
 return gen;
}

int IDGenerator::Next() {
 return rand() % max;
}

int main() {
 IDGenerator idGen = IDGenerator::GetInstance(time(NULL),100);
 for(int i = 0;i < 20;i++ ) {
  cout << idGen.Next() << " ";
 }

 return EXIT_SUCCESS;
}

C++ キャスト 1 - static cast, dynamic cast そして const cast

C++ のキャスト

C++はJavaと違って様々なキャスト演算子がある．標準のキャストが以下の４つである．

• Static cast
• Dynamic cast
• Const cast
• Reinterpret cast

勿論Cスタイルのキャスト - Javaでおなじみの， カッコでくくるキャスト演算子 - もある．C言語スタイルのキャストはstatic, const, reinterpretのいずれかのキャストと同じことをするのだが，C++では使うべきではない．(こちらを参照されたし)

C++のキャストは注意深く，丁寧にC言語のキャストを機能毎に３つに分割し，かつ新たにdynamic_castを追加しているのである．4つのキャストの内，static_castは最も直観的なキャストであり，longからint, intからcharといったような型変換 かつ 変数の中身の変換を行ってくれる．
Dynamic_castはダウンキャストを行う時に，継承関係の検査を行い，正しくないキャストの場合はポインタの場合はNULL,参照の場合はstd::bad_cast例外をスローする．Reinterpret castは型だけを変換し，内部の値はタッチしない．(こちらを参照されたし)．最後のconst_castはvolatileとconstを打ち消してくれるキャストである．

私のやっていることは正しいか？

Static_castはまあいいとして，他の３つのキャストを使う場面に出くわしたときは必ず以下のことを自問してほしい．

私のやっていることは，正しいのか？
このデザインは，なんか間違ってるんじゃないのか？
本当に，仕方がないのか？
これをやったら，それなりのベネフィットは，あるのか？

以上の自問について，あなたが自分と(可能ならばpeer)を納得できる答えを返すことができれば，実に結構．さもなれければリファクタリングに取り掛かったほうがよいのかもしれない．

サンプル

以下の例はstatic_cast, const_castそしてdynamic_castを使った例である．サンプルコードという手前もあって極めてナンセンスなコードであるが，上記キャストの用例としては適当かと思う．ちなみにこのコードを目の前にして上述の自問をすれば全ての問いに対して答えは，big noである．

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


class Base {
protected:
 int fieldA;
public:
 Base() { fieldA = 0;};
 virtual void ShowField(const string* prefix ) { printf("%s-%d\n", prefix->c_str(), fieldA); }
};

class Child: public Base {
public:
 Child();
 void ShowField(const string* prefix);
};

Child::Child(): Base() {
 printf("Child created.\n");
}

void Child::ShowField(const string* prefix) {
 Base::ShowField( prefix );
 string* p = const_cast<string*>(prefix);
 *p = "--the jail breaker--";

}

class Stranger {
public:
 Stranger() {}
};

int main() {

 // static_cast
 double d = 50.0;
 printf( "staticcast - %d\n", static_cast<int>(d) );

 // const_cast
 Child c;
 string str = "abc";
 c.ShowField(&str);
 printf("%s\n",str.c_str());

 // dynamic_cast
 Stranger *pS = dynamic_cast<Stranger*>(&c);
 if( pS == NULL )
  printf("downcast failed as per the pS content");

 return 0;

}

実行結果

staticcast - 50
Child created.
abc-0
--the jail breaker--
downcast failed as per the pS content

STL1 .. STLコンテナとクラス

STLコンテナに自作のクラスをストアしたい

STLコンテナに自作クラスをストアさせたいことはよくあるはず．

そうしたい場合はクラスを定義する際に以下のことを留意することが大事である．

クラスコンストラクタがメモリをアロケートする必要がある場合，コピーコンストラクタと=演算子オーバーロードを定義する必要がある．

忘れてはならないのはコピーコンストラクタと=演算子のオーバーロードである．それらを忘れればたちまちデスクトラクタにおいてメモリの２重解放が発生し，プログラムはたちまちクラッシュするだろう．


コード

以下のコードはコンストラクタでメモリをアロケートしているわけではないが，コピーコンストラクタと＝演算子を定義している例である．のちにクラスを拡張してポインタフィールドを足した場合でも安全である．

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

class TradeInfo 
{
protected:
 string tradeId;
 int eventId;

public:
 TradeInfo() {}
 virtual ~TradeInfo() {}
 TradeInfo(const TradeInfo& info) {
  tradeId = info.tradeId;
  eventId = info.eventId;
 }
 TradeInfo& operator =(const TradeInfo& info) {
  TradeInfo in;
  in.tradeId = info.tradeId;
  in.eventId = info.eventId;
  return in;
 }

 string GetTradeId() { return tradeId; }
 int GetEventId() { return eventId; }
 void SetTradeId(string str) { tradeId = str; }
 void SetEventid(int evt) { eventId = evt; }
 void dump() {
  cout << "TradeId-" << tradeId << ",EventId-" << eventId << endl;
 }

};

TradeInfo GenerateTradeInfo(string str,int eventId) {

 TradeInfo t;
 t.SetTradeId(str);
 t.SetEventid(eventId);
 return t;

}

int main() {

 vector<TradeInfo> v;
 v.push_back(GenerateTradeInfo("abc",1));
 TradeInfo t = v.at(0);
 t.dump();

 return EXIT_SUCCESS;

}

C++ - メモリと対話する楽しみ

C++

周りの新人や，面接等をしている限りひしと感じるのは，とにかくC/C++を知っている人がどんどん減ってきていることである．私はJavaをやっていて..というのが８割方，９割，いや，もうほとんど１０割である．時代の流れである．この流れをとやかく言うつもりはないし，ニーズも多いのは間違いない．なにしろC++に比べて非常に簡単に書ける．Javaならではの難しさだって多々ある．しかし，JVMの大変優れたGCや素晴らしいオープンソースライブラリのおかげでJavaの開発は他の言語，特にC/C++に比べて随分楽であることは間違いないだろう．

しかし，Javaを書いてもメモリと対話している感じはあまり感じない ( あくまでこれは私個人の一意見 )．勿論プロファイリングをしているときにヒープやpermgenの使用率をじーっとみているときはちょっとはメモリと対話してる感はあるが．．C/C++の比ではない．
つまるところ，Javaは物足りなさを感じるのである．幸い私のプロジェクトはJavaとC++が入れ代わり立ち代わりなので両方を楽しむことはできているが，やはりC++を離れてJavaばかりやっているとC++に無性に戻りたくなるのである．

ということでメモリを意識できる例の一つであるC++のポリモーフィズムの仕組みを紹介する．

C++のポリモーフィズム

以下のC++のコードは実に変哲もないポリモーフィズムのコードである．が，その仕組みは関数のメモリアドレスルックアップを含む，実にC++らしいものである．

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

class Parent {

protected:
 vector<int> v;

public:
 Parent(){ cout << "constructor" << endl; }
 virtual ~Parent() { cout << "Destructor" << endl; }

 virtual void push_back(int a){ v.push_back(a); }
 //virtual void push_back(int a){ v.push_back(a); }
 virtual int get(int idx){ return v.at(idx); }

};

class Child: public Parent {

private:
 string decoration;
public:

 Child(string decorationVal="empty") { decoration = decorationVal; }

 int get(int idx){ cout << "**" << decoration << "**" << endl; return v.at(idx); }

};

int main() {

 
 Parent *p = new Child(string("takoneko"));
 p->push_back(32);
 p->push_back(16);
 cout << p->get(0) << endl;
 return 0;

}

ここではvirtual修飾子がキーである．これをつければその関数は仮想関数ということになり，その修飾子がないメソッドは非仮想関数となる． コンパイラが上記クラスをコンパイルした場合はvtableという不可視のフィールドがそのクラスに足される．そして仮想関数はvtableにエントリされる．仮想関数はvtableにエントリされない．仮想関数が呼ばれた場合は動的結合(Dynamic Binding)という仕組みで呼び出される．これはランタイム時にvtableのルックアップを行い，呼び出すべき関数のメモリアドレスを取得する．一方非仮想関数が呼ばれた場合は静的結合(Static Binding)という仕組みで呼び出される．静的結合は単純にその関数を呼び出したポインタの型であるクラスの関数を呼ぶ．このバインディングはコンパイル時に決定するので動的結合より早い．
ちなみにJavaでは全て仮想関数．protected void init()とかをJavaで書けばC++でいうところのprotected virtual void init()と同じである．

Deadlock

デッドロックの定義

計算機科学の内の最重要タームの一つのデッドロック．今一度デッドロックの定義を確認しておきたい．端的に言えば，デッドロックとは

• “二つ以上”のリソースのロックをめぐって
• 複数のプロセスが互いに待ち合う

事象を指す．
デッドロックが発生すればデッドロック検知・処理機構が実装されていない限り，アプリケーションはクラッシュもせず処理もしない，プロセスは正常実行中のまま，という保守の観点から厄介な状態に陥る．

ここでは，デッドロックを意図的に発生させてみる．

デッドロックを意図的に発生

いざ，デッドロックを意図的に発生させるコードというのは実は思った以上に難しい．有名な４賢人の箸が最も有名だが，ここではウィキペディアのデッドロック中での原因の項で示されている例を実装してみた．

以下上記ページからの引用

ここに変数Aと変数Bの二つのデータと、BにAの値を加算し、Aを0にする処理AとAにBの値を加算し、Bを0にする処理Bの二つの処理があったとする。マルチスレッドで処理をするため変数Aと変数BにアクセスするためのクリティカルセクションA（以下CSA）とクリティカルセクションB（以下CSB）の二つのクリティカルセクションを用意する。

処理Aは以下の手順であるとする。

1. CSAに入る
2. CSBに入る
3. BにAの値を加算
4. Aに0を代入
5. CSBから出る
6. CSAから出る

また同様に処理Bは以下の手順であるとする。

1. CSBに入る
2. CSAに入る
3. AにBの値を加算
4. Bに0を代入
5. CSAから出る
6. CSBから出る

この場合は以下のようにプログラムが動作するとデッドロックが発生する。

以下のコードは上記ステップをJavaで実装してみた例である．

public class Deadlock {
 
 Object critA = new Object();
 Object critB = new Object();
 int a;
 int b;
 
 public void start() throws Exception {
  
  a = 100;
  b = 50;
  Thread a = new Thread( new CriticalSectionLogic(), "A" );
  Thread b = new Thread( new CriticalSectionLogic(), "B" );
  a.start();
  Thread.sleep( 100 );
  b.start();
 }

 /**
  * @param args
  */
 public static void main(String[] args) throws Exception {
  
  Deadlock d = new Deadlock();
  d.start();

 }
 
 public void criticalSectionA( String name ) throws Exception {
  
  synchronized( critA ) {
   System.out.printf( "%s entering into CSA\n", name );
   synchronized( critB ) {
    Thread.sleep( 100 );
    b += a;
   }
   a = 0;
  
   System.out.printf( "%s exitting into CSA\n", name );
  }
  
 }
 
 public void criticalSectionB( String name ) throws Exception {
  
  synchronized( critB ) {
   System.out.printf( "%s entering into CSB\n", name );
   synchronized( critA ) {
    a += b;
   }
   b = 0;
   System.out.printf( "%s exitting into CSB\n", name );
  }
  
 }
 
 class CriticalSectionLogic implements Runnable {

  public void run() {
   
   String name = Thread.currentThread().getName();
   System.out.printf( "Thread %s starting..\n", name );
   try {
    if( name.equals( "A" ) ) {
     criticalSectionA( name );
     criticalSectionB( name );
    }
    else {
     criticalSectionB( name );
     criticalSectionA( name );
    }
   } catch ( Exception e ) {
    e.printStackTrace();
   }
    
  }

 }

}

criticalSectionAでsleep()を読んでいるのはthreadAをwaitさせる為．

実行結果は何度実行しても以下の通りとなり，このプログラムは永遠に終了しない．

Thread A starting..
A entering into CSA
Thread B starting..
A exitting into CSA
B entering into CSB
B exitting into CSB
B entering into CSA
A entering into CSB

Commons Collection 4 - CompositeMap, FastList

CompositeMap - 複数のマップを統合

複数のマップをひとつのマップインスタンスからアクセスできる，ビューのようなものを利用できれば便利だなぁ，と思ったことはないだろうか．そのようなユースケースに対してはCompositeMapを使うと良い．以下のコードはマップのユースケースだが，同じような機能がセット，ひいてはコレクションに対しても用意されている ( CompositeSet, CompositeCollection )．
注意しておきたいのは，重複したキーがあった場合にはCompositeクラスは例外をスローすることである．

 @Test(expected=Exception.class)
 public void testCompositeMap() {
  
  CompositeMap compo = new CompositeMap( initMap(), initMap2() );
  assertThat( compo.size(), is( 10 ) );
  compo = new CompositeMap( initMap(), initMap() );
  
 }
 
 private Map<Integer,String> initMap() {
  Map<Integer,String> m = new HashMap<Integer,String>();
  m.put( 1, "NewYork" );
  m.put( 2, "Tokyo" );
  m.put( 3, "Bangalore" );
  m.put( 4, "London" );
  m.put( 5, "Paris" );
  return m;
 }
 
 private Map<Integer,String> initMap2() {
  Map<Integer,String> m = new HashMap<Integer,String>();
  m.put( 6, "Hongkong" );
  m.put( 7, "Seoul" );
  m.put( 8, "Cairo" );
  m.put( 9, "AllenTown" );
  m.put( 10, "GeorgeTown" );
  return m;
 }

FastList - 非同期リードを提供するリスト

Javadocにも書いてある通り，このクラスはマルチスレッド環境下で大半がリードアクセスである場合の使用を想定している．FastListを使った場合，リストへのリードアクセスは非同期化され，ライトアクセスは以下のような処理を経る．

1. 既存のコレクションをクローン
2. クローンに対して変更を適用
3. 既存のコレクションをステップ2 で変更したクローンと置き換える

FastListには slow モードと fast モードの２つがあり，slowモードはリードアクセスは同期化され，ライト時のクローンも行われない．fastモードはリードは非同期，ライトもクローンプロセスを経る．
最初にこのクラスを生成したときはslowモードなので，最初の初期化が経てあとはほとんどリードオンリー，となった段階でsetFast(true)を呼ぶ必要がある．

ちなみにFast系は以下のコードで使っているFastArrayListのほかにFastHashMapとFastTreeMapがある．

コード
このコードはFastArrayListとArrayListの同じノードに対してそれぞれ100回アクセスした場合のラップタイムを計っている． 結果は何度やってもArrayListのほうが約2倍近く早い．おそらくFastArrayListは実装が色々と複雑となってしまっているのだろう．

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.TimeUnit;

import org.apache.commons.collections.FastArrayList;
import org.apache.commons.lang3.time.StopWatch;
import org.junit.Before;
import org.junit.Test;
import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;

public class FastListTest implements Runnable {

 List<String> list = null;

 @Before
 public void init()  {
  
  list = initFastList();

 }
 
 @Test
 public void testFastList() throws InterruptedException {
  
  ExecutorService service = Executors.newFixedThreadPool( 30 );
  StopWatch watch = new StopWatch();
  watch.start();
  for( int i = 0;i < 100;i++ ) {
   service.submit( this );
   
  }
  service.shutdown();
  service.awaitTermination( 10000L, TimeUnit.HOURS );
  System.out.println( "FAST - " + watch.getTime() );
  
  watch.reset();
  
  list = initArrayList();
  service = Executors.newFixedThreadPool( 30 );
  
  watch.start();
  for( int i = 0;i < 100;i++ ) {
   service.submit( this );
   
  }
  service.shutdown();
  service.awaitTermination( 10000L, TimeUnit.HOURS );
  System.out.println( "NONFAST - " + watch.getTime() );
  
 }

 private FastArrayList initFastList() {
  
  // slow mode first
  FastArrayList list = new FastArrayList();
  list.add( "a" );
  // switching to fast mode
  list.setFast( true );
  return list;
  
 }
 
 private List<String> initArrayList() {
  
  // slow mode first
  List<String> list = new ArrayList<String>();
  list.add( "a" );
  // switching to fast mode
  return list;
  
 }

 public void run() {
  // access to random node
  list.get( 0 );
  
 }
}

Commons Collection 3 - Buffer

Queue, Stack, Binary Heap

Bufferはスタック，キュー及びバイナリヒープの機能を提供する．
標準ライブラリにもスタック，キューはあるのでわざわざこちらを使う必要があるかどうか．．の判断は私たち次第である．

コード

この例ではキューとしてUnboundedFifoBuffer, スタックとしてArrayStack, バイナリヒープとしてPriorityOrderを使っている．

import java.util.Comparator;

import org.apache.commons.collections.ArrayStack;
import org.apache.commons.collections.Buffer;
import org.apache.commons.collections.buffer.PriorityBuffer;
import org.apache.commons.collections.buffer.UnboundedFifoBuffer;
import org.junit.Test;
import static org.junit.Assert.*;
import static org.hamcrest.CoreMatchers.*;

public class CollectionsTest {

 @Test
 public void testBuffer() {
  // Queue - FIFO
  Buffer buffer = new UnboundedFifoBuffer();
  injectTestValue( buffer );
  assertThat( (String)buffer.get(), is( "1st" ) );
  assertThat( (String)buffer.remove(), is( "1st" ) );
  assertThat( (String)buffer.remove(), is( "2nd" ) );
  assertThat( (String)buffer.remove(), is( "3rd" ) );
  // Stack - LIFO
  buffer = new ArrayStack();
  injectTestValue( buffer );
  assertThat( (String)buffer.get(), is( "3rd" ) );
  assertThat( (String)buffer.remove(), is( "3rd" ) );
  assertThat( (String)buffer.remove(), is( "2nd" ) );
  assertThat( (String)buffer.remove(), is( "1st" ) );
  // BinaryHeap
  // ascending
  buffer = new PriorityBuffer( true, new StringLengthComparator<String>() );
  injectTestValueForPriorityBuffer( buffer );
  assertThat( (String)buffer.remove(), is( "/usr" ) );
  assertThat( (String)buffer.remove(), is( "/usr/local" ) );
  assertThat( (String)buffer.remove(), is( "/usr/local/bin" ) );
  // descending
  buffer = new PriorityBuffer( false, new StringLengthComparator<String>() );
  injectTestValueForPriorityBuffer( buffer );
  assertThat( (String)buffer.remove(), is( "/usr/local/bin" ) );
  assertThat( (String)buffer.remove(), is( "/usr/local" ) );
  assertThat( (String)buffer.remove(), is( "/usr" ) );
 }
 
 private void injectTestValue( Buffer buffer ) {
  buffer.add( "1st" );
  buffer.add( "2nd" );
  buffer.add( "3rd" );
 }
 
 private void injectTestValueForPriorityBuffer( Buffer buffer ) {
  buffer.add( "/usr" );
  buffer.add( "/usr/local" );
  buffer.add( "/usr/local/bin" );
 }

}

class StringLengthComparator<String> implements Comparator<String> {


 public int compare( String arg0, String arg1 ) {
  
  if( ((java.lang.String) arg0).length() > ((java.lang.String) arg1).length() )
   return 1;
  else if( ((java.lang.String) arg0).length() == ((java.lang.String) arg1).length() )
   return 0;
  else
   return -1;
  
 }
 
}

Commons Collection 2 - BidiMap, Bag

BidiMap - キー又はバリューで検索可能なマップ

Commons Collectionsの本命の一つとも思われるのがこのBidiMap(Bidirectional Map)だろう．
キーのみならずバリューでも検索できるのでこれは優れものである．

以下のコードの例はキーで検索して要素を削除，そしてバリューで検索して要素を削除する例を示している．

 @Test
 public void testBidiMap() {
  
  BidiMap bidiMap = new TreeBidiMap( initMap() );
  assertThat( (String)bidiMap.remove( 4 ), is( "London" ) );
  assertThat( ((Integer)bidiMap.removeValue( "NewYork" )).intValue(), is( 1 ) );
  assertThat( bidiMap.size(), is( 3 ) );
  
 }
 
 
 private Map<Integer,String> initMap() {
  Map<Integer,String> m = new HashMap<Integer,String>();
  m.put( 1, "NewYork" );
  m.put( 2, "Tokyo" );
  m.put( 3, "Bangalore" );
  m.put( 4, "London" );
  m.put( 5, "Paris" );
  return m;
 }

バッグ - データストレージ

オブジェクトのストレージとして使えるバッグ - 使えるのか？
とりあえずサンプルコードを作ってみた．

 @Test
 public void testBag() {
  
  Bag bag = new HashBag();
  bag.add( 4, 6 );
  bag.remove( 4, 3 );
  assertThat( bag.getCount( 4 ), is( 3 ) );
  Iterator iter = bag.iterator();
  while( iter.hasNext() ) {
   System.out.println( System.identityHashCode( iter.next() ) );
  }
 }

Commons Collection 1 - IterableMap, OrderedMap

便利！？

有難いライブラリを量産してくれているCommonsは，当然独自のcollectionも提供してくれている．
言うまでもなくこれらを知っておくことは大切だ，ということで何回かに分けてメジャーどころを紹介していくこととする．

IterableMap - イテレータが使えるマップ

ご存じのとおり，Javaの標準mapではイテレーションはサポートしていない．これが意外に不便だと思う時も少なくない．勿論イテレーションが出来ないわけじゃない．でもコードが大変不器用な感じになるのである．以下のように要素のセットをマップから取得しそのセットからイテレータを生成する，という流れである．

 @Test
 public void testMapIteration() {
  
  Map<Integer,String> map = initMap();
  Iterator<Entry<Integer,String>> entSet = map.entrySet().iterator();
  while( entSet.hasNext() ) {
   Entry<Integer,String> e = entSet.next();
   System.out.printf( "%d-%s\n", e.getKey(), e.getValue() );
  }
 }
 
 private Map<Integer,String> initMap() {
  Map<Integer,String> m = new HashMap<Integer,String>();
  m.put( 1, "NewYork" );
  m.put( 2, "Tokyo" );
  m.put( 3, "Bangalore" );
  m.put( 4, "London" );
  m.put( 5, "Paris" );
  return m;
 }

では一方でCommons Collectionが提供しているIterableMapを使うとどうなるか？
コードは以下のようになる．

 /**
  * Order not stable. Result is like .. 
  * <pre>
  * 2Tokyo
  * 4London
  * 1NewYork
  * 3Bangalore
  * 5Paris
  * </pre>
  */
 @Test
 public void testIterableMap() {
  
  IterableMap map = new HashedMap( initMap() );
  MapIterator iter = map.mapIterator();
  String val = null;
  int key = 0;
  
  while( iter.hasNext() ) {
   
   iter.next();
   key = ((Integer)iter.getKey()).intValue();
   val = (String)iter.getValue();
   System.out.printf("%d%s\n",key, val);
   
  }

 }

 private Map<Integer,String> initMap() {
  Map<Integer,String> m = new HashMap<Integer,String>();
  m.put( 1, "NewYork" );
  m.put( 2, "Tokyo" );
  m.put( 3, "Bangalore" );
  m.put( 4, "London" );
  m.put( 5, "Paris" );
  return m;
 }

まぁどっちがいいかは人の好みによるかもしれない(^_^;)

OrderedMap - 要素の順序が保障されるマップ

Mapにputした順序が維持されるマップである．便利そうだ．．でもたちまちにユースケースが思いつかない．．でもきっと役に立つ．．と不思議な感覚に陥るマップである．
ここではLinkedMapという実装クラスを使用する．
また，以下の例ではもしかしたら陥るかもしれない，ちょっとした落とし穴を跨いでいる．
上記の通りこのマップはputをした順を保持する．気をつけたいのはLinkedMapをjava.util.Mapを引数にとるコピーコンストラクタを使う場合だ．当然java.util.Mapの要素の取り出される順序はハッシュの順なのでputした順とは違う．なので最初のmapのループのアウトプットはinitMap()でputした順序ではないのである．あくまでコピーコンストラクタの内部で取り出された順序，である．

 @SuppressWarnings("unchecked")
 @Test
 public void testOrderedMap() { 
  
  OrderedMap map = new LinkedMap( initMap() ); 
  MapIterator iter = map.mapIterator();
  String val = null;
  int key = 0;
  while( iter.hasNext() ) {
   
   iter.next();
   key = ((Integer)iter.getKey()).intValue();
   val = (String)iter.getValue();
   System.out.println(key + val);
   
  }
  map.clear();
  map.put( 1, "Metuchen" );
  map.put( 3, "Kosciuszko" );
  map.put( 2, "Kitami" );
  map.put( 5, "Tripoli" );
  map.put( 4, "Serangoon" );
  assertThat( ((Integer)map.firstKey()).intValue(), is( 1 ) );
  assertThat( (String)map.get(map.firstKey()), is( "Metuchen" ) );
  assertThat( ((Integer)map.nextKey(3)).intValue(), is( 2 ) );
  assertThat( (String)map.get(map.nextKey(3)), is( "Kitami" ) );
  
 }


 private Map<Integer,String> initMap() {
  Map<Integer,String> m = new HashMap<Integer,String>();
  m.put( 1, "NewYork" );
  m.put( 2, "Tokyo" );
  m.put( 3, "Bangalore" );
  m.put( 4, "London" );
  m.put( 5, "Paris" );
  return m;
 }

Algorithm 問題を解く5 - インターセクション

問題

Given sorted arrays A and B of lengths n and m respectively, return an array C containing elements common to A and B. The array C should be free of duplicates. How would you perform this intersection if - (1.) n = m and (2.) n < m?
( 出典: Algorithms for interviews )

ヒント

これは典型的なインターセクションの問題である．ソート済みとくれば勿論あのアルゴリズムが頭をよぎるのではないだろうか．

解

逐次ループを回して配列nとmの共通要素を括りだしていけば簡単に解を得ることができるが，当然効率の面からみてよくない．O(n*m)である．ならば両配列がソート済みというヒントに注目したい．このヒントは明らかに２分探索して要素を探りなさい，といっているではないか．

コードは以下の通り．注意すべきは短い配列を最初のループにすること．O(N*log2M)とO(M*log2N)では大きな差となってしまう．

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

static char arrA[] = { 'A','B','B','E','G', 'K', 'U' };
static char arrB[] = { 'C','D','E','F','G', 'K', 'V','Z' };


void dump(char* arr, int size){

 for(int i = 0;i < size;i++){
  cout << arr[i] << ' ';
 }
 cout << endl;
}

void my_bsearch(char arr[], char target, int* idx){

 cout << "bsearching.." << endl;
 int min = 0;
 int max = sizeof(arrB)/sizeof(char) - 1;
 char midVal;

 while(min <= max){
  midVal = arrB[(min + max) / 2];
  cout << target << ',' << min << ',' << max << ',' << midVal << ',' << (min + max)/2 << endl;
  if(midVal == target) {
   arr[*idx] = midVal;
   *idx += 1;
   return;
  }
  else if(midVal < target)
   min = (min + max)/2 + 1;
  else
   max = (min + max)/2 - 1;

 }

}

int main() {

 char ansArr[100];
 int delta = 0;
 int idx = 0;
 
 for(int i = 0;i < sizeof(arrA)/sizeof(char);i++){
  my_bsearch(ansArr, arrA[i], &idx);
 }

 cout << "idx.." << idx << endl;
 dump(ansArr, idx);


 return EXIT_SUCCESS;
}