空想犬猫記

※当日記では、犬も猫も空想も扱っておりません。(旧・エト記)

Cron の設定メモ

Windows 7上でCygwinのCronを設定した。

cygrunsrvは管理者権限が必要なので、ショートカットを右クリックしてアドミニストレータとしてCygwinを起動する。サービスの登録は以下のコマンド

cygrunsrv --install Cron --path /usr/sbin/cron.exe \
    --neverexits --preshutdown --disp "Vixie's Cron" \
    --type auto --user "<domain>\\<user>" \
    --passwd <password>

サービスを削除するときは

cygrunsrv --remove Cron

とする

Firefox設定メモ ~MS PゴシックをMeiryo UIに置換~

Google Chromeが頻繁にクラッシュするのと、メモリ使用量が必要以上に多いので、Firefoxに戻ってきた。久々に帰ってきてみたら、UIがGoogle Chromeっぽくなっていて全然違和感がない。HTML5になってから動画の再生にもプラグインが必要なくなったので、プラグインは全てアンイストールないしdeactivateした。

やるべきことは、userContent.cssをいじって「MS Pゴシック」を「Meiryo UI」フォントに置き換えたくらい。Webブラウザの世界の技術も標準化が進み枯れてきたのか、オジサンの想像力が枯れてきたのか。

具体的には以下の2ステップ。

%APPDATA%\Mozilla\Firefox\Profiles\XXXXXXXX.default

以下に chrome というフォルダをつくって、userContent.cssというファイルを作成する。中身はかつてGoogle Chromeでサポートされていたユーザスタイルシートと同じで、たんに

@charset "UTF-8";
@font-face {
  font-family: "MS Pゴシック";
  src: local("Meiryo UI");
}

@font-face {
  font-family: "MS PGothic";
  src: local("Meiryo UI");
}

@font-face {
  font-family: "MS P明朝";
  src: local("Meiryo UI");
}

@font-face {
  font-family: "MS PMincho";
  src: local("Meiryo UI");
}

などとしておいた。私は英語版Windowsなのでフォント名は「Meiryo UI」だが、日本語版の場合は「メイリオ」などとする必要があるかもしれない。Google Chromeはご丁寧にユーザスタイルシートファイルの変更のイベントを拾って、動的に既に開いているページに変更を適用してくれたけれども、Firefoxの場合は再起動が必要。設定はたいてい一度限りだし、この方がよい実装だと思う。今のところなんの不満もない。

コンテナ内の検索の速度について(2) ~setの使いどころ~

C++エクササイズその3。前回前々回の実験で、setの良さが発揮できなかったものの、何となく経験に反する結果だったので、もう一つだけ実験してみた。

具体的には、要素の中身をintからstringに変え、要素数2000から50000のコンテナに対してそれぞれ100万回検索をかけて時間を測定した。

結果

横軸がコンテナの要素数、縦軸が100万回findするのに要した時間(単位:秒)
f:id:xoinu:20140814153240p:plain

ソート済みvectorはそれでも大健闘。挿入の速さやメモリ効率を考えると使いどころは多いと思う。string程度の大きさのオブジェクトで、ある程度比較関数も複雑になってくると、メモリ上の構造のシンプルさよりもアルゴリズム的な優位性が利いてきて、setに分がでてくるということなんだろうか。

まとめ

intのような単純なオブジェクトでなければ、やはりsetの方が検索は速いが、ソート済みvectorにも挿入の速さやメモリ効率などのアドバンテージがあるので、状況に応じて両方使いこなすとよい。単に検索目的であればunordered_set一択。

コード

#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <deque>
#include <unordered_set>
#include <random>
#include <functional>
#include <algorithm>
#include <omp.h>
#include <string>

using namespace std;

