日曜日, 5月 26, 2013

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


投稿者 時刻: 0 件のコメント:

日曜日, 5月 19, 2013

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;

}



投稿者 時刻: 0 件のコメント:

土曜日, 5月 18, 2013

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;
}
投稿者 時刻: 0 件のコメント:

木曜日, 5月 16, 2013

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


投稿者 時刻: 0 件のコメント:

水曜日, 5月 15, 2013

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;

}

投稿者 時刻: 0 件のコメント:

火曜日, 5月 14, 2013

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()と同じである．

投稿者 時刻: 0 件のコメント:

日曜日, 5月 12, 2013

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

投稿者 時刻: 0 件のコメント:

土曜日, 5月 11, 2013

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 );
  
 }
}

投稿者 時刻: 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;
  
 }
 
}


投稿者 時刻: 0 件のコメント:

木曜日, 5月 09, 2013

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() ) );
  }
 }




投稿者 時刻: 0 件のコメント:

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;
 }



投稿者 時刻: 0 件のコメント:

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;
}



投稿者 時刻: 0 件のコメント:

月曜日, 4月 29, 2013

Commons IO DateUtils

Yoda Timeの影に隠れて

Commons IOの中に，探してみればあった， DateUtils.
決して悪くはないが，JodaTimeがある以上無理して使うまでもないだろう．．とは思うが，とりあえず私たちのツールボックスの内に加えておいて損はない，ということでご紹介．

とりあえず便利

DateUtilsのJavaDocはこちらのとおり．
とりあえず加減算可能なset シリーズ ( setDays(), setYears() etc. ), 面倒なCalendarのインスタンスを省略できるtoCalendar(), 指定したフィールド以下を0にセットするtruncate()あたりが一番役立つと考えられる．iterator()もカレンダーアプリ関連で役立つかもしれない．

サンプルコード

import java.text.SimpleDateFormat;
import java.util.Calendar;
import java.util.Date;
import java.util.Iterator;

import org.apache.commons.lang3.time.DateUtils;
import static org.junit.Assert.*;
import org.junit.Before;
import org.junit.Test;

import static org.hamcrest.CoreMatchers.*;

public class DateUtilTest {

 private Date date;
 
 @Before
 public void init() {

  Calendar cal = Calendar.getInstance();
  cal.set( Calendar.YEAR, 1980 );
  cal.set( Calendar.MONTH, 0 );
  cal.set( Calendar.DAY_OF_MONTH, 2 );
  cal.set( Calendar.HOUR_OF_DAY,  5 );
  cal.set( Calendar.MINUTE,  20 );
  cal.set( Calendar.SECOND,  30 );
  cal.set( Calendar.MILLISECOND,  790 );
  date = cal.getTime();
  
 }
 
 @Test
 public void testAddAndSubtract() {

  Calendar cal = Calendar.getInstance();
  cal.setTime( DateUtils.addDays( date, 4 ) );
  assertThat( cal.get( Calendar.DAY_OF_MONTH ), is( 6 ) );
  cal = Calendar.getInstance();
  cal.setTime(  DateUtils.addHours( date, 5 ) );
  assertThat( cal.get( Calendar.HOUR_OF_DAY ), is( 10 ) );
  cal = DateUtils.toCalendar( DateUtils.addMilliseconds( date, 25 ) );
  assertThat( cal.get( Calendar.MILLISECOND ), is( 815 ) );
  // subtract
  cal = DateUtils.toCalendar( DateUtils.addYears( date, -10 ) );
  assertThat( cal.get( Calendar.YEAR ), is( 1970 ) );
  
  // truncate
  assertThat( DateUtils.truncate( date, Calendar.DAY_OF_MONTH ).toString(), is( "Wed Jan 02 00:00:00 EST 1980" ) ); 
 }
 
