Page List

Search on the blog

2010年10月31日日曜日

知ってると便利なSTL(3) max_element, min_element

便利なSTL紹介第3弾!

今日はSTL Containers ではなくSTL algorithmsの紹介。
配列の最大値、最大解(最大値を与える要素)を出力するプログラムを普通に書いてみます。

#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
#define REP(i, n) for(int i=0; i<(int)(n); i++)

int main() {
int x[] = {1,3,5,7, 10, 0, 4, 20, 4, 6};

int mx = -1;
REP(i, SIZE(x)) {
if (mx == -1 || x[mx] < x[i])
mx = i;
}
printf("max element=%d, max value=%d\n", mx, x[mx]);

return 0;
}
これが何気に面倒臭かったりします。最大値だけならそうでもない(ループ内でmax使えばいいだけ)ですが、最大値を与えるindexを求める場合は、ちょっとだけソースコードが長くなってしまい面倒です。

そんなときは、STL Algorithmsの出番です。
これでOKです。最大値・最大解と、ついでに最小値・最小解も求めてみましょう。
int main() {
int x[] = {1,3,5,7, 10, 0, 4, 20, 4, 6};

// search max
int *mx = max_element(x, x+SIZE(x));
printf("max element=%d, max value=%d\n", mx - x, *mx);

// search min
int *mn = min_element(x, x+SIZE(x));
printf("min element=%d, min value=%d\n", mn - x, *mn);

return 0;
}
かなりシンプルですね。戻り値はiteratorですが、配列の場合はポインタとの引き算もできるみたいです。これを使えば、上の例のように最小値(最大値)を与えるindexも簡単に出ますね!

2010年10月30日土曜日

Pythonで数値計算

Pythonのいいところは、何といってもinteractiveなconsoleモードがあるところ。
ちょっとした数値計算をしたいときに重宝する。

例えば、階乗の計算をしたいとき。。
C/C++だと、64bitまでしか計算できない。。JAVAだとBigIntegerが使えるが書くのが面倒。
Pythonならコマンドラインを立ち上げて、サクサクっとかくことが出来る。
こんな感じ。

>>> def f(x):
... if x == 1:
... return 1
... else:
... return x * f(x-1)
...
>>> f(50)
30414093201713378043612608166064768844377641568960512000000000000L
>>>

さらに、Pythonには強力な数値計算モジュールが存在する。
固有値計算なんかも簡単に出来てしまう。。Page Rankの簡易バージョンを実装しようと考えていたが、Pythonだったら簡単に出来てしまう@_@
でも、固有値・固有ベクトルについてはいつか自分でも勉強しなおさないと、と思っている。。
Pythonで固有値・固有ベクトルを求めるとこんな感じ。。

>>> import numpy
>>> A = [
... [1,2,3],
... [4,5,6],
... [7,8,9]
... ]
>>> l,v = numpy.linalg.eig(A)
>>> l
array([ 1.61168440e+01, -1.11684397e+00, -1.23190993e-15])
>>> v
array([[-0.23197069, -0.78583024, 0.40824829],
[-0.52532209, -0.08675134, -0.81649658],
[-0.8186735 , 0.61232756, 0.40824829]])
>>>

楽すぎる(笑)

プログラミング言語には一長一短あるが、
個人的には、
  • 基本はC++
  • 多倍長、正規表現の文字列処理を用いる場合はJAVA
  • 数値計算、ネットワークプログラミングはPython
という感じだろうか。。

2010年10月27日水曜日

PKU150問突破~~!

PKU150問突破した。
やった~~~。わーーい^^

動的計画にだいぶ慣れてきた。それからグラフの問題が解けるようになった。DijkstraとかWarshall-Floydとか基本的なアルゴリズムを勉強した成果だろう。
あとは、Union-Findとか包除原理とかモジュロ演算とかをもっと勉強したいところ。。

アルゴリズムコンテスト用のコーディングスタイルもだいぶ染みついてきた。
  • 変数の名前はなるべく1文字にする
  • 変数はグローバル変数として宣言する
  • なるべく改行しない
  • マクロを駆使する
などなど。。

とりあえず次の目標は、200問。そしてターゲットはKyushu Univ. Topのyuta_ihcarokさん。
あとは、TopCoderの過去問やるのもありかなと思う。こっちは過去問解いても順位が付かないからモチベーションは上がらないけど。。

2010年10月19日火曜日

久々の仕事でコーディング

約1年ぶりの仕事でコーディング。

VC++を使った保守開発が始まった。ちょっとした疑問があったのでここに纏めておく。
.h と .libおよび .dllの違いについて。(以下他サイトからの引用)

A header file contains declaration of something (constants, classes, ...), usually ends with a .h or hpp extension.

