火曜日, 12月 31, 2013

Java8 - stream

Java8の変更点の目玉の一つがstreamである.今までのfor文よりもずっときれいにデータプロセス用のコードが書けるようになる.

以下の例は,とある場外取引システムにおけるトレードデータから以下の条件を満たすものを抽出した例.

  • TradeDateが2013年1月1日以降
  • アクション名がADD
  • 取引相手先国が日本

package org.tanuneko.sample;

import java.time.ZonedDateTime;
import java.util.ArrayList;
import java.util.List;

public class StreamSample {

    private static List<Trade> trades = populateTrades();
    private static List<CounterParty> cps = populateCPs();

    private static List<Trade> populateTrades() {
        List<Trade> list = new ArrayList<Trade>();
        list.add( new Trade( "TRD111.1", 1, "ADD", parse( "2013-01-20" ), 1001, true, "15000000ABC" ) );
        list.add( new Trade( "TRD123.1", 1, "ADD", parse( "2013-01-20" ), 1006, true, "16000000ABC" ) );
        list.add( new Trade( "TRD123.1", 2, "MOD", parse( "2013-01-26" ), 1006, true, "16000000ABC" ) );
        list.add( new Trade( "TRD145.1", 1, "ADD", parse( "2013-09-20" ), 1009, true, "T7000000ABC" ) );
        list.add( new Trade( "TRD133.1", 1, "ADD", parse( "2013-06-20" ), 1001, true, "16600000ABC" ) );
        list.add( new Trade( "TRD080.1", 1, "ADD", parse( "2010-07-20" ), 1001, true, "TRD080.1" ) );
        list.add( new Trade( "TRD092.1", 1, "ADD", parse( "2010-09-15" ), 1008, true, "TRD092.1" ) );
        list.add( new Trade( "TRD092.1", 2, "MOD", parse( "2010-09-30" ), 1020, true, "TRD092.1" ) );
        return list;
    }

    private static List<CounterParty> populateCPs() {
        List<CounterParty> cps = new ArrayList<CounterParty>();
        cps.add( new CounterParty( 1001, "US" ) );
        cps.add( new CounterParty( 1009, "Ireland" ) );
        cps.add( new CounterParty( 1006, "Japan" ) );
        cps.add( new CounterParty( 1020, "India" ) );
        cps.add( new CounterParty( 1008, "France" ) );
        cps.sort((l,r) -> l.getCounterPartyId() - r.getCounterPartyId()  );
        return cps;
    }

    private static ZonedDateTime parse( String date ) {
        return ZonedDateTime.parse( date + "T00:00:00-05:00[America/New_York]" );
    }

    public static void main( String args[] ) {
        
        trades.stream()
                .filter(t -> t.getTradeDate().isAfter(parse("2013-01-01")))
                .filter(t -> t.getActionName().equals("ADD") )
                .filter(t -> cps.stream().anyMatch( x -> x.getCounterPartyId() == t.getCounterPartyId() && x.getCountry().equals( "Japan" ) ) )
                .forEach(t -> System.out.println(t));
        cps.forEach( c -> System.out.println( c ) );
    }
}

class CounterParty {

    private int counterPartyId;
    private String country;

    CounterParty(int counterPartyId, String country) {
        this.counterPartyId = counterPartyId;
        this.country = country;
    }

    public int getCounterPartyId() {
        return counterPartyId;
    }

    public String getCountry() {
        return country;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        CounterParty that = (CounterParty) o;

        if (counterPartyId != that.counterPartyId) return false;

        return true;
    }

    @Override
    public int hashCode() {
        return counterPartyId;
    }

    @Override
    public String toString() {
        return "CounterParty{" +
                "counterPartyId=" + counterPartyId +
                ", country='" + country + '\'' +
                '}';
    }
}

class Trade {

    private String tradeId;
    private int eventId;
    private String actionName;
    private ZonedDateTime tradeDate;
    private int counterPartyId;
    private boolean isSDREligible;
    private String USI;

    public Trade( String tradeId, int eventId, String actionName, ZonedDateTime tradeDate,
                   int counterPartyId, boolean isSDREligible, String USI ) {
        this.tradeId = tradeId;
        this.eventId = eventId;
        this.actionName = actionName;
        this.tradeDate = tradeDate;
        this.counterPartyId = counterPartyId;
        this.isSDREligible = isSDREligible;
        this.USI = USI;
    }

    public String getTradeId() {
        return tradeId;
    }

    public int getEventId() {
        return eventId;
    }

    public String getActionName() {
        return actionName;
    }

    public ZonedDateTime getTradeDate() {
        return tradeDate;
    }

    public int getCounterPartyId() {
        return counterPartyId;
    }

    public boolean isSDREligible() {
        return isSDREligible;
    }

    public String getUSI() {
        return USI;
    }

