題名なし
よくあるnext_permutationのサンプル
#include<iostream> #include<vector> #include<algorithm> void printvec( std::vector<int> &v){ for( int i = 0; i < v.size(); ++i ){ std::cout << v[i] << " "; } std::cout << std::endl; } int main(){ std::vector<int> v, e; v.push_back(1); v.push_back(2); v.push_back(3); printvec( v ); while( std::next_permutation( v.begin(), v.end() ) ) printvec( v ); return 0;
出力
1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1
ループを変えてみる
for( int i= 0; i < 12; ++i ){ std::cout << std::next_permutation( v.begin(), v.end() ) << " "; printvec( v ); }
出力
1 2 3 1 1 3 2 1 2 1 3 1 2 3 1 1 3 1 2 1 3 2 1 0 1 2 3 1 1 3 2 1 2 1 3 1 2 3 1 1 3 1 2 1 3 2 1 0 1 2 3
おお、覚えていらっしゃるのか。
複数の数字から３つ選んで三角形になるかどうかを調べるとかいう話
とある本に書いてあったオマケ話。多分こう。
1. ソートして、大きい方からウインドウサイズ３で配列を見る。
2. 一番大きい辺が残りの２辺の和より大きければ三角形を作らない。そうじゃなければ終わり。
3. 一番大きい辺と比べて、次に大きい辺と次の次に大きい辺を取ってきたというのに、それを足しても一番大きい辺にはかなわないんだから、残りの奴らには太刀打ち出来ないだろう。なので諦めて次行ってみよう。
#include <cstdlib> int cmp( const void *a, const void *b ){ return ( *( int* ) b - *( int* )a ); } int page21_nlogn( int n, int *a ){ qsort(a, n, sizeof(int), cmp); for( int i=0; i < n-2; ++i ){ int s = a[i] + a[i+1] + a[i+2]; if( s - 2 * a[i] > 0 )return s; } return 0; }
これならO(n logn)
たのむからバブルソートはしないで。
Jaro-Winkler距離
以前、スペルミスや「もしかして」系の機能の裏で動く技術としてわりと知られているLevenshtein距離についてちょっと書いてみました。
今回はそれと同様な用途に用いられがちなJaro-Winkler距離。
Jaro-Winkler距離というのは、Levenshtein距離同様に文字列同士の近さを数値化するアルゴリズムです。
距離って言っても、数値が小さいほうが遠いので気をつけましょう。cos距離みたいなかんじです。
こいつは、Jaro距離という、これまた謎の文字列類似度計測指標にすこしだけ改良を加えたもので、肝はJaro距離です。
その少しだけの改良というのは、（式を見る限り）プレフィックスのexact matchは重視しようか、という程度のもの。
で、パパっと作れると思ったら、意外とてこずった。
Jaro距離では文字同士の一致を取るのですが、マッチとする文字の文字位置に一定の範囲をもうけ、そのウインドウ内での一致を取ります。
また、文字位置の交換によるマッチが可能であるかどうか？という転置の考えも取り入れています。
この転置が曲者で、しばらくうんうんうなってました。
というわけでコード
// valid_distance = -1 : not consider distance between characters unsigned int getNumRangeMatchChar( const std::string &s1, const std::string &s2, const int distance = -1 ){ unsigned int l1 = s1.size(); unsigned int l2 = s2.size(); bool ignore_distance = false; if( distance < 0 ){ ignore_distance = true; } unsigned int counter = 0; for( unsigned int i = 0; i < l1; ++i ){ // setting search range unsigned int from = i; unsigned int under = l2; if(! ignore_distance ){ from = ( i < (unsigned int)distance ) ? 0 : i - (unsigned int)distance; under = ( i +(unsigned int)distance >= l2 ) ? l2 : i + (unsigned int)distance; } for( unsigned int j = from; j < under; ++j ){ if( s1[i] == s2[j] ){ ++counter; } // NOTICE : this code consider the case i == j ( both place and character match ) } } return counter; } std::string getRangeMatchChar( const std::string &s1, const std::string &s2, const int distance = -1 ){ unsigned int l1 = s1.size(), l2 = s2.size(); bool ignore_distance = false; if( distance < 0 ){ ignore_distance = true; } std::string ret = ""; for( unsigned int i = 0; i < l1; ++i ){ // setting search range unsigned int from = i; unsigned int under = l2; if(! ignore_distance ){ from = ( i < distance ) ? 0 : i - distance; under = ( i + distance >= l2 ) ? l2 : i + distance; } for( unsigned int j = from; j < under; ++j ){ if( s1[i] == s2[j] ){ ret += s1[i]; } // NOTICE : this code consider the case i == j ( both place and character match ) } } return ret; } unsigned int getNumTransposition( const std::string &s1, const std::string &s2 ){ unsigned int c = 0; for( unsigned int i = 0; i < s1.size() && i < s2.size(); ++i ){ if( s1[i] != s2[i] ){ ++c; } } return c; } // Error the case s1 & s2 are empty double getJaroDistance( const std::string &s1, const std::string &s2 ){ int distance = ( s1.size() > s2.size() ) ? s1.size() : s2.size(); if( distance < 0 ){ return -1; } distance = distance / 2 - 1; if( distance < 0 ){ return -1; } int match = getNumRangeMatchChar( s1, s2, distance ); int trans = getNumTransposition( getRangeMatchChar( s1, s2, distance ), getRangeMatchChar( s2, s1, distance ) ); double m = (double)match; double t = ( (double)trans ) / 2.; return ( m / (double)s1.size() + m / (double)s2.size() + ( m - t ) / match ) / 3.; } unsigned int getLengthOfCommonPrefix( const std::string &s1, const std::string &s2 ){ unsigned int c = 0; for( unsigned int i = 0; i < s1.size() && i < s2.size(); ++i ){ if( s1[i] == s2[i] ){ ++c; } else { return c; } } return c; } double getJaroWinklerDistance( const std::string &s1, const std::string &s2, const double scaling = 0.1 ){ if( scaling < 0 ){ return -1; } double j = getJaroDistance( s1, s2 ); return j + getLengthOfCommonPrefix( s1, s2 ) * scaling * ( 1 - j ); }
ミソは、マッチを取るときに軸足をstring1とstring2どちらにおいても同じ数字が得られるのだけど、
マッチした文字をマッチした順に並べると、軸足の置き方によって順番が変わるよね、という話。
Levenshtein距離より精度がいいぜ、という発言をたまに聞きますが、意味が分からないのでそういう考え方はしないほうがいいと思います。
ものの尺度なので。
Project Euler Problem 125
単なるブルートフォースなのだが、範囲が違うけど同じ数が出うることと、それを加算してはいけないことに1時間ハマって死にたい。何この凡ミス。
typedef unsigned long long int nat; vector<nat> gensqsq(nat lim){ vector<nat> sqsq; for(nat i=1;i*i <= lim;++i)sqsq.push_back(i*i); return sqsq; } bool ispalindromic( nat n ){ if( n >= 10 && n % 10 == 0 ) return false; deque<int> d; while( n ){ d.push_front( n % 10 ); n /= 10; } for( int i=0, j=d.size()-1; i <= j; ++i, --j ){ if( d[i] != d[j] ) return false; } return true; } nat pe125(){ set<nat> s; nat limit = 100000000; nat total = 0; vector<nat> sq = gensqsq(limit); for( nat from = 0; from < sq.size(); ++from){ nat seqsum = 0; for(nat to=from; to < sq.size(); ++to ){ seqsum += sq[(unsigned int )to]; if( to == from ) continue; if( seqsum >= limit )break; if( ispalindromic( seqsum ) ) s.insert( seqsum ); } } for( set<nat>::iterator itr = s.begin(); itr != s.end(); ++itr ) total += *itr; return total; }
boost::random見てみた
boost::random見てみた。
お、おお・・・うつくしい。なるほど、なるほど。
乱数生成器と生成される数値の型・範囲、分布モデル、を自由に決められる。
boost::variate_generator< 生成器, 分布モデル > hoge( 生成器のインスタンス, モデルのインスタンス )
個人的にはとても綺麗だなぁー、と感じました。
というのも、以前、確率分布モデルに任意の乱数生成器を組み合わせるテンプレートを書いたのだ。
template< class RandGen > class Gaussian{ void somefunc(){ ... RandGen::genreal(); ... } ... }; class RandBase{ public: virtual void init() = 0; virtual int genint() = 0; virtual double genreal() = 0; }; class MTRand{ static void init(){ ... } static int genint(){ ... } static double genreal(){ ... } };
という感じ。
まあ結局似たようなことをやっているんですが。
書いていた当時は、個別の数で初期化した複数の乱数生成器を使い分けるという方法が思いつかず、結局それは諦め手しまいました。
なるほど、乱数生成器のインスタンスを渡せばいいのかー。
当たり前っちゃあ当たり前だよなー。という感じ。
というわけで最近boostにうっとりしています。
すごいgenericな構造しているなぁ、Boostすごいなぁ、C++すごいなあ、と思う反面、
コードがどんどんわけ分からなく、かつ長くなっていくことに懸念を感じます。
ちょっと使うために書かなければいけないコードの量がハンパ無い。
そもそもC++の++って、なんで存在したんだっけとか思ってしまう。
また、boostを使うにあたってよく言われる障壁は、C++のgenericなプログラミングに慣れている必要があるということらしいですね。
先鋭化していくことで、できることは増えるんだけど、そこにたどり着くのに障害が多くて使ってもらえなきゃちょっとなあ、というのも同時に感じます。
そのうち、boostのラッパーとか誰か作ったりしちゃうんだろうか。
まあそもそもboostの目的がそういうユーザーをターゲットにしてなさそうなので別にいいのかもしれませんが。
個人的にはこんなに便利でウマいメシ食わなきゃ損だと思います。
なんだか宣伝っぽくなってしまった。
Project Euler Problem 73
71とほぼ一緒。
上限と下限が決め打ちされている分71より簡単。
natural f73(){
natural lowd = 3;
natural lown = 1;
natural highd = 2;
natural highn = 1;
natural counter = 0;
for(natural d = 12000; d > 1 ; --d){
for(natural n = (highn * d / highd) + 1; n > lown * d / lowd - 1; --n){
if(gcd(n, d) != 1){ continue; }
if(highn * d > n * highd){
if(lown * d < n * lowd){
//std::cout << n << " " << d <<std::endl;
++counter;
}else {
break;
}
} else {
continue;
}
}
}
return counter;
}
テンプレート・テンプレート・パラメータ in Visual C++ 2010
久しぶりに書きますね．
本日はVisual C++ 2010（下位バージョンはしらない）において，
テンプレート・テンプレート・パラメータを使う場合に，
デフォルトパラメータを用いたいときに起こった問題,
という極端にマニアックな問題についてメモっておきます．
その前に，本の宣伝をします．
/*begin ------------------------------ */
以前ブログにコメント下さった方が本を書いているらしいので，購入してみました．
…というか，以前から目を付けていたものなので，ブログってすごいなと思った次第です．
- 作者: επιστημη,高橋晶
- 出版社/メーカー: ソフトバンククリエイティブ
- 発売日: 2009/04/25
- メディア: 単行本
- 購入: 16人 クリック: 224回
- この商品を含むブログ (54件) を見る
こいつぁすげえ本だ．こういうのを待っていた．
…激しくマニアックな気がするけれど．
テンプレート教団の末席信者としてはこのような教典を見つけられて非常にうれしい限りです．
何だかんだ言ってテンプレートはすごく便利で，その技術をある程度網羅した本がほしいな，という気持ちの分かる人はこれを買うしかありません．
解説も分かりやすく，例も豊富で久々の良書な気がします．
ただすごい濃いので，僕には全てを一度に脳内インストール出来ません．
それでも全体をさらっておくと，
「こういう場合，テンプレートでなんかできたよな…」
↓
この本で調べる
という流れができるので，がんばって読んでみましょう．
この辺の技術はコンパイラとの対話の確率が飛躍的に上がるので嫌になりますが，
「あー，テンプレートにしておいて良かった…」
と思える瞬間がきっとくるはず．
皆さんテンプレートを大いに活用しましょう（布教活動）
/*end ------------------------------ */
そんなテンプレート教信者は今日もテンプレートをゴリゴリ書いていたわけなのですが，VC++2010でハマりました．
テンプレートを使っていて，とても便利で離れられない機能「ポリシー」．
クラス内での処理をコンパイル時に切り替えるもの(C++テンプレートテクニックより)とのことですが，こんなページを見ている人には，説明よりもコードでしょう．
namespace nsp{ class Def{ public: void f(){ std::cout<<"default\n"; } }; class Alt{ public: void f(){ std::cout<<"alternative\n"; } }; template<class Some_func = Default_func> class A{ public: Some_func sf; void g(){ sf.f(); } }; }; int main(){ nsp::A<> a; a.g(); return 0; }
このコードの出力はdefaultとなります．
mainの中の１行目をnsp::A
つまり，クラスの関数の処理を指定されたクラスに応じて切り替えることができます．すばらしい．
ポリシーを使ったクラスは（僕は）結構使うし，慣れるとその内普通のクラス感覚で使うようになります(僕は)．
そうすると，クラスをテンプレート引数としてとるようなテンプレートクラスを作るような場面にも遭遇すると思います．いや，僕が遭遇しました．
ここで使うのが，いわゆるテンプレート・テンプレート・パラメータというやつですね．
先ほどのポリシーを使ったクラスをパラメータとしてとるテンプレートクラスを考えた場合，以下のようになると思います．
#include <iostream> namespace nsp{ class Def{ public: void f(){ std::cout<<"default\n"; } }; class Alt{ public: void f(){ std::cout<<"alternative\n"; } }; typedef Def Default_func; template<class Some_func = Default_func> class A{ public: Some_func sf; void g(){ sf.f(); } }; template< template<class Some_func = Default_func>class T> class B{ public: T<> Z; void h(){ Z.g(); } }; }; int main(){ nsp::B<nsp::A> b; b.h(); return 0; }
Visual C++2010ではコンパイルが通りませんでした．何故だろう？
問題は，テンプレート・テンプレート・パラメータの宣言で，
template< template<class Some_func = Default_func>class T>
Visual C++ 2010では，宣言がnspスコープであるにもかかわらず，このDefault_funcのスコープを与えてやらなければいけないようです．
template< template<class Some_func = nsp::Default_func>class T>
g++ on cygwinではこの問題は起こりませんでした．
また，上のコードではデフォルトのクラスを使っていますが，
T<> Z;
デフォルトじゃない場合は問題が起こりませんでした．
T<Alt> Z;
同じような問題にぶち当たる人はレアすぎると思うのですが，
まあ，自分用メモということで．
vectorのイテレータから配列の添え字を取り出す
タイトルの通りなのですが、C++でSTLのvectorをいじっている時、
イテレータがvectorのどの要素（何番目）かを知りたいときがあると思います。
たとえば要素番号に何らかの意味を持たせていたりする場合です。
それ自体があまりいいやり方ではない気がしますが、それは置いておきましょう。
普通に++itrとかで直にイテレータをまわしている時は、
なんかカウンタ変数みたいなのを別個にインクリメントすればいいかもしれませんが、
findなどのアルゴリズムで返ってきたイテレータに対して要素番号が欲しいときはどうすればよいでしょうか？
返ってきたイテレータとbegin()で取得したイテレータの引き算で取得できます。
vector<int> v; vector<int>::iterator itr; for(int i=0; i<10; ++i) v.push_back(i); itr = find(v.begin(), v.end(), 3); cout << itr - v.begin() <<endl;
これは知らなかった。
僕「イテレータから添え字番号ってどうやって取得できますか？
師匠「え？できないよ。」
僕「やっぱりかー。こまったなー。」
師匠「うーん、begin()と引き算してみれば。知らないけど」
僕（やってみる）「げ、できましたよ！」
師匠「うそ！できるんだ！」
なお、他のコンテナだと駄目だと思います。やってみてないけど。
プログラミングのテキストについて
2009/07/14の日記について。
とまあ、Accelerate C++についてえらそうなことを書いたら、Amazonでも同じ様な書き込みがいっぱいでした。
なのでもうちょっと。
Amazonではすごくいい！っていう人と、ぜんぜん駄目！っていう人にぱっかり分かれています。
本の評価は読む人により過ぎるので、あくまで個人的意見です。
●初心者向けか？ → 内容はYes,文章はNo
データ型については、組み込み型スタートではなく、stringスタート。
ぱっとわかりやすい結果を得られる。反面、文章は結局それなりの知識がある人が「ああ、あれのことかな」と推測せざるを得ない部分が多い。
●移行組にとっては？ → 微妙
STLをとりあえず使わせてから、かなりしばらくしてからクラスの説明になっているところはいいのかな？という感じ。
Cからの移行組にとっては、いきなりSTLからってのは逆に抵抗があるかも。中身の良くわからないもを前提に話が進むのは気持ちが悪いかも。
Javaからの人にとってはすんなりだとおもう。
演習のあたりはまったく見ていないのでわかりません。
一応プログラム未経験者のために、高速な学習を、という風に銘打っているので、文章の難解さ（というよりわかりにくさ）、
翻訳の微妙さとか考えると、星一つ。
積極的にこの本を否定するわけではないけれども、売れているというのは不思議。もっといい本があるんじゃないでしょうか。
ところで僕がプログラミングを始めたのは中学1年生の頃で、N88-BASIC on PC-9821でした。
その後、中学卒業後、C++をさわりはじめたのですが、その時のテキストがこれ。
C++プログラミング〈Vol.1〉 (Computer Science Textbook)
- 作者: ハーベイ M.ダイテル,ポール J.ダイテル,Harvey M. Deitel,Paul J. Deitel,小嶋隆一
- 出版社/メーカー: ピアソン・エデュケーション
- 発売日: 1999/05
- メディア: 単行本
- 購入: 1人 クリック: 13回
- この商品を含むブログ (5件) を見る
グラフィックを簡単に操作できるBASICからC++にいきなり跳躍したのもきつかったですが、
この本もマジできつかった。当時はインクリメントなんて言葉も知らず、内容も専門的で、
ウェルカムハノイの塔だったのでだいぶ苦労しました。
今読むとすごいいい本だなぁと思う反面、やはり独習には向かないなと思うしだいです。
内容が充実しすぎています。
今は独習シリーズをはじめ、いい本がいっぱいあり、みなさん恵まれていますね。
でもC++なんて使う人はどんどん減っていくのでしょうか。
確かにわかりにくい言語ですし、ダブルスタンダードなんてもんじゃないし、C++0xになってもう何がなんだかわからなくなってきましたし。
ある意味ではプロフェッショナルのためのとも言えるかもですが、これまでの資産を無駄にできないので無理やりに延命し、
使い続けることでさらに仕様が肥大化し…というスパイラルに入ってしまっているような気もします。
何より需要が減っているんですかね。
むしろ需要は一定数必ずあるのだけど、ものすごい精鋭である必要がある世の中になってきているような気がします。
コードが書ける、ではなくて、すんげー最適化ができるとか、難しいアルゴリズムを実装できるとか。
