8.29.2011

C++: Matrix class

C++: 2次元行列クラスの作成

とりあえず、行列の積(operator*)と累乗(pow)のみ実装。
全ての値はMの剰余としているが、適宜変更して使用する。

template <typename T>
class Matrix {
 public:
  Matrix(int row, int column, T value=T()) {
    data.resize(row, std::vector<T>(column, value));
  }
  int rows() const { return static_cast<int>(data.size()); }
  int columns() const { return static_cast<int>(data[0].size()); }

  Matrix<T> operator*(Matrix<T> const& rhs) const {
    int m = rows();
    int n = rhs.rows();
    int p = rhs.columns();
    Matrix<T> ret(m, p);
    for (int i=0; i < m; ++i) {
      for (int j=0; j < p; ++j) {
        for (int k=0; k < n; ++k) {
          ret[i][j] = (ret[i][j] + data[i][k] * rhs[k][j]) % M;
        }
      }
    }
    return ret;
  }
  std::vector<T> const& operator[](size_t n) const { return data[n]; }
  std::vector<T> & operator[](size_t n) { return data[n]; }
  std::vector<std::vector<T> > data;
 private:
  static int const M = 10007;
};

template <typename T>
Matrix<T> pow(Matrix<T> mat, long long int n) {
  int m = mat.rows();
  Matrix<T> ret(m, m);
  for (int i=0; i < m; ++i) ret[i][i] = 1;  // identity matrix
  while (n > 0) {
    if (n & 1) ret = ret * mat;
    mat = mat * mat;
    n >>= 1;
  }
  return ret;
}

8.28.2011

Lexical cast in C++ standard

C++標準での文字列<=>数値変換

boost::lexical_cast と同等の処理をC++標準で実現する。
ただしエラーは考慮しない。

・ジェネリック版

#include <sstream>

template <typename T>
T LexicalCast(char const* src) {
  std::istringstream is(src); T x; is >> x; return x;
}
template <typename T>
T LexicalCast(std::string const& src) {
  return LexicalCast<T>(src.c_str());
}
template <typename T, typename U>
T LexicalCast(U src) {
  std::ostringstream os; os << src; return os.str();
}

#define INT(a) LexicalCast<int>(a)
#define STR(a) LexicalCast<std::string>(a)

・省コード版

#include <sstream>

int INT(std::string src) { std::istringstream is(src); int x; is >> x; return x; }

template <typename T>
std::string STR(T src) { std::ostringstream os; os << src; return os.str(); }

・使用例

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
  cout << INT("01234") << endl;  // 1234
  string s = STR(56789);
  reverse(s.begin(), s.end());
  cout << s << endl;  // 98765
  cout << INT(s) + 1 << endl;  // 98766
  cout << STR(0)[0] << STR(9)[0] << endl;  // 09
  return 0;
}

8.27.2011

Developing GAE/P with Eclipse

Eclipse 上での Google App Engine/Python の開発

・セットアップはこちらを参照。
http://www.gesource.jp/weblog/?p=1704

「PyDev: Google App Engine」プロジェクトを作ることと、デバッグ設定
 モジュール:デフォルトでは「C:\Program Files\Google\google_appengine\dev_appserver.py」
 引数:「${project_loc}/src」
が必要。

・アップロードは、ツールバーの「Deploy App Engine Project」ではうまくいかず。
 「src」フォルダを右クリックし、「PyDev: Google App Engine」-「Upload」で配信できた。

Starting Google App Engine

Google App Engine の利用開始

導入手順のメモ。

1. 初期登録

・Google App Engine ホームページ
http://code.google.com/intl/ja/appengine/

・登録ページへ移動し、Google アカウントでサインイン
https://appengine.google.com/

image 「Create Application」を押下。
image 携帯電話の認証が必要となる。
国(Japan)およびキャリア(DoCoMo等)を選択し、
ユーザー名(アドレスの@より前の部分)を指定して
「Send」を押下。
image 送信に失敗すると、このような画面となる。
携帯電話側で、「google.com」からの着信を許可すること。
image 携帯電話に送られたメールに書かれているコードを入力し、
「Send」を押下。
image いよいよアプリの登録。
アプリケーションID(Application Identifier)は、ユニークなものを指定する必要がある。