    @Override
    public String toString() {
        return "Trade{" +
                "tradeId='" + tradeId + '\'' +
                ", eventId=" + eventId +
                ", actionName='" + actionName + '\'' +
                ", tradeDate=" + tradeDate +
                ", counterPartyId=" + counterPartyId +
                ", isSDREligible=" + isSDREligible +
                ", USI='" + USI + '\'' +
                '}';
    }
}



月曜日, 12月 30, 2013

Java8 新しい Date and Time API

Java8の新機能の一つが新しいDate and Time API(JSR-310)の追加だろう.ご存じの通り標準SDKに付属していた従来のDate関連のクラスは機能が貧弱であったり,Calendarクラスmutabilityに起因する懸念から,Joda Timeを使っていた.
この新しいDate and Time API(JSR-310)を使うか,Joda Timeを使い続けるかはあなた次第だが,少なくとも旧来のDateの実装で無理をし続ける必要だけはなさそうである.

ちなみに以下のサイトは良質なDate and Time APIのサマリ,Joda TimeとJSR-310の比較記事だと思う.

http://sssslide.com/www.slideshare.net/JustinSDK/2013-java-developer-day-joda-timejsr310
http://howtodoinjava.com/2013/05/15/date-and-time-api-changes-in-java-8-lambda/

LocalDate, ZoneDateTimeそしてDateTimeFormatterの使用例

import java.time.LocalDate;
import java.time.ZoneId;
import java.time.ZonedDateTime;
import java.time.format.DateTimeFormatter;
import java.time.format.DateTimeFormatterBuilder;

/**
 * Created by morinoko on 12/29/13.
 */
public class Kerorin {

    public static void main( String args[] ) {

        LocalDate date = LocalDate.now();
        System.out.println( "today:" + date );
        System.out.println( "after five days from today:" + date.plusDays(5) );
        //ZoneId.getAvailableZoneIds().forEach(x -> System.out.println(x));
        ZonedDateTime zTime = ZonedDateTime.now(ZoneId.of("America/New_York"));
        DateTimeFormatter fmt = new DateTimeFormatterBuilder().append( DateTimeFormatter.ISO_DATE )
                .appendLiteral("-")
                .appendZoneId().toFormatter();

        System.out.println( fmt.format( zTime ) );
        System.out.println( "Converting to JST" );
        System.out.println( fmt.format( zTime.withZoneSameLocal( ZoneId.of( "Asia/Tokyo" ) ) ) );
      }

}



Java8 ラムダ

関数言語の使用者には十二分におなじみのlambda式がついにJava バージョン8で正式採用である.今まで無名クラスを書いてはコードが汚れるたびに,関数ポインタのように書ければなぁ,と思っていたのだが..これからはLambda式で綺麗にかけるようになるわけである.実にありがたい.

Lambda式を使ってリストをソート後ダンプ

import java.util.Arrays;
import java.util.List;

/**
 * Created by morinoko on 12/29/13.
 */
public class Tanukin {

    public static void main( String args[] ) {

        List<String> list = Arrays.asList( new String[]{"tanu", "tanuku", "hello"} );
        list.sort( (l,r) -> l.length() - r.length()  );
        list.forEach( s -> System.out.println( s ) );

    }

}
C++での例
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
using namespace std;

bool cmp(const string& l, const string& r) { return l.size() < r.size(); }
void dump(const string& s){ cout << s << endl; }

int main() {

 vector<string> v;
 v.push_back( "tanu" ); v.push_back( "tanuku" ); v.push_back( "hello" );
 sort( v.begin(), v.end(), cmp );
 for_each( v.begin(), v.end(), dump );
 
}


土曜日, 11月 16, 2013

C++ STL - Partition関数

STL algorithmのpartition関数は特定の要素をリスト中で仕分けできる便利な関数なので覚えておくとよいことが色々あるかも.以下の例はファイル名のリスト中jpegファイル名の要素とそうでない要素を分類する例.

#include <string>
#include <algorithm>
#include <vector>
#include <iostream>
#include <sstream>
using namespace std;

static vector<string> JPEG_POSTFIX;

void init() {

 JPEG_POSTFIX.push_back(".jpg");
 JPEG_POSTFIX.push_back(".jpeg");

}

bool IsJpeg(const string& s) {
        // should use boost's to_lower, though!
 vector<string>::iterator iter;
 for(iter = JPEG_POSTFIX.begin();iter != JPEG_POSTFIX.end();iter++ ) {
  if(s.find(*iter) != string::npos)
   return true;
 }
 return false;

}