 @Test
 public void testIterator() {
  
  Iterator<Calendar> iter = DateUtils.iterator( date, DateUtils.RANGE_MONTH_SUNDAY );
  int i = 0;
  SimpleDateFormat sdf = new SimpleDateFormat( "yyyy/MM/dd" );
  while( iter.hasNext() ) {
   if( ++i == 10 ) break;
   System.out.print( sdf.format(iter.next().getTime()) + " ");
  }
 }

}



投稿者 時刻: 0 件のコメント:

日曜日, 4月 28, 2013

C# - testboxを末尾まで自動スクロール

AppendText関数を使うべし

TextBoxで += を使った場合は単純にTextBoxのテキストプロパティに文字列を追加するだけで，テキストボックス自体へのアクションは何も起こらない．
一方AppendText関数を使った場合は文字列末へ自動スクロールしてくれる．


投稿者 時刻: 0 件のコメント:

火曜日, 4月 16, 2013

Algorithm 問題を解く4 - 長さ不明の配列のサーチ

問題

Suppose you do not know the length of A in advance; accessing A[i] for i beyond the end of the array throws an exception.
Find the index of the first occurrence in A of a specified key k; return -1 if k does not appear in A.
(出典: Algorithms for interviews )

ヒント

終点がわからなければ探すしかない．終点がわかってからサーチ．ひと手間増えただけのこと．
問題はソート済みかどうかは言っていないがとりあえずソート済みということにしておこう．

解

まずは終点，つまり配列の終点を探す．ここで以下に効率よく絞り込みを行えるかが鍵となる．
安全に，手軽に行くのならば線形検索でよいが，O(N)のオーダであるので配列が小さい時にのみにしか適用すべきではない．
コードは以下の通り．


#include <cstdio>
#include <cstdlib>

int arrVal[] = {1,6,21,25,28,28,31,45,51,53,62,64,85};

int search_linear(int val) {

 int st = 0;
 int mid;
 int end = 0;
 int t;
 while(true) {

  // simulate out of index exception
  try {
   if( end >= (sizeof(arrVal) / sizeof(int)) )
    throw "out of index access";
   t = arrVal[end];
   printf("t=%d,end=%d,val=%d,idx=%d\n",t,end,val,end);
   if( t == val )
    return end;
   else if( t > val )
    break;

  } catch( char* str ) {
   printf("exception:%s.\n", str );
   break;
  }
  end++;
 }

 // now we know the end index of the "unbounded array.". Do the bsearch!
 while( st <= end ) {
  mid = (st + end) / 2;
  printf("st=%d,end=%d,mid=%d,val=%d,midval=%d\n",st,end,mid,val,arrVal[mid]);
  if( arrVal[mid] == val)
   return mid;
  else if( arrVal[mid] > val )
   end = mid - 1;
  else
   st = mid + 1;
 }
 return -1;

}


int main() {

 printf("%d ? %d\n",64,search(64));
 printf("%d ? %d\n",25,search(25));
 printf("%d ? %d\n",6,search(6));
 printf("%d ? %d\n",19,search(19));
 printf("%d ? %d\n",53,search(53));
 printf("%d ? %d\n",85,search(85));
 return EXIT_SUCCESS;
}

データが大きくなった場合，どうするか？上のコードでは計算量が多くて話にならないので，
なんとかlog2Nのオーダで絞り込むことを考える．
例外が投げられるか，又はA[2^k-1]の値が検索対象の値より大きくなるかのどちらかを満たすまで配列の終点と推定できるインデックスを探す．そしてその配列の終点と仮定した点2^k-1と2^kの間でバイナリサーチをすれば，log2Nのオーダの計算量で収まる．


投稿者 時刻: 0 件のコメント:

日曜日, 4月 14, 2013

Algorithm 問題を解く3 - バイナリサーチ(２分探索) その弐

問題

 SEARCH A SORTED ARRAY FOR A[i] = i

 Suppose that in addition to being sorted, the entries of A are distinct integers. Design an efficient algorithm for finding an index i such that A[i] = i or indicating that no such index exists.

 ( 出典: algorithms for interviews )

ヒント