以下の文字を使用し、6~30文字とすること。
 ・英小文字
 ・数字
 ・ハイフン(ただし先頭・末尾は不可)
一度決めたら変更はできない。

タイトル(Application Title)を入力し、利用同意書を許諾して
「Create Application」を押下。
image 無事に作成できたら、このような画面が表示される。

 

2. 開発ツールの入手

・Python 2.x系の入手
http://www.python.org/download/

・Google App Engine SDK の入手
http://code.google.com/intl/ja/appengine/downloads.html

image プラットフォームに応じて、
Google App Engine SDK for Python をダウンロード。
image Windows の場合。
「Next」を押下。
image チェックを付けて「Next」を押下。
image インストールパス、オプションを指定して「Next」を押下。
image 「Install」を押下。
image 「Run Launcher」を選択するとランチャが起動する。
「Finish」を押下。
image ランチャを起動するとこのような画面。
image まずは「File」-「Create New Application…」を実行。
image アプリケーション名と作業ディレクトリを指定し、
「Create」を押下。
image アプリを選択し、「Run」ボタンを押下するとローカルでWebサーバが立ち上がる。
image 「Browse」ボタンで画面の確認、「Deploy」ボタンでサーバへのアップロードができる。
image 配信(Deploy)にはGoogleアカウントの認証が必要。
アップロードの状況は別ウィンドウに表示。

ここまでの作業で、晴れてサーバ側に「Hello world!」が表示されるようになる。

・Google Plugin for Eclipse の入手
http://code.google.com/intl/ja/eclipse/

Eclipse 上でダウンロードサイトを指定すればよい。
「Help」-「Install New Software...」でサイト名に「http://dl.google.com/eclipse/plugin/バージョン」とする。
例えばHELIOSならば、http://dl.google.com/eclipse/plugin/3.6

参考:
http://techblog.ecstudio.jp/tech-tips/freewebsite-with-google-app-engine.html

8.25.2011

C++: Remove duplicates from vector

C++: 重複したvector要素の削除

以下のテンプレート関数を使えば、ソート~ユニーク~削除の一連の操作を簡単にできる。

   1: template <typename T>
   2: void UNIQ(std::vector<T> &v) {
   3:   std::sort(v.begin(), v.end());
   4:   v.erase(std::unique(v.begin(), v.end()), v.end());
   5: }

ただし、単に重複を考慮しない集合を扱うのであれば、std::set を利用したほうがいい。

参考:
http://learningcppisfun.blogspot.com/2008/04/remove-duplicates-from-vector.html

8.14.2011

TopCoder: How to setup Code Processor

TopCoder: Code Processor エディタ設定のメモ

TopCoder の Arena に CodeProcessor + TZTester + FileEdit の環境をセットアップする。

1. jarファイルのダウンロード