int main() {

 init();
 istringstream f("neko.jpg tako.jpeg ika.png rakko.gif fugu.jpg");
 vector<string> fileList;
 string s;
 while(getline(f,s,' ')) {
  fileList.push_back(s);
 }
 cout << "## before partitioning.." << is_partitioned( fileList.begin(),fileList.end(),IsJpeg ) << endl;
 for_each(fileList.begin(),fileList.end(),[](string& s){cout << s << " "; });
 partition(fileList.begin(),fileList.end(),IsJpeg);
 cout << endl << "## after partitioning.." << is_partitioned( fileList.begin(),fileList.end(),IsJpeg ) << endl;
 for_each(fileList.begin(),fileList.end(),[](string& s){cout << s << " "; });
 cout << endl;

 return 0;

}


月曜日, 11月 11, 2013

Java - StrSubstitutor

Apache Commons langからまた一つ便利なクラスのご紹介をさせていただきたい.
StrSubstitutorクラスは名前の通り文字列中のキーワード変換を行う.キーワードのプレフィックス・ポストフィックスの変更並びに変換後の値中のキーワードに対しての変換もサポートしている優れものである.この車輪の再発明はしないのが賢明だろう.

import java.util.HashMap;
import java.util.Map;

import org.apache.commons.lang3.text.StrSubstitutor;
import org.junit.Test;
import static org.junit.Assert.assertThat;
import static org.hamcrest.CoreMatchers.*;

public class StrSubstTest {

 @Test
 public void testSubst() {
  
  final String TEST_STR = "${PATTERN} cat";
  final String EXPECTED_STR = "black cat";
  
  StrSubstitutor subst = new StrSubstitutor( prepareValueMap() );
  assertThat( subst.replace( TEST_STR ), is( EXPECTED_STR ) );
  
 }
 
 @Test
 public void testSubstWithPrefix() {
  
  final String TEST_STR = "<<PATTERN>> cat";
  final String EXPECTED_STR = "black cat";
  
  StrSubstitutor subst = new StrSubstitutor( prepareValueMap(), "<<", ">>" );
  assertThat( subst.replace( TEST_STR ), is( EXPECTED_STR ) );
  
 }
 
 @Test
 public void testSubstInVariable() {
  
  final String TEST_STR = "${PATTERN} cat";
  final String EXPECTED_STR = "calico(white,black,brown) cat";
  
  StrSubstitutor subst = new StrSubstitutor( prepareValueMap2() );
  subst.setEnableSubstitutionInVariables( true );
  assertThat( subst.replace( TEST_STR ), is( EXPECTED_STR ) );
  
 }
 
 private Map<String,String> prepareValueMap() {
  
  Map<String,String> map = new HashMap<String,String>();
  map.put( "PATTERN", "black" );
  map.put( "SIZE", "big" );
  return map;
  
 }
 
 private Map<String,String> prepareValueMap2() {
  
  Map<String,String> map = new HashMap<String,String>();
  map.put( "PATTERN", "calico(${COLORS})" );
  map.put( "COLORS", "white,black,brown" );
  return map;
  
 }

}

水曜日, 10月 09, 2013

all of, any of, none of

リスト・配列要素検査の関数all_of,any_of,none_ofは是非覚えておくとよい.

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

using namespace std;

bool chk(string s) {
 return s.size() > 5;
}

int main() {

 vector<string> v;
 v.push_back("Warsaw");
 v.push_back("NewYork");

 // all of
 cout << ( all_of(v.begin(),v.end(),chk) ? "[GOOD] all good" : "some failed or all failed" ) << endl;
 v.push_back("Tokyo");
 cout << ( all_of(v.begin(),v.end(),chk) ? "[GOOD] all good" : "some failed or all failed" ) << endl;

 v.clear();
 v.push_back("Rome");
 v.push_back("Nagoya");

 // any of
 cout << ( any_of(v.begin(),v.end(),chk) ? "[GOOD] some good" : "all failed" ) << endl;
 v.erase( find( v.begin(),v.end(),"Nagoya"));
 v.push_back("Osaka");
 cout << ( any_of(v.begin(),v.end(),chk) ? "[GOOD] some good" : "all failed" ) << endl;

 // none of
 cout << ( none_of(v.begin(),v.end(),chk) ? "[GOOD] all failed" : "not all failed" ) << endl;
 v.erase(find(v.begin(),v.end(),"Osaka"));
 v.push_back("Mangalore");
 cout << ( none_of(v.begin(),v.end(),chk) ? "[GOOD] all failed" : "not all failed" ) << endl;

 return 0;

}


C++でforeach

ForeachはJavaやPythonといった他の言語で多用されている反復処理用構文である.
C++ではSTLのalgorithmがそれを提供してくれている.是非使おう.

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

using namespace std;

void show(const string s) {
 cout << s << ' ';
}

int main() {

 vector<string> v;
 v.push_back("Algonquin");
 v.push_back("Iroquois");

 for_each(v.begin(),v.end(),show);

 return 0;

}


lvalueとrvalue

C++のコンテクストでたまに見かける用語の一つがlvalueとrvalueである.
これを知らないと苦労することもあるかもしれないので是非覚えておいてほしい.