sorted arrayときたらまずとりあえず考えるのは? 
distinct integers, つまり重複無しのソート済み配列である．

答え

重複無しのソート済み配列とのこと．昇順であると仮定すれば以下が成り立つ

 S[i] > S[i-1]

 私の解答は以下の通り．
ロジックとはしては調べたいインデックスを２分木で絞り込む．調べたい値targetと２分木の中央要素v.at(mid)が等価ならばそのインデックスを返し，２分木探索終了時まで見つからなければ問題の指示通り-1を返す．


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

#define INTARRAY_MAX 10

int search(vector<pair<int,int>> v, int target) {
 
 int st = 0;
 int end = v.size() - 1;
 int mid;
 while( st < end ) {
  
  mid = (st + end) / 2;
  cout << st << ',' << end << ',' << mid << ',' << v.at(mid).second << endl;
  if( v.at(mid).second == target )
   return mid;
  else if( v.at(mid).second > target )
   end = mid - 1;
  else
   st = mid + 1;
 }
   
 return -1;
}

int main() {
 vector<pair<int,int>> v;
 int arrVal[] = { 0,1,3,15,18,26,38,45,50,62};
 for( int i = 0;i < INTARRAY_MAX;i++ )
  v.push_back(make_pair(i,  arrVal[i] ));

 cout << "find? " << search(v, 1) << endl;
 cout << "find? " << search(v, 5) << endl;

 return EXIT_SUCCESS;
}

プログラムを走らせると以下のようなアウトプットを得る． 
0,9,4,18
0,3,1,1
find? 1
0,9,4,18
0,3,1,1
2,3,2,3
find? -1
O(log2N)の平均又は最悪計算量で終えることできるのでデータ量が多くても大丈夫．(最もここではソートのコストは考慮に入れていない．)
ちなみにutilityヘッダはSTLのpairを使用する為に必要．

投稿者 時刻: 0 件のコメント:

アルゴリズム基本編 1 - ランダムな整数列の生成

ランダムで要素の重複があってもよい整数列

ランダムな整数列をつくりなさい，要素の重複はあってもいいですよ，といわれた場合，あなたはどうするか．
当然ながら最も簡単な答えは整数列に疑似乱数を生成して割り当てればよい．

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INTARRAY_MAX 10

int* gen_rand_intarray(int* arr, int size) {
 
 for(int i = 0;i < size;i++){
  *arr = rand() % size;
  printf("%d\n",*arr);
  arr++;
 }
 return arr;

}

int main() {

 srand(time(NULL));
 int* arr = (int*)malloc(INTARRAY_MAX*sizeof(int));
 gen_rand_intarray(arr,INTARRAY_MAX);
 for( int i = 0;i < INTARRAY_MAX;i++ ) {
  printf("%i - %d[@%d]\n",i,*arr,arr);
  arr++;
 }
 return EXIT_SUCCESS;

}
では要素の重複はゆるさないよ，となったら？リストからセットにデータを移し替えればおのずと重複要素は消えるが，整数列長は縮む可能性があるので解として不適な可能性がある．
やはりここは定石の配列のインデックスを乱数生成しシャッフル，だろう．乱数値の生成とシャッフル合わせてO(2N)．もっと効率的な方法はありそうだが．． 


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define INTARRAY_MAX 10

int main() {

 srand(time(NULL));
 int r,t;

 int arr2[INTARRAY_MAX];
 for(int i = 0;i < sizeof(arr2)/sizeof(int);i++)
  arr2[i] = i;

 for(int i = 0;i < INTARRAY_MAX;i++) {
  r = rand() % INTARRAY_MAX;
  t = arr2[r];
  arr2[r] = arr2[i];
  arr2[i] = t;
 }

 for(int i = 0;i < INTARRAY_MAX;i++)
  printf("%d ", arr2[i]);

 char ch;
 scanf(&ch);
 return EXIT_SUCCESS;

}
ちなみにSTLのrandom_shuffleを使った場合の解は以下の通り．


