C++: Union-Find data structure

Union-Find木の実装

こちらの習作、というかそのまんま。
http://www.prefield.com/algorithm/container/union_find.html

   1: #include <vector>

   2: #include <algorithm>

   3:  

   4: struct UnionFind {

   5:   std::vector<int> data;

   6:   UnionFind(int size) : data(size, -1) {}

   7:   bool Union(int x, int y) {

   8:     if ((x = Root(x)) == (y = Root(y))) return false;

   9:     if (data[y] < data[x]) std::swap(x, y);

  10:     data[x] += data[y]; data[y] = x;

  11:     return true;

  12:   }

  13:   bool IsSame(int x, int y) { return Root(x) == Root(y); }

  14:   int Root(int x) { return data[x] < 0 ? x : data[x] = Root(data[x]); }

  15:   int Rank(int x) { return -data[Root(x)]; }

  16: };

rank がアンダーフローしたらどうなる？

Vrapper – Eclipse plugin for vi-like editing

vi キーバインドの Eclipse プラグイン

Vrapper をインストールすれば、Eclipse でvi(Vim)ライクのエディタを利用することができる。
Eclipse のインストール場所に「http://vrapper.sourceforge.net/update-site/stable」を追加して実行すればよい。

eclipse のコマンドとの競合を防いだり、新しいコマンドを登録するためには「~/.vrapperrc」を作成する。

少なくともWindows Vistaでは「.vrapperrc」という名前でファイルが作れなかったので、一旦他の名前のファイルを作成してからコマンドプロンプトから「move」した。（保存先は %homedrive%%homepath% 配下）

参考：
http://vrapper.sourceforge.net/home/　（本家）
http://d.hatena.ne.jp/yuroyoro/20100218/1266477264
http://d.hatena.ne.jp/basyura/20100913/p1

How to disable window resizing in Firefox

Firefox: ウィンドウサイズ変更の無効化

Firefox の以下のオプション設定で、Webページのスクリプトによるウィンドウサイズ変更を無効化できる。

・メニュー => オプション => コンテンツ => JavaScript を有効にする - 詳細設定

「ウィンドウの移動または大きさの変更」のチェックを外せばよい。

C++: Initialize a multidimensional array with std::fill()

STL の std::fill() アルゴリズムによる多次元配列の初期化

こちら（http://mogproject.blogspot.com/2011/05/c-vector.html）同様、
マクロ＋テンプレートで実現。

   1: #define FILL(ptr, value) FILL_((ptr), sizeof(ptr) / sizeof(value), (value))

   2: template <typename T>

   3: void FILL_(void* ptr, size_t size, T value) {

   4:   std::fill((T*)ptr, (T*)ptr + size, value);

   5: }

・使用例

   1: int a[3][3];

   2: char c[2][2][2];

   3: FILL(a, 5);

   4: FILL(c, 'X');

   5:  

   6: for (int i=0; i<3; ++i) for (int j=0; j<3; ++j)

   7:   std::cout << a[i][j] << " ";

   8: std::cout << std::endl;  // "5 5 5 5 5 5 5 5 5 "

   9: for (int i=0; i<2; ++i) for (int j=0; j<2; ++j) for(int k=0; k<2; ++k)

  10:   std::cout << c[i][j][k] << " ";

  11: std::cout << std::endl;  // "X X X X X X X X "

How to flush memory on an Oracle instance

Oracle: メモリフラッシュのコマンド

性能検証を行う前など、ライブラリ・キャッシュやデータベース・バッファ・キャッシュをクリアしたい場合、
以下のコマンドをSYSDBA権限で発行すれば、インスタンスを再起動する必要はない。

・ライブラリ・キャッシュなど共有プールのフラッシュ

   1: ALTER SYSTEM FLUSH SHARED_POOL ;

・データベース・バッファ・キャッシュのクリア　※Oracle 10g以降のみ

   1: ALTER SYSTEM FLUSH BUFFER_CACHE ;

（注意）　同一インスタンス上で実行中の全てのSQLに影響が発生する。（結果レコードが返されないなど）

参考：
http://www.shift-the-oracle.com/dba_tips_optimizer.html

C++: Compilation error 'unresolved overloaded function type' in std::transform

C++: transform 関数での unresolved overloaded function type コンパイルエラー

G++で以下のコードをコンパイルするとエラーが発生する。

   1: #include <iostream>

   2: #include <deque>

   3: #include <algorithm>

   4: #include <cmath>

   5:  

   6: using namespace std;

   7:  

   8: int main() {

   9:   deque<double> radians(1, 3.14), sines(1);

  10:  

  11:   transform(radians.begin(), radians.end(), sines.begin(), sin);

  12:   cout << sines[0] << endl;

  13: }

・エラー

   1: error: no matching function for call to 'transform(std::deque<double>::iterator, std::deque<double>::iterator, std::deque<double>::iterator, <unresolved overloaded function type>)'

 

sin関数は、G++の「cmath」において以下のようにオーバーロードされている。

   1: inline float

   2: sin(float __x)

   3:  

   4: inline long double

   5: sin(long double __x)

   6:  

   7: template<typename _Tp>

   8:   inline typename __gnu_cxx::__enable_if<__is_integer<_Tp>::__value, 

   9:       double>::__type

  10:   sin(_Tp __x)

一方、transformのテンプレート引数では、テンプレート関数のsinについて推論することができない。そのため、どのsin関数を使えばいいのか分からない状態となってしまい、エラーが発生する。

以下のように、sin関数の型を指定すれば動作するようになる。

   1: transform(radians.begin(), radians.end(), sines.begin(), (double(*)(double))sin);

参考：
http://2bangai.net/read/c582add4b3ec2e8b617ee5e942e57d68c6418eac78102818fd04c3cf09e42d80/301

C++: Printing all elements in a vector using operator

C++: vector の全要素の出力

「<<」演算子のオーバーロードによって vector の出力を簡単にできるようにする。

   1: #include <iostream>

   2: #include <vector>

   3:  

   4: template <typename T>

   5: std::ostream & operator<<(std::ostream & stream, std::vector<T> & v) {

   6:   stream << "[";

   7:   for(typeof(v.begin()) i = v.begin(); i != v.end(); ++i) {

   8:     if (i != v.begin()) { stream << ", "; }

   9:     stream << *i;

  10:   }

  11:   stream << "]";

  12:   return stream;

  13: }

  14:  

  15: int main() {

  16:   std::vector<int> iv;

  17:   std::vector<char> cv;

  18:  

  19:   for (int i = 0; i < 5; ++i) {

  20:     iv.push_back(i);

  21:     cv.push_back('A' + i);

  22:   }

  23:  

  24:   std::cout << iv << std::endl;

  25:   std::cout << cv << std::endl;

  26:  

  27:   return 0;

  28: }

・出力結果

   1: [0, 1, 2, 3, 4]

   2: [A, B, C, D, E]