lvalue .. いわゆる変数・定数.2回以上使いまわされることもあるかもしれないデータである.
rvalue .. いわゆる代入される又は出現後即揮発するデータ.

int i = 100 * 3;

とあればiがlvalue, 100 * 3 がrvalueである.

インライン関数

Q. classの宣言中に関数を定義した場合,その関数はインライン扱いされるか?

A. yes



土曜日, 8月 03, 2013

プチクイズ8 - コピーコンストラクタ

Q. 以下のコードのコンパイル&実行結果は?

#include <cstdio>
#include <cstdlib>
#include <string>

class C {
private:
 int d;
public:
 C() { d = 5;};
 ~C() {};
 C(C m) { d = m.d; }
 virtual void a() { printf("aaa"); }
 int GetD() { return d; }
};

int main() {

 C m;
 C m2(m);
 
 printf("%d\n",m2.GetD());
}

A.
大抵のコンパイラではコンパイルできないはず.上記コピーコンストラクタは値渡しのパラメータが定義されているので,このコピーコンストラクタが呼ばれ,ランタイム上で値渡しのパラメータmを”コピー”しようとコピーコンストラクタを更に呼び... と永遠に再帰呼び出しが発生する.
この問題を避けるには,const C&にパラメータの宣言を変更すればよい.

プチクイズ 7 - クラスのsizeof

Q1. 空のクラスに対してのsizeofの結果は?

A1. (visual studioでもgnu c++でも)1.実質データは0だがクラスの存在を示すためにダミーのデータ(size 1)が作られる.

Q2. コンストラクタとデストラクタを宣言した場合?

A2. 変わらず.ただしvirtualであればvtableを作るのでその分のサイズは増える.32bitマシン上なら4, 64bitマシン上なら8.

Q3. 関数を宣言すると?

A3. コンストラクタ・デストラクタに同じ.virtualであればvtable分の増加,さもなければ何も変わらず.

Q4. intの変数をクラスに追加すると?

A4. int型分のサイズが増加.

アルゴリズム問題を解く 13 - 回文

問題

Please implement a function that checks whether a positive number is a palindrome or not.
For example, 121 is a palindrome, but 123 is not. Please write an answer in C.
( Coding interviewsより抜粋 )

ヒント

山本山,とかたけやぶやけた,に共通するのは,文字列長が奇数であることである.この問題はマイナスでない整数であることも忘れずに.

答え1

先頭と最後尾,先頭+1と最後尾-1..を比較していけばよいのでO(N/2)の計算量でよい.
NULLの場合,負の場合等々といったチェックも忘れずに.

#include <cstdio>
#include <cstdlib>
#include <string>

int isdigits(const char* const s, int len) {

 int result = 1;
 for( int i = 0;i < len;i++ ) {
  if( !isdigit(s[i]) ) {
   result = 0;
   break;
  }
 }

 return result;

}

int ispalindrome(const char* const s, unsigned int len) {

 // prerequisite check
 if( s[0] == '-' ||
  !(len % 2) ||
  len == 1 ||
  s == NULL ||
  !isdigits(s,len))
  return 0;
  
 int result = 1;
 unsigned int half = len >> 1;
 for( unsigned int i = 0;i < half;i++ ) {
  if(s[i] != s[len-1-i]) {
   result = 0;
   break;
  }
 }
 return result;
}

int main() {

 char* s1 = "142";
 char* s2 = "5";
 char* s3 = "282";
 char* s4 = "2820";
 char* s5 = "-10";
 char* s6 = "ABA";
 printf("%d\n",ispalindrome(s1,strlen(s1)));
 printf("%d\n",ispalindrome(s2,strlen(s2)));
 printf("%d\n",ispalindrome(s3,strlen(s3)));
 printf("%d\n",ispalindrome(s4,strlen(s4)));
 printf("%d\n",ispalindrome(s5,strlen(s5)));
 printf("%d\n",ispalindrome(s6,strlen(s6)));

 char ch;
 scanf(&ch);
}

答え2

答え1よりはるかに優れたコードである.

#include <cstdio>
#include <cstdlib>
#include <string>

int ispalindrome(unsigned int n) {

 if( n <= 110 )
  return 0;

 unsigned int orig = n;
 unsigned int rev = 0;
 while( n != 0 ) {
  rev = rev * 10 + n % 10;
  n /= 10;
 }

 return (rev == orig) ? 1 : 0;

}

int main() {

 unsigned int s1 = 142;
 unsigned int s2 = 5;
 unsigned int s3 = 282;
 unsigned int s4 = 2820;
 unsigned int s5 = 111;

 printf("%d\n",ispalindrome(s1));
 printf("%d\n",ispalindrome(s2));
 printf("%d\n",ispalindrome(s3));
 printf("%d\n",ispalindrome(s4));
 printf("%d\n",ispalindrome(s5));

}

