2.28.2012

Binary Indexed Tree (BIT) in C++

C++: BITの実装

BITは、数列においてある区間の合計値を効率良く求めたい場合などに使われるデータ構造である。
計算量は、値の加算、合計値の取得ともにO(log n)。

0-indexed にて実装してみる。

//------------------------------------------------------------------------------
// Binary Indexed Tree (BIT)
//------------------------------------------------------------------------------
template <typename T>
class BinaryIndexedTree {
 public:
  BinaryIndexedTree(int size) : size_(size) {
    data_.resize(size + 1);
  }
  void Add(int index, T value) {
    if (index < 0 || index >= size_) return;
    ++index;
    while (index <= size_) {
      data_[index] += value;
      index += index & -index;
    }
  }
  T Sum(int index) {
    if (index < 0 || index >= size_) return 0;
    ++index;
    T ret = 0;
    while (index > 0) {
      ret += data_[index];
      index -= index & -index;
    }
    return ret;
  }
 private:
  std::vector<T> data_;
  int size_;
};

2.22.2012

Handling XML with VBScript

VBScript で XML を扱う

「Msxml2.DOMDocument」オブジェクトを利用すれば、VBScript で効率化に XML を扱うことができる。
詳細は後日投稿予定。

・Microsoft リファレンス
http://msdn.microsoft.com/en-us/library/windows/desktop/ms762722%28v=vs.85%29.aspx

2.06.2012

How to split a string with space in C++

C++: 文字列をスペースで分割

文字列を区切ってベクタに代入するエレガントな方法。

・コード

#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <iterator>

//------------------------------------------------------------------------------
// Split a string with space
//------------------------------------------------------------------------------
std::vector<std::string> split(std::string const& s) {
  std::istringstream iss(s);
  return std::vector<std::string>(
      std::istream_iterator<std::string>(iss),
      std::istream_iterator<std::string>());
}

int main() {
  std::vector<std::string> a = split("a dramatic turn of events");
  std::vector<std::string> b = split("1 23 456 7890");

  for (int i = 0; i < (int)a.size(); ++i) { std::cout << a[i] << std::endl; }
  for (int i = 0; i < (int)b.size(); ++i) { std::cout << b[i] << std::endl; }

  return 0;
}

・出力

a
dramatic
turn
of
events
1
23
456
7890

参考:
http://blog.goo.ne.jp/linux_ekyu/e/3a89ea531b6a0ea6997dd68238b198ce

2.04.2012

Creating Japenese holidays calendar

「国民の祝日」の判定

テーブルを使わない祝日の判定ロジック。
http://www.h3.dion.ne.jp/~sakatsu/holiday_logic.htm

世界の祝日付きカレンダー
http://www.timeanddate.com/calendar/?year=2012&country=26

「国民の祝日」について(内閣府)
http://www8.cao.go.jp/chosei/shukujitsu/gaiyou.html

日本国内の大半のシステムは祝日判定を行なっているだろうし、NTPのように
内閣府などが最も鮮度の高いデータ(csv? xml?)をインターネットで公開してもよい気がする。