static void BenchmarkFindString()
{
  default_random_engine generator;
  uniform_int_distribution<int> distribution;
  auto dice = bind(distribution, generator);

  uniform_int_distribution<int> distChar(65, 90);
  auto diceChar = bind(distChar, generator);

  uniform_int_distribution<size_t> distStrLen(16, 128);
  auto diceStrLen = bind(distStrLen, generator);

  vector<size_t> DATA_LENGTH_ARRAY(25);
  size_t next = 2000;

  for (auto& len : DATA_LENGTH_ARRAY)
  {
    len = next;
    next += 2000;
  }

  vector<string> QUERY_DATA(1000000);

  for (auto& dat : QUERY_DATA)
  {
    auto len = diceStrLen();
    dat.reserve(len + 1);

    for (size_t i = 0; i < len; ++i)
      dat += (char)diceChar();
  }

  cout << "size,vector,set,unordered_set" << endl;

  for (auto DATA_LENGTH : DATA_LENGTH_ARRAY)
  {
    vector<string> vals(DATA_LENGTH);

    for (auto& val : vals)
    {
      auto len = diceStrLen();
      val.reserve(len + 1);

      for (size_t i = 0; i < len; ++i)
        val += (char)diceChar();
    }

    cout << DATA_LENGTH;
    {
      vector<string> cont(begin(vals), end(vals));
      sort(begin(cont), end(cont));
      cont.erase(unique(begin(cont), end(cont)), end(cont));
      double dStart = omp_get_wtime();

      for (auto& val : QUERY_DATA)
        lower_bound(begin(cont), end(cont), val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      set<string> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto& val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      unordered_set<string> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto& val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }

    cout << endl;
  }
}

int main(int argc, char* argv[])
{
  BenchmarkFindString();
  return 0;
}

コンテナ内の検索の速度について

追記:この記事には続きがあります。

C++エクササイズその2。前回の実験で、要素の追加についてはvectorの性能が際立っていたので、今度は要素の検索について実験してみた。

vectorに対して要素の検索をする場合、誰もが思いつくのはに定義されているstd::findだろうと思うが、setに対して公正な比較対象になるのはstd::lower_bound()(二分岐探索)だろう。

というわけで、今回はソート済みvectorに対するstd::lower_bound()、set::find()、unordered_set::find()の比較を行ってみた。

  1. コンテナに対して100万回検索をかける
  2. コンテナサイズは20000から500000まで、20000刻み。各コンテナは同じ乱数を使って初期化(中身は一緒)

結果

f:id:xoinu:20140814121252p:plain

さすがにunordered_setは速い。しかしソート済みvectorに対する二分岐探索は、setよりも速い。あれ、set、いいとこ無いじゃん。vectorに比べて挿入は400倍遅くて、検索も2倍から3倍遅いとは。

まとめ

  1. 検索に関してはunordered_set最強。これは技術書どおりでホッとした
  2. ソート済みの要素に対して検索をかけられるならば、vectorのほうがsetよりも速い
  3. 前回の結果と組み合わせると、ソート済みvectorは挿入も検索もsetを凌ぐパフォーマンスを示している。これはハードウェア的な問題なのか、単にsetの実装がマズいのか...。

コード

実験に使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)で、コンパイラオプションも特にいじらず素のリリースモジュールで実験しました。

#include <iostream>
#include <set>
#include <vector>
#include <unordered_set>
#include <random>
#include <functional>
#include <algorithm>
#include <omp.h>

using namespace std;