金曜日, 8月 02, 2013

constの使い方

面接をしていて感じたのが,意外にconstの使い方をわかっていない又は誤って理解しているケースも多いということである.

constの正しい用法はcode as documentationとして重要なのでしっかり理解しておきたいところ.

int i = 500;
// 1. 
const int* pVal = &i;
// 2.
int* const pVal = &i;
// 3.
const int* const pVal = &i;

1はconst修飾子が適用されたint型,つまり定数intを指すポインタである.
ゆえにポインタを経由してpValの値を変更することはコンパイラが許可しないが,pVal自体別のconst int型を指し示すことはできる.

2はint型を示すconst修飾子が適用されたポインタ,言い換えるとそのポインタの持つ値,つまりはアドレスの変更が不可能なポインタである.ポインタ経由でiの値を変更することは認めるが,i意外の変数を指し示すことは許さない.

3は定数int型を示す定数ポインタである.ポインタ経由での値の変更も許されなければ,またポインタの指す値を変えることも出来ない.




金曜日, 7月 26, 2013

マージ

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


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

}

マージソート

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

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


#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

木曜日, 7月 18, 2013

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

SafeC++にはvectorに要素が多く積み込まれると,リサイズ(デフォルトサイズは恐らく16)により,ベクタは他のメモリアドレス上にコピーを作りそこにデータをコピーする,とあった.それが本当であるならば,コンポジションクラス中の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;

}



水曜日, 7月 17, 2013

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++ではスマートポインタを使って,更にデストラクタを空にしたならば,むしろコンストラクタから例外を投げることも悪くはないと述べている.

土曜日, 7月 13, 2013

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

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

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

月曜日, 7月 08, 2013

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

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;

}

日曜日, 7月 07, 2013

アルゴリズム問題を解く 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;
 }

}


木曜日, 7月 04, 2013

アルゴリズム問題を解く 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()は先頭から5番目の要素までサンプリングをする - 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;
}

水曜日, 7月 03, 2013

プチクイズ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;
}

月曜日, 7月 01, 2013

プチクイズ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 .. 2分探索?2分探索でも勿論解ける.しかしバイナリサーチより効率の良いアルゴリズムは?

解答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;

}

日曜日, 6月 23, 2013

Algorithm 問題を解く 6 - ハッシュ

ハッシュ

ハッシュはバイナリサーチよりも効率的に検索をしたい場合に必須になるアルゴリズムである.
手短にハッシュを説明すれば,

  1. 一程度のメモリ領域をハッシュバケットとして確保
  2. ハッシュコードを要素から算出し,そのハッシュコードを検索キーとしてハッシュバケット中の1スロットに挿入

となる.例えば以下のハッシュバケット領域があったとして
0x0000 .. NO DATA
0x0001 .. NO DATA
0x0002 .. NO DATA
あるデータ X を保存したいとする.Xのハッシュキーが2だったらば,上記のハッシュバケットは
0x0000 .. NO DATA
0x0001 .. NO DATA
0x0002 .. { X }
となる.
検索はハッシュキーを元にデータを検索し,計算量はO(1)であり,2分検索の平均O(logN)より効率的である.

ハッシュコリジョン

当然,別のデータが同じハッシュキーを持つことがある.そういった場合はそのハッシュキーのスロットは大抵は循環リストのデータ構造を持つか,または別の空きスロットを見つける(オープンアドレッシング)する.最悪の場合の計算量はO(n)となる.


問題

Given a dictionary of English words, return the set of all words grouped into subsets of words that are all anagrams of each other.

Algorithms for Interviews より引用.


解答

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

list<string> dict;

void init_dict() {

 dict.push_back( string("dog") );
 dict.push_back( string("god") );
 dict.push_back( string("redrum") );
 dict.push_back( string("murder") );
 
}

void analyze( list<list<string>> ls ) {

 list<string> l;
 string s;
 map<int,list<string>> m;
 list<string>::iterator iter;

 for( iter = dict.begin();iter != dict.end();iter++ ) {

  int sum = 0;
  s = *iter;
  for( int i = 0;i < s.length();i++ ) {
   sum += s[i];
  }
  if( m.find(sum) == m.end() ) {
  
   l.clear();
   l.push_back(*iter);
   m[sum] = l;

  }
  else {

   l = m[sum];
   l.push_back(*iter);
   m[sum] = l;

  }

 }

 map<int,list<string>>::iterator mapIter;
 pair<int,list<string>> t;
 for( mapIter = m.begin();mapIter != m.end();mapIter++ ) {
  t = *mapIter;
  cout << t.first << ":{";
  list<string>::iterator li = t.second.begin();
  for(;li != t.second.end();li++)
   cout << li->data() << ",";
  cout << "}" << endl;

 }



}