ここから(http://community.topcoder.com/tc?module=Static&d1=applet&d2=plugins
3種類のプラグイン「TZTester.jar」「CodeProcessor.jar」「FileEdit.jar」を入手。

以下は、Linuxマシンの /opt/TopCoder 配下にこれらのファイルを格納した想定の手順。

2. エディタの設定

Arena にログインし、「Options」-「Editor」を開く。

Screenshot-Editor Preferences 「Browser」を選択し、以下のプラグインを選択。
 ・TZTester.jar
 ・FileEdit.jar

Screenshot-Editor Preferences-1

「Add」を選択。
Screenshot-Enter Plugin Information 以下のように入力し「OK」。

Name: CodeProcessor (任意の名前でよい)
EntryPoint: codeprocessor.EntryPoint
ClassPath: CodeProcessor.jar のパス
Screenshot-Editor Preferences 「CodeProcessor」に対し必要に応じて
「Default」「At Startup」のチェックを付け、「Configure」を選択。

Screenshot-CodeProcessor Configuration

以下のように入力。

Editor EntryPoint: fileedit.EntryPoint
Processor Class: tangentz.TZTester
Screenshot-Info 「Verify」を押してこのような画面になればOK。
Screenshot-FileEdit Configuration 「Configure」を押すと、詳細設定ができる。
必要に応じて出力ファイルのパスなどを設定。
Screenshot-FileEdit Configuration-1 「Code Template」タブで言語ごとのテンプレートを記述できる。
$BEGINCUT$ ~ $ENDCUT$
の間に記述されたコードは、TopCoderでコンパイルしたときに削除される。

各画面で「Save」して終了。

あとは問題を開けば、指定したパスにファイルが自動的に作成される。

参考:
http://gulfweed.starlancer.org/d/index.php?itemid=10

Restoring name resolution in Ubuntu

Ubuntu: 名前解決設定の復旧

Ubuntu で急にDNS(名前解決)ができなくなっていた。
急にと言っても、無線接続とか色々やっていたためだろうが……

/etc/resolv.conf を正しい状態にして復旧。

search local
nameserver xxx.xxx.xxx.xxx

Taking a window screenshot in Ubuntu 10.10

Ubuntu 10.10: ウィンドウサイズのスクリーンショットの取得

Ubuntu 10.10 で Alt + PrintScreen が機能しないというバグがある。

キーボードショートカットの設定で「Ctrl + PrintSreen」など別のキーバインドを割り当てるか、
以下のコマンドを実行すればよい。

$ sudo sysctl -w kernel.sysrq=0

参考:
http://www.virtualhelp.me/linux/212-altprint-screen-not-working-ubuntu-1010
http://ugoisgood.blogspot.com/2010/10/066-ubuntu-1010-altprintscreen.html

8.11.2011

Encode a binary file in UNIX

UNIX: バイナリファイルのエンコードコマンド

UNIX標準コマンド「uuencode」「uudecode」を使えば、
バイナリファイルをASCII文字列に変換(エンコード)したり、元に戻すことが可能である。

・基本的な使い方

$ uuencode /bin/pydoc pydoc
begin 755 pydoc
M(R$O=7-R+V)I;B]P>71H;VX*"FEM<&]R="!P>61O8PII9B!?7VYA;65?7R ]
>/2 G7U]M86EN7U\G.@H@(" @<'ED;V,N8VQI*"D*
 
end
$ uuencode pydoc < /bin/pydoc
begin 755 pydoc
M(R$O=7-R+V)I;B]P>71H;VX*"FEM<&]R="!P>61O8PII9B!?7VYA;65?7R ]
>/2 G7U]M86EN7U\G.@H@(" @<'ED;V,N8VQI*"D*
 
end

復元の時のために、実際のデータとは別に「ファイル名」を指定しないといけない。

・「-m」をつけると、Base64変換ができる

$ uuencode -m /bin/pydoc pydoc
begin-base64 755 pydoc
IyEvdXNyL2Jpbi9weXRob24KCmltcG9ydCBweWRvYwppZiBfX25hbWVfXyA9PSAnX19t
YWluX18nOgogICAgcHlkb2MuY2xpKCkK
====

・通常はエンコード結果をファイルに書き出して使う

$ date > date.txt
$ uuencode ./date.txt date.txt > ./date.enc
$ cat ./date.enc
begin 644 date.txt
L,C Q,>6YM# XYIR(,3'FEZ4@*.:<J"D@,C+FF8(T,.6(AC XYZ>2($I35 H
 
end
$ rm -i ./date.txt
rm: remove regular file `./date.txt'? y
$ uudecode ./date.enc
$ cat ./date.txt
2011年08月11日 (木) 22時40分08秒 JST

日付を出力した「date.txt」をエンコード。元ファイルを消してデコード。正しく復元できたことがわかる。

・圧縮してからエンコードすると、サイズを節約できる

$ gzip -c ./date.txt | uuencode date.txt > ./date.enc

参考:
http://x68000.q-e-d.net/~68user/unix/pickup?uuencode

8.07.2011

TopCoder constraints

TopCoder の実行環境制限

C++の場合の制限など。(2011/8/7時点)

実行時間  : 各テストケースにつき 2秒以内
メモリ使用量: 64MB (スタック領域は8MB以下)
その他    : 一時ファイルは使用できない

CPU          : 2.3 GHz Intel Xeon E5345 × 6~8基
OS           : Linux 2.6.9-55.0.12.ELsmp (RedHat EL 4)
コンパイラ      : gcc 4.0.2, glibc-2.3.2, and libstdc++-3
コンパイラオプション: g++ -Wall -W -O2 -s –pipe
型のサイズ: 
 char - 8 bits (signed)
 short - 16 bits
 int - 32 bits
 long - 32 bits
 long long - 64 bits

参考:
http://www.itmedia.co.jp/enterprise/articles/0908/22/news001.html
http://apps.topcoder.com/wiki/display/tc/General+SRM+Algorithm+FAQ

8.06.2011

Command line length limit in Solaris

Solaris: コマンドラインの長さ制限に関する調査

シェル上のコマンドラインから外部コマンドを実行する場合、そのパラメータが長すぎるとエラーとなってしまう。
大量のファイルがヒットするような場所でワイルドカードを使う場合と再現できるだろう。

$ rm -f ./*
-bash: /usr/gnu/bin/rm: Arg list too long

回避するには「xargs」を使えばいいのだが、実際のところ制限値はどれほどなのか。
それは「getconf ARG_MAX」コマンドで確認できる。

$ getconf ARG_MAX
1048320

bash などのシェルでは、ワイルドカードや変数を展開し
その後で子プロセス生成のためにシステムコール execve(2) を呼び出す。

この展開後のパラメータが制限値よりも長いと execve(2) がエラーとなる。これが「Arg list too long」である。

尚、パラメータには「env」コマンドで表示される環境変数も含まれているので注意。
従って実際の制限値は「getconf ARG_MAX」の結果から「env |wc -c」の結果を減算したものとなる。

以下のようなコマンドで検証してみる。

$ s=x; for i in {1..19}; do s=$s$s; /bin/echo $s; done > /dev/null
$ s=x; for i in {1..20}; do s=$s$s; /bin/echo $s; done > /dev/null
-bash: /bin/echo: Arg list too long

最初に変数「s」に「x」(適当な文字1文字)を代入。
for ループでその変数の長さを2倍にしていくと、n回目のループで変数sは2のn乗の長さに展開される。
そのパラメータを外部コマンドの echo に渡している。

文字列の長さが 2**19=524,288 文字までは問題なく、2**20=1,048,576 文字ではエラーが発生している
ことが分かる。

ちなみに、bash 組み込みコマンド(内部コマンド)の「echo」ではシステムコールが発生しないので
エラーは発生しない。

$ s=x; for i in {1..20}; do s=$s$s; echo $s; done > /dev/null

ループ回数を増やしていくとメモリを使い果たし、やがてメモリアロケーションエラーとなってしまった。
(これは ksh で実行)

$ s=x; for i in {1..100}; do s=$1 s$s; echo $s; done > /dev/null
-ksh: storage allocator out of space on 402653184 byte request ( region 545947648 segments 2 busy 315:358065680:223719752 free 2:187879352:187879336 ) [Resource temporarily unavailable]
-ksh: warning: vmbusy() inside job_reap() -- should not happen
-ksh: warning: vmbusy() inside job_reap() -- should not happen
-ksh: warning: vmbusy() inside job_reap() -- should not happen
-ksh: warning: vmbusy() inside job_reap() -- should not happen
^C-ksh: cannot fork [Interrupted system call]

参考:
http://www.cyberciti.biz/faq/argument-list-too-long-error-solution/

8.05.2011

Python: Get Google trends queries ver.2

Python: Google トレンドの取得 バージョン2

文字コード変換に関して改良を行ったバージョン。

・GetGoogleTrends.py

# Copyright (c) 2011 Mog Project. All rights reserved.
# -*- coding: utf-8 -*-
"""Get queries of Google trends."""
 
import re
import urllib2
 
URL = 'http://www.google.co.jp/m/services/trends/get'
PTN_QUERY = '<query>(.*)</query>'
 
def main():
  rank = 1
  for line in urllib2.build_opener().open(URL).readlines():
    x = re.findall(PTN_QUERY, line.decode('utf-8'), re.I)
    if x:
      print '%2d: %s' % (rank, unicode(x[0]))
      rank += 1
 
if __name__ == '__main__':
  main()