A DLL (dynamically linked library) is a binary file (with .dll, .ocx, .a, ... extentions), containing functions, resources, ... and can be linked to your program at run-time. In order to use a DLL you need to include the corresponding header file, which declares things in the DLL, so that your program gets compiled. The DLL file is automatically loaded (by system) at run-time when your executable program invokes functions and asks for resources.

A library file (also called static library, with .lib extension usually) is a binary file which alsocontains functions and variables like DLL, but resolved at compile-time, meaning they need to be provided at link-time.

Dynamic and static libraries are often provided together with header file (but no source file, which contains the implementation) when the provider lets you use his/her functions/services but doesnt give you access to the implementation.

簡単にまとめると、
  • libファイルは、コンパイル時にリンクされる。実行時にexeファイル単体で実行できるけど、ファイル容量が重くなる。
  • dllファイルは、実行時に動的にリンクする。ファイル容量を小さくできるが、実行時に参照しているdllファイルを配置しなければならない。複数アプリから同様の機能を使用する場合は、dllファイルを用いるとメモリの節約ができる。
  • hファイルは、宣言のみ書いたファイル。libファイルやdllファイルを使用する場合は、使用するファイル内に含まれるクラス、関数を宣言しておかなければならない。
てな感じでしょうか。

引用元:

2010年10月16日土曜日

Pythonで美人時計の画像を自動取得

昨日に引き続きPythonを用いたネットワークプログラミング。
今日は、Pythonでweb上の画像を自動取得するコードにチャレンジ。

まずは、Pythonでネット上の画像を取得します。
ソースはこちら。


import sys
import os
import urllib2

argvs = sys.argv
img_path = argvs[1]
output = "/home/kenji/python/img/" + os.path.basename(img_path)

print "downloading from", img_path, "to", output, "......"

opener = urllib2.build_opener()
req = urllib2.Request(img_path)
req.add_header('Referer', "http://bijint.com/jp")
file = open(output, 'wb')
file.write(opener.open(req).read())
file.close()


これで画像は取得できました。
次に、上記ソースを使って複数の画像をダウンロードすることを考えてみましょう。
ここでやっかいなのは、美人時計の画像は、現時刻および1分前の画像しかアクセスできないというところ。。cronを使えばいけそうですね。。

Unixのdateコマンドで
imgpath=`date '+http://www.bijint.com/jp/img/clk/%H%M.jpg'`
とすれば、その時間の画像ファイルのパスを生成できます。

あとは、この文字をPythonに渡すシェルスクリプトを作成して、cronで毎分実行してあげれば、24*60枚の美人お姉様の画像をダウンロードすることができます。(※注意1)
Windows OSを使っている人は、cygwinのcronでもOKです。

(注意1)著作権絡みの問題があるかもしれないので実際にやるのはやめましょう。あくまでもこの情報はネットワークプログラミングの勉強のための資料としてご一読ください。

2010年10月15日金曜日

PythonでHTML解析

最近、pagerankに関する論文を読んで、ネットワーク関係のプログラミングをしたくなってきました。今日はpythonを使った簡単なhtml分析を紹介します。(本当に簡単ですいません。。)

pagerankは言わずと知れたgoogleで使われているwebページの重要度を割りあてるための手法。
論文を読むまでは、ページに重み付けて、入力リンクの重み付け和を計算してるだけだろうと、ナメてました。忘れてました。彼らはStanfordの学生だったのです。
上の計算を大規模なネットワークに適用するために、グラフ理論と行列・固有値を駆使して高速に解くという学術的なことをちゃんとやってました。。

簡易版のpagerankなら簡単に実装できそうな気がしたので(気がしただけ)、pythonを使って勉強を始めようかと思います。

とりあえず、今日やったのは、
  1. yahooのhtml ソースを取得する
  2. 自分のbloggerのページから張っているリンク先のページを列挙する
です。
以下ソース。
まず一つ目。
'''
sample 1
Get html contents and automatically decode its strings
'''
import urllib2

res = urllib2.urlopen("http://yahoo.co.jp")
charset = res.headers.getparam('charset')
html = res.read().decode(charset)
print html
urllib2というモジュールを使うと簡単にhtmlコンテンツを取得できます。あとは、文字コードを取得してそれをデコードすればOK。

次に二つ目。
'''
sample 2
Get html contents and get the link from the page
'''
import urllib2
import re

def getHrefAddress(x):
x = re.sub(r'^href="|^href=\'', '', x)
x = re.sub(r'"$|\'$', '', x)
if re.match(r'http://', x) == None or re.match(url, x):
x = None
return x

url = "http://techtipshoge.blogspot.com/"
res = urllib2.urlopen(url)
html = res.read()
links = re.findall(r'href=".+?"|href=\'.+?\'', html)
links = map(getHrefAddress, links)
links = filter(None, links)
for link in links:
print link
これは、ちょっと汚いです。BeautifulSoupというHTMLパーサライブラリがあるのでそれを使うともっとスマートに書けそうです。
上のソースでは、正規表現でリンクを取得し、自ページ(サブページ含む)へのリンクやjavascriptへのリンクは無視しています。それらしい情報を取り出すことができました。
次は、取得したリンクから再帰的にページを辿っていくようなものを作ってみたいと思います。