int main() {

 init_dict();
 list<list<string>> ls;
 analyze(ls);
 list<string>::iterator iter;
 for( iter = dict.begin();iter != dict.end();iter++) {
  cout << (*iter).c_str() << endl;
 }

 return 0;
}


木曜日, 6月 20, 2013

C++ 標準関数 おさらい 1 .. strtol, strtod, strtof

充実のC++標準ライブラリ

C++標準ライブラリは大変優れています,というのはいうまでもない....勿論boostを使わないとできないことも多々あるが,それでもまずC由来のライブラリと合わせてこの標準ライブラリを使いこなせるようになれば大抵のことは出来るはず.

strtol, strtod, strtof - 文字列から数値型に変換

strtol, strtod, strtof -これらの関数はそれぞれconst char*をそれぞれlong型,double型,float型に変換する.strtolは指定した底から10進数に変換することもできる.似たような関数にatoi,atof,atolがある(atodはない,atofはdoubleを返す)が,N進数パース等といった機能も含めるとstrto系のほうがお勧めだ.ちなみにヘッダはcstdlid. long longに変換するstrtoll,long doubleへのstrtold, unsigned long longへのstrtoullもちゃんとある.

Javaでは

それぞれLong.parseLong(), Double.parseDouble(), Float.parseFloat().


サンプル

O'reillyのC++ Cookbookのサンプルコードをほぼ引用したうえで,自作のmyhex2int()で16進数->10進数変換するコードを足してみた.底変換のコードはもっときれいにかけるはずだがご愛嬌.

#include <iostream>
#include <string>
#include <cstdlib>
#include <cmath>
#include <map>

using namespace std;

static map<char,unsigned int> nummap;

long hex2int(const string& hexStr){

 char *offset;
 if(hexStr.length() > 2) {
  if(hexStr[0] == '0' && hexStr[1] == 'x')
   return strtol(hexStr.c_str(), &offset,0);

 }
 return strtol(hexStr.c_str(),&offset,16);
}

static void init_map() {

 for( char ch = 0x30;ch < 0x40;ch++ )
  nummap[ch] = ch-0x30;
 for( char ch = 0x61;ch < 0x67;ch++ )
  nummap[ch] = ch-0x31;

}

long myhex2int(const string& hexStr){

 double repeat = 0;
 int t = 0;

 init_map();
 int sum = 0;

 if(hexStr.length() > 2 && hexStr[0] == '0' && hexStr[1] == 'x') {
  for(int i = hexStr.length() - 1,repeat = 0;i > 1;i--,repeat++){
   sum += ( nummap[hexStr[i]] * pow(16.0,repeat) );
  }
 }
 else {
  for( int i = hexStr.length() - 1,repeat = 0;i >= 0;i--,repeat++){
   sum += ( nummap[hexStr[i]] * pow(16.0,repeat) );
  }
 }
 return sum;

}

int main() {

 string str1 = "0x1234";
 cout << hex2int(str1) << endl;
 string str2 = "1234";
 cout << hex2int(str2) << endl;
 string str3 = "QAFG";
 cout << hex2int(str3) << endl;
 cout << "--- my(hex) ---" << endl;
 cout << myhex2int(str1) << endl;
 cout << myhex2int(str2) << endl;
 
        return EXIT_SUCCESS;
}

土曜日, 6月 15, 2013

UNIXコマンド One liner 4

あるディレクトリ以下の,rootユーザ又はルートグループが所有しているファイル又はディレクトリを再帰的に探し表示
この結果はノイズを含む可能性がある.

find *|xargs ls -al|egrep root

月曜日, 6月 10, 2013

TopコマンドのRES,VIRT,SHR

Topコマンド

管理者のみならず開発者,そして私のようなアーキテクトにとっても良い友人のTopコマンド.その友人がもたらしてくれる情報の内,VIRT,RESそしてSHRの意味合いをもう一度おさらいしておく.

VIRT (Virtual Image )

VIRTはプロセスの
  • コード
  • データ
  • ライブラリ
  • スワップアウトしたページ
  • メモリマップドファイル
の内,まだ使用されていないものの合計であるわけで,全てがメモリを指しているわけではないので注意.C/C++コードでただnew或いはmallocしただけだと,確保した分がVIRTのサイズに上乗せされる.Windowsでいうところのコミットチャージか.

RES (Resident Memory)

RESは実際にプロセスに利用されているデータの総計を示している.Javaで大きなヒープを確保していたり,C/C++でたくさんnewあるいはmallocしているとRESとVIRTの差が大きくなる.Windowsでいうところのワーキングセットである.

SHR (Shared Memory)

ライブラリなど,他のアプリケーションからも利用される可能性のあるメモリの総計である.

蛇足 - PSで指定したプロセスの情報だけ見る

