mog project

3.04.2012

Binary search with predicate in Python

Python: predicate の二分検索

predicate P がある値を境に真偽が分かれる場合、その境界を調べるのに二分検索を行うことができる。

整数 x について、P(x) が true となる最小のx（上の図ではa）を検索する処理のPythonによる実装例を以下に示す。

def binary_search(predicate, lower_bound, upper_bound, not_found=0):
  """
  Returns the least x for which predicate P(x) is true.
  
  Predicate P must be assumed:
    for all x in ordered set S, P(x) implies P(y) for all y > x
  
  @param predicate: unary function which returns true or false
  @param lower_bound: lower bound on the search
  @param upper_bound: upper bound on the search
  @param not_found: return value when all the predicates are false
  """
  ret = not_found

  while lower_bound < upper_bound:
    mid = lower_bound + (upper_bound - lower_bound) / 2
    if predicate(mid):
      ret = upper_bound = mid
    else:
      lower_bound = mid + 1

  return ret

参考：
http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch

3.01.2012

How to get a line count of a file in Windows

WIndows で行数のカウント
UNIXの「wc -l」コマンドと同様の処理は、以下のDOSコマンドで実現できる。

find /c /v "" filename

※ファイルの末尾が改行文字である場合、最後の空行はカウントされない。
　つまり、UNIXの「wc -l」コマンドの結果よりも1少なくなる。
もちろん、VBScriptで実現することも可能。
参考：
http://scripting.cocolog-nifty.com/blog/2008/06/post_2998.html

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.13.2012

Determinant of a square matrix in C++

C++: 行列式の計算

メモ。

http://paulbourke.net/miscellaneous/determinant/
http://thira.plavox.info/blog/2008/06/_c.html
http://www.softwareandfinance.com/CPP/Matrix_Determinant.html
http://cboard.cprogramming.com/cplusplus-programming/30001-determinant-calculation.html

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

・出力