static void BenchmarkFind()
{
  default_random_engine generator;
  uniform_int_distribution<int> distribution;
  auto dice = bind(distribution, generator);

  vector<size_t> DATA_LENGTH_ARRAY(25);
  size_t next = 20000;

  for (auto& len : DATA_LENGTH_ARRAY)
  {
    len = next;
    next += 20000;
  }

  vector<int> QUERY_DATA(1000000);
  for (auto& dat : QUERY_DATA)
    dat = dice();

  cout << "size,vector,set,unordered_set" << endl;

  for (auto DATA_LENGTH : DATA_LENGTH_ARRAY)
  {
    vector<int> vals(DATA_LENGTH);

    for (auto& val : vals)
      val = dice();

    cout << DATA_LENGTH;
    {
      vector<int> cont(begin(vals), end(vals));
      sort(begin(cont), end(cont));
      cont.erase(unique(begin(cont), end(cont)), end(cont));
      double dStart = omp_get_wtime();

      for (auto val : QUERY_DATA)
        lower_bound(begin(cont), end(cont), val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      set<int> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }
    {
      unordered_set<int> cont(begin(vals), end(vals));
      double dStart = omp_get_wtime();

      for (auto val : QUERY_DATA)
        cont.find(val);

      cout << ',' << (omp_get_wtime() - dStart);
    }

    cout << endl;
  }
}

int main(int argc, char* argv[])
{
  BenchmarkFind();
  return 0;
}

コンテナへの挿入の速度について

C++エクササイズ。今回は挿入の速度に的を絞って計測してみた。

やったこと

  1. ランダムな整数値を50000個生成
  2. 整数値をコンテナに挿入する
  3. 2の操作を各コンテナにつき10回繰り返す

vectorについてはさらに3つの異なる条件でも実験してみた。

  • (R) ... あらかじめ領域をreserveする
  • (RS) ... setは挿入時に値をソートし、ユニークかどうかのチェックもするので、vectorで同等の後処理をする(vector + sort + unique)
  • (RSS) ... 後処理ではなく、挿入時にユニークかどうかを二分岐探索でチェックする(よりsetに近い挙動)

結果

(単位:秒)

vector<int>     0.0305866
vector<int>(R)  0.00266554
vector<int>(RS) 0.0445996
vector<int>(RSS)        1.97772
set<int>        17.7869
unordered_set<int>      36.134
list<int>       76.8214
deque<int>      15.5323

発生する乱数のレンジを小さくして、衝突が起こりやすくすれば、setの速度はもう少し上がる。しかし、極端な例としてレンジを [0, 10] にしても、vector + sort + unique の速度にはダブルスコアで負けてしまった。vector強し。

1秒あたりの挿入数をグラフにプロットしてみた(対数グラフ)
f:id:xoinu:20140814170831p:plain

まとめ

この結果、実はCPUのキャッシュがどれくらい有効に使われているかとかのほうが利いているのかもしれない(それもまた良い発見)。STLportなどの異なるSTLの実装、異なるハードウェアでも、また違った傾向が観察できるはず。

とりあえず覚えておくと良いのは

  • 連続領域が安全に確保できるならvectorを使っておけば間違いない
  • reserveしたvector最強。なるべくreserveを呼んでおく
  • 検索を必要とせず、単にソート済みのユニークな要素のリストがほしければsetではなくvector + sort + unique の組み合わせを使う(場合によっては1万倍以上の差が出る)
  • 実は検索が必要な場合も、二分岐探索で挿入、検索するほうがパフォーマンスが出るかもしれない(これはあとで検証する)
  • list/setへの挿入のコストはvectorのpush_backとは次元が違う
  • dequeとvectorもこれだけ差が出る(似て非なる)

といったところ。雑感としては、unordered_set、dequeの結果は想像したoptimalな挙動とかけ離れていると感じる。本当にパフォーマンスが必要とされるところではSTLを信用せず、必要があれば自作するという選択肢もアリだと思った。

たまにこうやって手を動かして、速度を体感しておくのは大切ですね。

コード

使ったコードは以下の通り。開発環境はVisual Studio 2013 (msvc12)を使った。

#include <iostream>
#include <set>
#include <list>
#include <vector>
#include <deque>
#include <unordered_set>
#include <random>
#include <functional>
#include <algorithm>
#include <omp.h>

using namespace std;
int main(int argc, char* argv[])
{
  default_random_engine generator;
  uniform_int_distribution<int> distribution;
  const int LOOP_COUNT = 10;
  const size_t DATA_LENGTH = 50000;
  vector<int> vals(DATA_LENGTH);
  auto dice = bind(distribution, generator);

  for (auto& val : vals)
    val = dice();

  double dStart = omp_get_wtime();

  //-----------------------------------------------------------------
  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "vector<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;
    cont.reserve(DATA_LENGTH);

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "vector<int>(R)\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;
    cont.reserve(DATA_LENGTH);

    for (auto val : vals)
      cont.push_back(val);

    sort(begin(cont), end(cont));
    cont.erase(unique(begin(cont), end(cont)), end(cont));
  }

  cout << "vector<int>(RS)\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    vector<int> cont;
    cont.reserve(DATA_LENGTH);

    for (auto val : vals)
    {
      auto lb = lower_bound(begin(cont), end(cont), val);
      if (lb != end(cont) && *lb == val)
        continue;
      cont.insert(upper_bound(begin(cont), end(cont), val), val);
    }
  }

  cout << "vector<int>(RSS)\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    set<int> cont;

    for (auto val : vals)
      cont.insert(val);
  }

  cout << "set<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    unordered_set<int> cont;

    for (auto val : vals)
      cont.insert(val);
  }

  cout << "unordered_set<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    list<int> cont;

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "list<int>\t" << (omp_get_wtime() - dStart) << endl;

  //-----------------------------------------------------------------
  dStart = omp_get_wtime();

  for (int i = 0; i < LOOP_COUNT; ++i)
  {
    deque<int> cont;

    for (auto val : vals)
      cont.push_back(val);
  }

  cout << "deque<int>\t" << (omp_get_wtime() - dStart) << endl;

  return 0;
}

水曜日:C++関数の多重定義

かれこれC++で飯を食べさせていただいて10年くらいになるけれど、久々に血の気が弾いたあと鼻血がでるくらい酷いバグ入れてしまった。

幸い正式リリースモジュールを送信する数時間前に気付いて事無きを得たのだけど、本当に危なかった。

#include <iostream>
#include <string>

using namespace std;

void writeOption(const string& value)
{
  cout << "text: " << value << endl;
}

void writeOption(bool value)
{
  cout << "bool: " << (value ? "true" : "false") << endl;
}

int main()
{
  string s = "std::string de gonsu.";
  bool b = true;

  writeOption(s);
  writeOption(b);
  writeOption("text de gonsu");
  
  return 0;
}

最後の呼び出しがバグで、"test de gonsu" が出力されると思われがちだが、実際の結果は

text: std::string de gonsu.
bool: true
bool: true

となる。

とりあえずconst char*版を追加することで最小限の変更で修正をした。

同様の問題には ostream に対して wchar_t* の文字列を流し込んでポインタ値が出力されるバグなどがある。今のところ、この手の問題を未然に防ぐエレガントな方法が見つかっていない。

火曜日

昼はお好み焼き。夕飯はカレーと名前の知らない野菜と豚肉の炒め物。Chromecastが届いた。

夕方、普段果物を食べないK氏が苺を食べたと奥さんから連絡。めでたい。普通に考えれば大したことないことかもしれないけれども、我が家にとっては一大事であった。

M氏は高度なことをして親を驚かせるのに対して、K氏は真央ちゃん効果でいつも驚かしてくれる。