ps -pオプションで指定したプロセスの情報を見ることが出来る.

UNIXコマンド One liner 3

特定のプロセス(ここではbigというプログラム)のPIDとパスをreport.txtにダンプし表示

egrep -vでps -ef中のegrepのPIDを除外.


ps -ef|egrep ./big|egrep -v egrep|awk 'print{$2,$8}' > report.txt;cat report.txt

UNIXコマンド One liner 2

特定のワード(ここではGETをPOSTに)を置換して別名ファイルとして保存

rm -fr conv;mkdir conv;for f in `find * -prune -type f`;do sed -e 's/GET/POST' $f > conv/%$f.conv;done

火曜日, 6月 04, 2013

UNIXコマンド One liner 1

UNIXシェルは奥深い

UNIXシェルの奥の深さは底知れない.あなたがもし何かの処理の為のスモールプログラムを書くつもりならば,UNIXシェルだけで95%のことは出来る,ということをまず考えたほうが良い.何十行のプログラムやスクリプトでできることはシェルの一行でできるはずだ.

一行で色々やってみる

以下は一行で色々やってみたという参考例.実際に私の仕事のうち,データ解析,大量のファイルデータ処理等はR/SQL/スクリプトを書く以前に,大概ワンライナーシェルスクリプトの組み合わせである程度まで出来る.

特定のファイルのサイズ総計を表示

find *Neko*|xargs ls -al|gawk '{s+=$5} END {print s}'

全ての.txtファイルのサイズが大きい順トップ10のファイル名とサイズを表示

find **/*.txt|xargs ls -alSr|awk '{print $9,$5}'|tail -10

全ての.txtファイルのサイズが小さい順トップ10のファイル名とサイズを表示

find **/*.txt|xargs ls -alSr|awk '{print $9,$5}'|head -10

又は

