2009年9月15日火曜日

C++: STL algorithmのlower_boundとupper_boundの使い方

このブログ記事をはてなブックマークに追加

C++ STLのalgorithmに入っているlower_boundとupper_boundが間違えやすいのでメモ。

vector<int>で定義されたコンテナvの要素のうち、A以上、B以下の要素を求める場合。

vector<int>::iterator a = lower_bound(v.begin(), v.end(), A); vector<int>::iterator b = upper_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "[" << *a << ", " << *(b - 1) << "]" << endl; else cout << "no element" << endl;

*aが最小の要素、*(b-1)が最大の要素になる。

A以上、B未満の場合。

vector<int>::iterator a = lower_bound(v.begin(), v.end(), A); vector<int>::iterator b = lower_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "[" << *a << ", " << *(b - 1) << "]" << endl; else cout << "no element" << endl;

因みに、lower_boundとupper_boundに渡すコンテナはソートされている必要がある。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { vector<int> v; for (int i = 100; i > 0; i--) v.push_back(i); int A = 30; // 下限. int B = 50; // 上限. vector<int>::iterator a, b; cout << "要素数" << v.size() << "で、"; cout << "最小要素" << *min_element(v.begin(), v.end()) << "、"; cout << "最大要素" << *max_element(v.begin(), v.end()); cout << "のコンテナから、" << endl; // lower_bound, upper_boundに渡すコンテナはソートされている必要がある. sort(v.begin(), v.end()); cout << A << "以上、" << B << "以下の要素を求める: "; a = lower_bound(v.begin(), v.end(), A); b = upper_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "最小要素 " << *a << ", 最大要素 " << *(b - 1) << endl; else cout << "要素なし" << endl; cout << A << "以上、" << B << "未満の要素を求める: "; a = lower_bound(v.begin(), v.end(), A); b = lower_bound(v.begin(), v.end(), B); if (a != v.end() && b != v.begin() && *a <= *(b - 1)) cout << "最小要素 " << *a << ", 最大要素 " << *(b - 1) << endl; else cout << "要素なし" << endl; return 0; }

出力結果:

要素数100で、最小要素1、最大要素100のコンテナから、 30以上、50以下の要素を求める: 最小要素 30, 最大要素 50 30以上、50未満の要素を求める: 最小要素 30, 最大要素 49

続きを読む...

2009年9月8日火曜日

JavaScriptで素数を計算して動的に表示する

このブログ記事をはてなブックマークに追加

JavaScriptを使って素数を計算して、それを動的に表示してみた。今更という感じもするけど、10行そこそこでこのような動的な表示ができるというのは、とても便利だと思う。とは言え、普段はあまりJavaScriptを使ったHTMLは書いてないな。

までの素数


テキストボックスに数字を入力すると、その数までの素数を計算して表示する。最大入力桁を5桁にしたので、99,999までの素数を求めることができる。括弧内の数値は求めた素数の数を示す。

複数のブラウザ(Google Chrome, Firefox, IE8, Safari4)で確認してみたけど、最近はどのブラウザもJavaScriptが速い。今後、ますますJavaScript、特にAjaxなどは要の技術になっていくのだろうな。

以下にソースを示す。

<script type="text/javascript"><!-- function calcPrimes(data) { var primes = []; if (data.value >= 2) primes.push(2); for (i = 3; i <= data.value; i += 2) { for (j = 0; i > primes[j] * primes[j] && i % primes[j] != 0; j++); if (i < primes[j] * primes[j]) primes.push(i); } document.getElementById("primes").innerHTML = primes.length ? " (" + primes.length + "): " + primes.join(", ") : ""; } // --></script> <form><input type="text" size="5" maxlength="5" onkeyup="calcPrimes(this)">までの素数<span id="primes"></span></form>

続きを読む...

2009年9月1日火曜日

結局Pythonを使ってコマンドラインで動作するTwitterクライアントを作ってしまった

このブログ記事をはてなブックマークに追加

Twitterのアカウントを取ってから既に1年半になるが、活発に使っているとは言い難い。その原因の一つとしてTwitterのクライアントがある。どうにも自分が利用するのにピッタリだと思うクライアントが見つからなかったのだ。そこで結局、自分の好みに合わせてコマンドライン上で動作するシンプルなTwitterクライアントをPythonで作ってしまった。しかも、ワンライナー(1行プログラム)。

最初の頃はいくつかのクライアントを使ってみたのだが、PCでの作業はシェルで行うことが多いので別のウィンドウを開きたくなかったり、Windows、Unix、MacなどのOSが変わっても同じクライアントを使いたかったり、GUIじゃなくてCUIで操作したかったり、それほど使い込むつもりがないので極力シンプルでコンパクトになっていて欲しかったり、そもそもクライアントをインストールしたくなかったりと、かなり条件を厳しく求めていたら使えるクライアントがなくなってしまい、結局、公式サイトもしくは自分で作成した掲示板からたまにつぶやくだけになってしまった(ただし、Twitterfeedは利用している)。

しかし、最近になってタイムラインをよく眺めるようになり、これが結構面白いと気がついた。自分と違う考え方に触れるのは楽しい。そして、自分ももう少しつぶやいてみようかと思ったのだが、公式サイトや掲示板からのポストはいちいちブラウザを開かなくてはならず手軽だとは言い難かった。

そこで、先日、PythonのワンライナーでTwitterを使えるようにしたこともあり、もう少し改良してそれをクライアントにすることにした。Pythonスクリプトなら、Pythonが入っていればどのOSでも動作するし、使い方はどこでも一緒で、コマンドラインでそのまま使え、タイムラインをgrepなどで簡単に選択表示できる。それに、たった1行のソースコードなので簡単に中身を確認でき、パスワード漏洩やキーロガーなどを心配しなくてもいい。

tw.py

でタイムラインを取得することができ、

tw.py つぶやき tw.py つぶやき http://handasse.blogspot.com/ ブログのURLです。 tw.py "つぶやき&つぶやき" tw.py "つぶやき つぶやき"

などでTwitterにつぶやくことができる。つぶやきに&などの特殊文字や連続でスペースが入る場合などはダブルクォーテーション(")で括ること。つぶやきに入っているURLは自動的にbit.lyによる短縮URLとなる。

また、Windows PowerShellで使用する場合は、プロファイル($profileで表示されるファイルで、Microsoft.PowerShell_profile.ps1などを指し、PowerShell起動時に読み込まれる)に以下の関数を定義しておくと便利だ。

function tw { python 実行パス\tw.py "$args" }

Unixなどで日本語コードが異なっていても、ソースを変更せずにnkfなどを使ったエイリアスで簡単に対処できる。ただ、特殊文字などを使ったときに問題が出るかもしれない。以下の例は、Unix側の表示がUTF-8でシェルがtcshの場合。

alias tw 'tw.py `echo -n \!* | nkf -s` | nkf -w'

これならば tw とするだけで実行できる。また、PowerShellでは tw | select-string フレンド名、Unixでは tw | grep フレンド名で、指定したフレンドの発言をタイムラインから簡単に抜き出すこともできる。

今回のPythonによるTwitterクライアントのソースを以下に示す。simplejsonを使っている。bit.lyのアカウント名とAPI Keyはbit.lyアカウントのページですぐに取得できる。また、Base64でエンコードされたユーザ名とパスワードの作成は、Pythonのbase64モジュールを使ってもいいし、以前にGoogle App Engineで作ったバイナリ/アスキー変換を利用してもらっても構わない。まあ、エンコードされていてもセキュリティが強固になるわけではないのだが、ぱっと見でばれてしまう平文よりはいいんじゃないかな。ワンライナーにしたのもぱっと見で解りづらくするためだし。

ところで、TwitterのAPIでデータを取得したり送信したりすると、たまに失敗することがあるので、エラーが出たときは再度実行すること。

tw.py

#!/usr/bin/env python import sys,re,urllib,urllib2,xml.sax.saxutils,base64,simplejson;pm=urllib2.HTTPPasswordMgrWithDefaultRealm();pm.add_password(None,'twitter.com',base64.b64decode('エンコードされたユーザ名'),base64.b64decode('エンコードされたパスワード'));urllib2.install_opener(urllib2.build_opener(urllib2.HTTPBasicAuthHandler(pm)));tw=None;len(sys.argv)>1and[globals().__setitem__('tw',' '.join(sys.argv[1:]))];F=lambda x:str(simplejson.loads(urllib2.urlopen('http://api.bit.ly/shorten?version=2.0.1&longUrl=%s&login=bit.lyのアカウント名&apiKey=bit.lyのAPI Key'%urllib.quote(x)).read())['results'][x]['shortUrl']);G=lambda x:re.sub(re.escape(x),F(x),tw);tw and[globals().__setitem__('tw',G(link))for link in sorted(re.findall(r'(http(?:s?)\:\/\/[^\/\ ]+\/.*?)(?:[\ <>\"\{\}\|\\\^\[\]\`]|$)',tw),reverse=True)];tw and[urllib2.urlopen('http://twitter.com/statuses/update.xml',urllib.urlencode({'status':tw.decode('cp932').encode('utf-8')}))]or[sys.stdout.write(''.join(['%s: %s\n'%(d['user']['screen_name'],re.sub(r'\r\n|\n|\r',' ',xml.sax.saxutils.unescape(d['text'])))for d in simplejson.loads(urllib2.urlopen('http://twitter.com/statuses/friends_timeline.json').read())]).encode('cp932','replace'))]

追記(2009/9/9):

今までTwitterのお気に入り機能を使っていなかったけど、ふぁぼったーを見て使いたくなったので、今回のコマンドライン型Twitterクライアントでも使えるように改良した。

まず、tw.pyについてはつぶやきの最後に[つぶやきのID]を表示するようにした。また、fav.pyでつぶやきをお気に入りに加えることができる。使い方は以下の通り。

fav.py [つぶやきのID]

tw.pyで表示されたIDを入力する。コピー&ペーストだと簡単。IDの括弧([])は入れても入れなくても構わない。また、IDを付けずに

fav.py

とすれば、自分のお気に入りを表示することができる。

ただ、お気に入りを使わないのであればtw.pyによるIDの表示は目障りになるかもしれないので、そのときは以前のtw.pyを使った方がいいと思う。

以下、修正したソース。

tw.py

#!/usr/bin/env python import sys,re,urllib,urllib2,xml.sax.saxutils,base64,simplejson;pm=urllib2.HTTPPasswordMgrWithDefaultRealm();pm.add_password(None,'twitter.com',base64.b64decode('エンコードされたユーザ名'),base64.b64decode('エンコードされたパスワード'));urllib2.install_opener(urllib2.build_opener(urllib2.HTTPBasicAuthHandler(pm)));tw=None;len(sys.argv)>1and[globals().__setitem__('tw',' '.join(sys.argv[1:]))];F=lambda x:str(simplejson.loads(urllib2.urlopen('http://api.bit.ly/shorten?version=2.0.1&longUrl=%s&login=bit.lyのアカウント名&apiKey=bit.lyのAPI Key'%urllib.quote(x)).read())['results'][x]['shortUrl']);G=lambda x:re.sub(re.escape(x),F(x),tw);tw and[globals().__setitem__('tw',G(link))for link in sorted(re.findall(r'(http(?:s?)\:\/\/[^\/\ ]+\/.*?)(?:[\ <>\"\{\}\|\\\^\[\]\`]|$)',tw),reverse=True)];tw and[urllib2.urlopen('http://twitter.com/statuses/update.xml',urllib.urlencode({'status':tw.decode('cp932').encode('utf-8')}))]or[sys.stdout.write(''.join(['%s: %s [%d]\n'%(d['user']['screen_name'],re.sub(r'\r\n|\n|\r',' ',xml.sax.saxutils.unescape(d['text'])),d['id'])for d in simplejson.loads(urllib2.urlopen('http://twitter.com/statuses/friends_timeline.json').read())]).encode('cp932','replace'))]

fav.py

#!/usr/bin/env python import sys,re,urllib,urllib2,xml.sax.saxutils,base64,simplejson;pm=urllib2.HTTPPasswordMgrWithDefaultRealm();pm.add_password(None,'twitter.com',base64.b64decode('エンコードされたユーザ名'),base64.b64decode('エンコードされたパスワード'));urllib2.install_opener(urllib2.build_opener(urllib2.HTTPBasicAuthHandler(pm)));len(sys.argv)>1and[urllib2.urlopen('http://twitter.com/favorites/create/%d.xml'%int(sys.argv[1].strip('[]')),{})]or[sys.stdout.write(''.join(['%s: %s [%d]\n'%(d['user']['screen_name'],re.sub(r'\r\n|\n|\r',' ',xml.sax.saxutils.unescape(d['text'])),d['id'])for d in simplejson.loads(urllib2.urlopen('http://twitter.com/favorites.json').read())]).encode('cp932','replace'))]

続きを読む...