2010年10月10日日曜日

最短経路アルゴリズムまとめ

今日、グラフアルゴリズム勉強会をした。
第一弾は、最短経路問題を解くためのアルゴリズムについて。
以下まとめ。

 Bellman-FordDijkstra(matrix)Dijkstra(list)Warshall-Floyd
Applicable Problem単一始点最短路問題単一始点最短距離問題単一始点最短距離問題全頂点対最短経路問題
Input Data Form隣接リスト隣接行列隣接行列隣接行列
Idea・すべての距離を毎回更新・確定した接点に接続する接点の距離のみ更新・priority_queueを用いて確定接点の探索を高速化
・暫定距離の更新も実在する枝の数だけで実施
・逐次通過可能な接点集合を増加させながら解く
Calculation Amount・1回のループではE本の枝を走査
・負の閉路が含まれないければループは高々V-1回で終わる(最短パスに含まれる頂点数は最高でもV-1であるため)
・O(E * V)
・外側のループ一回につき一つの接点が確定
・ループ内部では、最小値検索、V個の距離更新を行う
・O(V^2)

・値の更新はO(E)で実施できる
・値の取り出しはO(logV)で実行でき、O(E)回程度実行される
・O(ElogV)

・通過できる接点は1つずつ増やす
・隣接行列の値を毎回すべて更新する
・O(V^3)
Feature・負の辺が含まれていても解ける
・負の閉路がある場合は更新が無限に続くため解けない。
(※無効グラフの場合は辺も閉路になるので注意)
・上記の性質を利用すれば負の閉路を検出できる

・負の辺が含まれている場合は解けない
・Bellman-Fordの無駄な計算を省略した改良バージョンと解釈できる

・負の辺が含まれている場合は解けない
・EはV^2個に比べて小さい場合が多いため、matrixバージョンの無駄を省略し高速に計算できる

・負の辺が含まれていても解ける
・実装が簡単なので計算量に余裕があれば、単一始点問題でもWarshall-Floydを利用するとよい

ダイクストラくらいしか知らなかったが、今回いろいろなアルゴリズムを知ることができて良かった。

使い分けのポイントを簡単にまとめると、
全頂点間の最小距離が必要なときは、Warshall-Floyd
単一始点で負の辺がある場合は、Bellman-Ford。(※時間に余裕があればWarshall-FloydでもOK。)
単一始点で、負の辺がなく、計算時間の制限が厳しい場合はDijkstra

この本はかなりお勧め。アルゴリズマーは是非買うべし!!コンピュータアルゴリズムのバイブルになると言っても過言ではないでしょう。

2010年10月7日木曜日

スマートグリッド、そしてスマートシティへ

恥ずかしながら、『スマートグリッド』と初めて聞いた時はグリッドコンピューティングみたいなものだと思っていた。全然違う。
スマートグリッドとは日本語に訳すと『次世代伝送網』のことで、電力の配送システムを供給・需要の両側から制御し最適化しようという試みである。経済面からも環境面からも有益なソリューションであるため、産官学が協力し研究・計画を実施している。
スマートグリッドをさらに発展させて、『スマートシティ』という概念も現れた。これは伝送網だけではなく、街そのものをスマート化しましょうというアイディアである。
簡単に言うと、“自然に優しく、無駄遣いをしないような賢い街づくりをコンピュータを使ってやってみましょう!”ということだ。具体例を挙げれば、
  • 太陽光発電を自宅に取り入れて、
  • 自動車は電気自動車に変えて、
  • 交通渋滞が起こらないように交通量を制御して、
  • 配電はもちろんスマートグリッドで、
  • 電気の使用状況は常時モニタリングして
  • ・・・
という感じ。最近IBMがテレビCMやってますよね。(参考ページ参照)
日本では、横浜(参考ページ参照)、豊田市、京都府、北九州市がスマートシティのモデル都市として選ばれました。うちの会社もがんばってるみたい!ガンバレー!!!

もともとスマートグリッド構想は、オバマ政権がグリーンニューディール政策の柱として打ち出したもの。さらに起源をたどれば、2003年のアメリカ大停電を経験して、停電を起こしにくい配電網を構築しようというのがそもそもの動機付けだったのかもしれない。それが、エコブームの波に乗り、今日の“スマート○○”ブームを作り上げたのかも。。