find **/*.txt|xargs ls -alS|awk '{print $9,$5}'|tail -10

あるgzipされたファイルの,パイプで区切られたデータの4行目の内容を使ってソート,多かったデータの上位5件を表示

zcat data.txt.tar.gz|cut -f4 -d"|"|uniq -c|sort -nr|head -5


月曜日, 6月 03, 2013

sudo設定1 .. 権限の委譲とパスワードプロンプトの抑制

権限移譲は慎重に

sudoを効果的に使えることは,ある程度以上の規模のサーバ管理を複数人で行うとすれば必要になってくるのだろう.今回は権限の委譲とパスワードプロンプト抑制というテーマである.
ターゲットは極私的な,しかも完全に安全なところに配置されているラボラトリサーバである.会社や大学の一般のサーバ上では権限の委譲はある程度良いにしてもパスワードプロンプト抑制はおこなわないように.

グループ作成

ここではADM_LIMITEDというグループを作成し,特定のパワーユーザをこのグループに属させ,そのグループを経由してroot権限を委譲する.

まずは以下のコマンドでグループ ADM_LIMITEDを作成,そしてユーザをそのグループに属させる.

groupadd ADM_LIMITED
usermod -G ADM_LIMITED tanuchan


新規ユーザをそのままグループに属させたいならばuseraddの-gオプションを使う.
とりあえずidコマンドでユーザのグループ情報を確認しておこう.グループは基本は追加すること.リプレースは危険だ.

sudoviで編集

sudoの設定ファイルは/etc/sudoersであるが,直接ファイルを編集すべきでない.代わりにvisudoコマンドを使うべきである.visudoコマンドは編集後自動的にバリデーションを行ってくれて,バリデーションに失敗した時は what now? と編集に戻るかどうか聞いてくれるので安全だ.ちなみにrootまたはそれに準ずる権限でvisudoコマンドを実行すること.


権限移譲とパスワードプロンプト抑制

visudoコマンド実行後,sudoersファイルが開かれる.ポインタをずっと下げていくと Allows people in group wheel to run .. というセクションが見つかる. そこらへんに以下のような行を追加.
%ADM_LIMITED ALL=(ALL) ALL
%ADM_LIMITED ALL=(ALL) NOPASSWD: ALL

これを保存すれば,全てのADM_LIMITEDユーザがパスワード入力なしで任意のコマンドをsudo経由で実行できる.sudo (ver 1.8.6p7)は毎回/etc/sudoersを読みにいくので何かのプロセスを再起動等は必要ない.ただし,新しいグループに対する変更はどうやらサーバのリブートが必要かもしれない.

個人にroot権限を付与できるが

これは出来るだけやめておこう.極私的なサーバで,一切公開の予定無しという環境であれば問題ないが,拡張性等の点からいってもベストプラクティスではないのでできるならグループ経由で権限移譲をしよう.

日曜日, 6月 02, 2013

Sambaサーバのセットアップメモ

Sambaサーバ

最近sambaサーバを再インストールするはめになったので,ついでにメモを当ブログにアップロードしておく.
ちなみにこのメモはFedora18を対象としている.他のディストリビューションとは手順4のステップが恐らくことなるだろう.

手順1. インストール

sudo yum install samba

手順2. smb.conf編集

cd /etc/samba,そしてsmb.confを編集.

workgroup = [任意のワークグループ]
netbios name = [任意の名前]
hosts allow = [アクセスを許可するホストのIPaddress, 192.168.1. で192.168.1/24ネット全体を許可 )


手順3. share directoryを作成

シェアしたいディレクトリを作成し,そのエントリをsmb.confに追加

[shareddir]
comment = shared dir
path = /home/[userdir]/shared
public = yes
writable = yes
printable = no
browsable = yes

手順4. サービスの起動及び登録

Fedora18はinit.dではなくsystemdをデフォルトでつかっているようである.
なので以下のコマンドを発行.


systemctl start smb.service
systemctl start nmb.service
systemctl enable smb.service
systemctl enable nmb.service


土曜日, 6月 01, 2013

C++ - コンソールのプログレス表示

コンソールでプログレスを表示するには

rpmのvオプションをつけた時やyumの出力等で見かける,同じラインで進捗状況を出力する機能.コマンドラインユーティリティを作る際は遅かれ早かれ必要になることも多いはず.個人的には多いのでいちおうメモということで.

ちなみにC++と題してはいるがこの方法は他の言語でも使えるはず.

コード

肝心なポイントは \r(キャリッジリターン)だけを表示すること,そしてバッファをマニュアルでフラッシュすること.少なくともgnu g++のcoutは改行をしないとバッファを標準出力にフラッシュしない.
#include <iostream>
#include <unistd.h>
#include <cstdlib>
using namespace std;

int main() {

    string progress = "progress..";
    cout << "starting.." << endl; 
    for( int i = 0;i < 10;i++ ) {

        progress += "#"; 
        cout << progress << "\r" << flush;
        sleep( 1 );
    }

    cout << endl << "done." << endl;

    return EXIT_SUCCESS;

}

日曜日, 5月 26, 2013

Fedora18にChromeをインストール

Missing Security Signatures

Googleからchromeのrpmをダウンロードしてインストールしようとしても,Fedora18ではMissing Security Signaturesというエラーが出てインストールできない.
仕方がないので以下のサイトからrpmをrpmコマンドから直にダウンロードしてインストールする.
rpm -ivh https://dl.google.com/linux/direct/google-chrome-stable_current_i386.rpm


日曜日, 5月 19, 2013

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

Voidポインタの役割

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

つかいどころ

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

サンプル

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

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

}



土曜日, 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;
}

木曜日, 5月 16, 2013

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

C++ のキャスト

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

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


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

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

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

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

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

以上の自問について,あなたが自分と(可能ならば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


水曜日, 5月 15, 2013

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

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

STLコンテナに自作クラスをストアさせたいことはよくあるはず.
そうしたい場合はクラスを定義する際に以下のことを留意することが大事である.

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

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


コード

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


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

}

火曜日, 5月 14, 2013

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

C++

周りの新人や,面接等をしている限りひしと感じるのは,とにかくC/C++を知っている人がどんどん減ってきていることである.私はJavaをやっていて..というのが8割方,9割,いや,もうほとんど10割である.時代の流れである.この流れをとやかく言うつもりはないし,ニーズも多いのは間違いない.なにしろ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()と同じである.

日曜日, 5月 12, 2013

Deadlock

デッドロックの定義

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

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

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

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

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

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

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


ここに変数A変数Bの二つのデータと、BにAの値を加算し、Aを0にする処理AAに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

土曜日, 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 モードの2つがあり,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;
  
 }
 
}


木曜日, 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() ) );
  }
 }




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)である.ならば両配列がソート済みというヒントに注目したい.このヒントは明らかに2分探索して要素を探りなさい,といっているではないか.

コードは以下の通り.注意すべきは短い配列を最初のループにすること.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;
}



月曜日, 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()) + " ");
  }
 }

}




日曜日, 4月 28, 2013

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

AppendText関数を使うべし

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


火曜日, 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のオーダの計算量で収まる.


日曜日, 4月 14, 2013

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

問題

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]

私の解答は以下の通り.
ロジックとはしては調べたいインデックスを2分木で絞り込む.調べたい値targetと2分木の中央要素v.at(mid)が等価ならばそのインデックスを返し,2分木探索終了時まで見つからなければ問題の指示通り-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を使用する為に必要.

アルゴリズム基本編 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;
}

金曜日, 4月 12, 2013

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

最初は知らず..

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

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


水曜日, 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() ) );
 }
}

火曜日, 4月 09, 2013

Algorithm 問題を解く2 - バイナリサーチ(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 )

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

解.


#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 ) を合わせても十分見合うことがわかる.