#include <iostream>
#include <vector>
#include <algorithm>

#define INTARRAY_MAX 10

int main() {
 std::vector<int> v;
 for( int i = 0;i < INTARRAY_MAX;i++ )
  v.push_back(i);
 std::random_shuffle(v.begin(),v.end());
 for(std::vector<int>::iterator it = v.begin();it != v.end();++it)
  std::cout << *it << ' ';
 std::cout << std::endl;
 return EXIT_SUCCESS;
}
投稿者 時刻: 0 件のコメント:

金曜日, 4月 12, 2013

blogにソースコードを埋め込む

最初は知らず．．

このブログを始めた時，ブログにソースコードを綺麗に貼り付ける方法を知らなかった．．ので，ベタベタと能も無く貼り付けていたのだが，色々なページを見ているうちに私もエディター風の綺麗なコードを埋め込みたい！と思って調べてみたら，実にわかりやすい解説をしてくださっているサイトを発見．このブログの紹介もこのSyntax Highlighterもvery good jobだね．

http://www.craftyfella.com/2010/01/syntax-highlighting-with-blogger-engine.html


投稿者 時刻: 0 件のコメント:

水曜日, 4月 10, 2013

Commons Lang - EqualsBuilder & HashCodeBuilder

equals() と hashCode()

Javaでドメインモデル設計の際重要になってくるequals()とhashCode()のオーバーライド．
これを自分で実装するのは結構めんどうくさいし，コードの可読性も決して高くはないのが通常だろうと思う．そんな時にお勧めなのはやはりApache CommonsのEqualsBuilderとHashCodeBuilderだろう．

サンプル

以下のようなトレードクラスがあったとする．
このクラスの主キーフィールドはtradeIdとeventIdとしよう．
equals()とhashCode()ではそれぞれEqualsBuilderとHashCodeBuilderを使って複合主キーを比較している．この例では非主キーのフィールドは比較をしていない．

import java.util.Date;

import org.apache.commons.lang3.builder.EqualsBuilder;
import org.apache.commons.lang3.builder.HashCodeBuilder;

public class Trade {
 
 private String tradeId;
 private String eventId;
 private Date settleDate;
 private Date tradeDate;
 private int counterPartyId;
 
 public Trade( String tradeId, String eventId, Date settleDate, Date tradeDate, int counterPartyId ) {
  this.tradeId = tradeId;
  this.eventId = eventId;
  this.settleDate = settleDate;
  this.tradeDate = tradeDate;
  this.counterPartyId = counterPartyId;
 }
 
 public boolean equals( Object obj ) {
  boolean result = false;
  if( obj instanceof Trade ) {
   Trade other = (Trade)obj;
   result = new EqualsBuilder().append( tradeId, other.getTradeId() )
     .append( eventId, other.eventId )
     .isEquals();
  }
  return result;
 }
 
 public int hashCode() {
  return new HashCodeBuilder().append( tradeId )
    .append( eventId ).toHashCode();
 }
 
 public String getTradeId() { return tradeId; }
 public String getEventId() { return eventId; }
 public Date getSettleDate() { return settleDate; }
 public Date getTradeDate() { return tradeDate; }
 public int getCounterPartyId() { return counterPartyId; }
}


それでもってこのTradeのequals()とhashCode()のテストクラスが以下の通り．
以下のテストで分かる通り，trd6は主キーが同じなのに非主キーフィールドは異なっているという異常ケースである．上記の実装ではこのような例外ケースには対応できていない．理想的には対応したほうがよい，と思うがとりあえずそれをするかどうかはプロジェクトの様々なvariablesを考慮した結果次第，だろうか．

 

import java.text.ParseException;
import java.text.SimpleDateFormat;

import org.junit.Test;
import static org.junit.Assert.*;

public class BuilderSampleTest {