とりあえず、この『スマートシティ』、IT関連の会社にとってはとてつもないビジネスチャンスです。市場規模は今後30年累計で3100兆円と言われている@_@
私の会社も、スマートグリッドを『IFRS』と並ぶ今後の二大ビジネスチャンスとして捉えているようです。もちろん、IT会社の他にも自動車会社、電力・ガス会社、電気機器メーカーにとっても大きなビジネスチャンスです。今後、“スマート○○”のパワーで日本の、そして世界の景気が上向くことを期待しましょう!
あーーー、給料あがれー、あがれーー笑。

引用:
http://www.kankyo-business.jp/topix/smartgrid_01.html
http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%9E%E3%83%BC%E3%83%88%E3%82%B0%E3%83%AA%E3%83%83%E3%83%89
http://blog.goo.ne.jp/thinklive/e/05b191a8ecf7f535934185843f745355

参考ページ:
http://www-06.ibm.com/innovation/jp/smarterplanet/cities/
http://www.jftc.or.jp/shoshaeye/contribute/contrib2010_07e.pdf

2010年10月5日火曜日

ショートコーディング(1) : if文はお嫌い!?

最近、ショートコーディングの本を買った。なかなか面白い。
環境依存のテクニックだったり、コンテスト専用のチートコードの作成方法だったりと、必ずしもすべてが皆に有用かと言われるとそうではないが、学ぶべきものはたくさんある。

今日は、その中で面白いと思ったものを紹介します。
とりあえず、次のコードを見てください。

int main() {
REP(i, 10)
i % 2 && printf("%d\n", i);

REP(i, 10)
i % 3 || printf("%d サン!\n", i);

REP(i, 10)
i ? printf("%lf\n", 1.0 / i) : puts("Zero Devider");

return 0;
}
何をやっているか分かりますか?2つ目のループは3の倍数のときだけアホになってます。

ショートコーダーはif文を基本的に書かないらしいです(笑)
確かにこっちの方が短く書けますね!
以下に対応表をまとめます。

分岐文対応するショートコーディング文
if(hogehoge) dohogehoge && do
if(!hogehoge) dohogehoge || do
if(hogehoge) do1 else do2hogehoge ? do1 : do2

これで、今日からあなたもショートコーダー!!

2010年10月2日土曜日

ビット演算で遊ぼう

Hi, folks. How's it going?
I made an application that deals with some bit operations. Guess it's downright interesting.
If you're unfamiliar with bit operations, I recommend you try the application below.

どうやら、アメリカからもアクセスがあるみたいなので、ちょっとだけ英語でも書いてみました。
今日はビット演算がテーマです。

世の変態天才プログラマーたちは、ビット演算を巧みに扱います。ビット演算の魔術師と言っても過言ではありません。
私も最近ビット演算のすごさに気付きました。ビットというのは2進数なのでいろいろなことに使えます。例えばバイナリサーチの応用のようなこと(※)もビット演算で出来ます
(※ 「のようなこと」と書いたのは少なくとも私のイメージではという意味です。0か1かを常に2つに1つの可能性を選んでデータを構築していて、探索時はO(log n)で出来るという意味です。詳しくは「ビット演算を用いたべき乗計算の高速化」参照のこと。)

『ビット演算を制するものはプログラムを制する!』
『そうか、ビット演算を使えば、コードの量も1/2になり、実行速度も2倍になる。
つまり、おれがビット演算を使えば、その働きは4倍っていうことか!!!』
桜木花道もびっくり@_@

ちょっと話が脱線しましたが、下がソースです。
ビット演算初心者向けです。かなり基本ですが動きを自分で見て確認するにはいいかと。。
あと、どのような演算を施すと何が起きるのかをしっかり把握できます。一度自分で同じようなものを作ってみるといいでしょう。




void getBin(int n, char bin[]) {
    REP (i, 16)
        bin[15 - i] = (n >> i & 1) + '0';
    bin[16] = '\0';
}

int main() {
    int n, bit;
    char calc, bin[16 + 1];

    cout << "Input an integer." << endl;
    cin >> n;
    getBin(n, bin);
    printf("%s\n", bin);

    // Input one of the manipulations below:
    // q exit
    // u bit change bit-th bit to '1'
    // d bit change bit-th bit to '0'
    // x bit reverse bit-th bit
    // c reverse all bits
    // where q, u, d, x and c are characters themselves, bit is an integer and 0-based.
    while (cin >> calc) {
        switch (calc) {
        case 'q':
            cout << "Bye!" << endl;
            return 0;
        case 'u':
            cin >> bit;
            n |= 1 << bit;
            break;
        case 'd':
            cin >> bit;
            n &= ~(1 << bit);
            break;
        case 'x':
            cin >> bit;
            n ^= 1 << bit;
            break;
        case 'c':
            n = ~n;
            break;
        default:
            cerr << "Syntax Error." << endl;
            cerr << "Try again." << endl;
            continue;
        }
        getBin(n, bin);
        printf("%s\n", bin);
    }
    return 0;
}