 @Test
 public void testEqualsAndHashCode() throws ParseException {
  SimpleDateFormat sdf = new SimpleDateFormat( "yyyy/MM/dd" );
  Trade trd1 = new Trade( "TRD123", "21-123221", sdf.parse( "2012/03/04" ), sdf.parse( "2012/04/04" ), 565000 );
  Trade trd2 = new Trade( "TRD238", "21-123250", sdf.parse( "2012/03/05" ), sdf.parse( "2012/04/04" ), 565000 );
  Trade trd3 = new Trade( "TRD123", "21-123250", sdf.parse( "2012/03/05" ), sdf.parse( "2012/04/09" ), 565300 );
  Trade trd4 = new Trade( "TRD126", "21-123221", sdf.parse( "2012/03/04" ), sdf.parse( "2012/04/04" ), 565000 );
  Trade trd5 = new Trade( "TRD123", "21-123221", sdf.parse( "2012/03/04" ), sdf.parse( "2012/04/04" ), 565000 );
  Trade trd6 = new Trade( "TRD123", "21-123221", sdf.parse( "2012/05/04" ), sdf.parse( "2012/06/04" ), 620000 );
  
  // trd1 and trd2 - composite primary key different
  assertTrue( !trd1.equals( trd2 ) );
  // trd1 and trd3 - composite primary key different
  assertTrue( !trd1.equals( trd3 ) );
  // trd1 and trd4 - composite primary key different
  assertTrue( !trd1.equals( trd4 ) );
  // trd1 and trd5 - both composite primary key and non-key fields are same. Of course.
  assertTrue( trd1.equals( trd5 ) );
  // trd1 and trd6 - composite primary key is same but non-key fields are different - WHAT?!
  assertTrue( trd1.equals( trd6 ) );
  // trd1 and non-Trade object
  assertTrue( !trd1.equals( new String() ) );
 }
}
投稿者 時刻: 0 件のコメント:

火曜日, 4月 09, 2013

Algorithm 問題を解く2 - バイナリサーチ(２分探索)

問題．


Write a method that takes a sorted array A of integers and a key k and
returns the index of first occurrence of k in A. Return -1 if k does not
appear in A. 
(出典: Algorithm for interviews )

 これは，ただ単に２分検索．あまりに捻りがないので逆に疑って問題を読んでしまった．

解．


#include <stdio.h>
#include <stdlib.h>

 static int intArray[] = {2,16,18,18,21,35,42,59,60,68,74,92};

int bsearch(int k) {

 int st,end,mid;
st = 0;end = sizeof(intArray)/sizeof(int)-1;

while(st <= end) {
mid = (st+end)/2;
printf("st-%d,end-%d,mid-%d,k-%d,midVal=%d\n",st,end,mid,k,intArray[mid]);
if(intArray[mid] == k)
return mid;
else if(intArray[mid] < k)
st = mid + 1;
else
end = mid - 1;
}
return -1;
}

 void show_result(int num, int result){
printf("%d:%d\n", num, result);
}

 int main(int argc, char **argv) {
// not found
show_result(68,bsearch(68));
// found
show_result(74,bsearch(74));
char ch;
scanf(&ch);
return EXIT_SUCCESS;
}


特に捻りもなく，実に普通のbsearchである．
アウトプットは以下の通り．bsearchを書くといつも義経の八艘飛びを思い浮かべるのは私だけだろうか．

st-0,end-11,mid-5,k-68,midVal=35
st-6,end-11,mid-8,k-68,midVal=60
st-9,end-11,mid-10,k-68,midVal=74
st-9,end-9,mid-9,k-68,midVal=68
68:9
st-0,end-11,mid-5,k-74,midVal=35
st-6,end-11,mid-8,k-74,midVal=60
st-9,end-11,mid-10,k-74,midVal=74
74:10

平均オーダはO(log2 n)．最悪でもO(log2 n)．線形サーチはO(n)なのでソートするコスト(例えば n log n ) を合わせても十分見合うことがわかる．

投稿者 時刻: 0 件のコメント:
登録: 投稿 (Atom)