12.31.2013

Getting Started with Erlang pt.2

Erlang をはじめよう その2

 

前回 - mog project: Getting Started with Erlang pt.1 の続き

CHAPTER 3: Atoms, Tuples, and Pattern Matching

 

アトム

アトムを利用したパターンマッチ、ブール値を示す特別なアトム

> hello.
> F = (fun(apple, Num) -> 100 * Num; (banana, Num) -> 200 * Num end).
> F(apple, 2).
> F(banana, 3).
> F(candy, 4).    % error
> 3<2.
> 3>2.
> 10 == 10.
> true and true.
> true or false.
> false xor false.
> not false.
ガード

when句、アンダースコアの利用

> Abs = (fun (Num) when Num =< 0 -> -Num; (Num) when Num > 0 -> Num end).
> Abs(-10).
> Abs(0).
> Abs(3).
> Abs = (fun (Num) when Num  -Num; (Num) when Num >= 0 -> Num end).  % error
> Abs2 = (fun
> (Num) when Num < 0 -> -Num;
> (0) -> 0;
> (Num) -> Num
> end).
> Abs2(-5).
> _.
> _ = 20.
> _.
> F = (fun(apple, Num) -> 100 * Num; (_, Num) -> 500 * Num end).
> F(apple, 3).
> F(candy, 10).
> G = (fun(apple, Num) -> 100 * Num; (_, _) -> 1 end).
> G(hello, world).
タプル

タプルの操作、パターンマッチでの利用

> {atom, 123, "string"}.
> T = {atom, 123, "string"}.
> element(2, T).
> setelement(2, T, 456).
> tuple_size(T).
> {A, B, C} = T.
> A.
> B.
> C.
> F = (fun ({apple, Num}) -> 100 * Num; ({banana, Num}) -> 200 * Num end).
> F({apple, 3}).

タプルを使った実装の隠蔽 (カプセル化)

-module(shop).
-export([buy/1]).

buy({Item, Num}) -> buy(Item, Num).

buy(apple, Num)  when Num >= 0 -> 100 * Num;
buy(banana, Num) when Num >= 0 -> 200 * Num;
buy(_, Num)      when Num >= 0 -> 500 * Num;
buy(_, _)                      -> 0.
> c(shop).
> shop:buy({apple, 3}).
> shop:buy({banana, 2}).
> shop:buy({candy, 1}).
> shop:buy({apple, -1}).
> shop:buy(apple, 3).    % error

CHAPTER 4: Logic and Recursion

 

case 構成要素 (case construct)

case は値を返す。case 内部でガードを行うことも可能。

> F = fun (Item, Num) ->
>   case Item of
>     apple -> 100 * Num;
>     banana -> 200 * Num
>   end
> end.
> F(apple, 3).
> G = fun (Item, Num) ->
>   X = case Item of
>     apple -> 100;
>     banana when Num >= 5 -> 198;
>     banana -> 200
>   end,
>   X * Num
> end.
> G(banana, 3).
> G(banana, 10).
if 構成要素 (if construct)
> F = fun (Item, Num) ->
> X = 100.
> if X >= 99 -> 'good' end.
> if X =< 99 -> 'good' end.
> F = fun(X) ->
>   if
>     X =< 99 -> io:format("X is less than ~w.~n", [100]);
>     true -> true
>   end
> end.
> F(10).
> F(100).
> A = 10.
> B = if A == 5 -> 100; true -> 20 end.
> B.
> BadFun = fun (X) ->
>   if
>     X < 0 -> Y = 1;
>     X >= 0 -> Z = 2
>   end,
>   Y + Z
> end.
再帰

カウントダウン

-module(count).
-export([countdown/1]).

countdown(From) when From > 0 ->
  io:format("~w!~n", [From]),
  countdown(From - 1);

countdown(From) ->
  io:format("blastoff!~n").
> c(count).
> count:countdown(10).

階乗

-module(fact).
-export([factorial/1]).

factorial(N) when N =< 1 -> 1;
factorial(N) -> N * factorial(N - 1).
> c(fact).
> fact:factorial(10).

階乗 (アキュムレーター付き)

-module(fact).
-export([factorial/1]).

factorial(N) -> factorial(1, N, 1).

factorial(Current, N, Result) when Current =< N ->
  factorial(Current + 1, N, Result * Current);
factorial(Current, N, Result) -> Result.
> c(fact).
> fact:factorial(10).

 

 

 

References

 

Related Posts

12.30.2013

Machine Learning: Logistic Regression vs SVMs

機械学習: ロジスティック回帰 vs サポートベクターマシン

Stanford大学の Andrew Ng 先生の Coursera での講義。
だいぶ遅れをとってしまったが、Week 7: Support Vector Machines を復習している。

 

ライブラリを使おう

世の中には、

といった優れたライブラリが既に存在するので、数値計算を自分で実装するのは避けよう。

 

アルゴリズムの選択

素性の数 (n) と学習データの数 (m) によって最適なアルゴリズムは変わってくる。

 

(mと比較して) n が大きい場合 [例: n  >= m, n = 10000, m = 10 .. 1000]

ロジスティック回帰、またはカーネルトリックなしの線形SVM

理由: 学習データが少ない状態で複雑なアルゴリズムを使うと過学習(overfit)が起こり、汎用性がなくなってしまうため。

n が小さく、m が中くらいの場合 [例: n = 1 .. 1000, m = 10 .. 10000]

ガウスカーネルを使ったSVM (非線形SVM)

n が小さく、m が大きい場合 [例: n = 1 .. 1000, m >= 50000)

新しい素性を付け加えた上で、ロジスティック回帰、またはカーネルトリックなしの線形SVM を使う

理由: 巨大な m に対して非線形SVMを行うと計算量が非常に多くなるので、コンピューティングリソースが不足するおそれがある。

 

その他、ニューラルネットワークはいずれの状況にも適用可能だが、学習処理の速度は遅くなる可能性が高い。

また、線形SVM、ガウスカーネル以外のSVMカーネルとして、以下のものが挙げられていた。

  • 多項式カーネル
  • 文字列カーネル
  • カイ二乗カーネル
  • ヒストグラムインターセクションカーネル

12.25.2013

Getting Started with Erlang pt.1

Erlang をはじめよう その1

 

本ブログ初のErlangエントリ。

Introducing Erlang - O'Reilly Media を読みながら、実行したコマンドを自身の復習のために書き連ねていく。

どのような結果になるか、考えながら手を動かしていくスタイル。
尚、以下に記載している内容は、書籍のサンプルコードとは異なります。

  • 凡例
    $     ===> OS のシェルプロンプト
    >     ===> Erlang Shell で実行
    %     ===> インラインコメント
    

CHAPTER 1: Getting Comfortable

Erlang Shell での基本的な操作。

起動と終了

erl コマンドを実行し、Erlang Shell を起動する。 (Windows の場合は werl コマンド)

$ erl
>     % Ctrl+G を押下
User switch command
 --> ?
 --> q
>     % Ctrl+C を押下
BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution
a
> q().
> init:stop().
ディレクトリとヒストリの操作

Erlang Shell 組み込みコマンド。

1> help().
2> pwd().
3> ls().
4> h().
5> v(2).
6> results(3).
7> h().
8> v(2).    % エラー
8> v(-1).
9> e(2).
10> history(3).
11> h().
12> e(2).    % エラー
12> e(-1).
13> cd(..).    % エラー
13> cd("..").
14> cd("/tmp").
15> pwd().
数値の操作

どの処理でエラーが発生するか?

> 1+2.
> 10 - 100.
> 1+3.0.
> 100 * 10.
> 10.0 * 0.
> 100/33.
> 100 div 33.
> 100 rem 33.
> 100/0.
> -100.0/0.0.
> 0.0/0.0.
> 100 div -33.
> -100 div 33.
> 100 rem -33.
> -100 rem 33.
> -100 rem -33.
> 5 - 4 * (3 + 2).
> round(100/22).
> math:sin(math:pi()/2).
> math:sin(math:pi()).
> math:cos(0).
> math:pow(2, 10).
> math:pow(10, 333).
> 2#1111.
> -16#f0f0.
> 16#fffffffffffffffff.
> 36#a3Z.
> bnot 10.
> bnot -1.
> 5 band 15.
> -1 band -2.
> 5 bor 11.
> 5 bxor 11.
> 11 bsl 2.
> 11 bsr 2.
> 1 bsr 10.
> -1 bsr 10.
> 1 bsl 1000.
変数の操作

どの操作でエラーが発生するか?

> n=10.
> N=10.
> N=11.
> 10=N.
> 11=N.
> 25 = N * 2 + N div 2.
> N * 2 + N div 2 = 25.
> M=N+1.
> M=N+1.
> N+1=M.
> 11=M.
> M=11.
> b().
> f(M).
> b().
> M=N*3.
> N=11.
> f().
> N=M.
> N=11.

 

CHAPTER 2: Functions and Modules

引き続き Erlang Shell で実行。

関数の定義

今日はクリスマス。というわけで、ケーキの代金を求める Price 関数を作る。
ドル払い(端数は四捨五入)もできるようにしますよ。

> Price = fun(Num) -> trunc(348 * Num * 1.05) end.
> Yen_to_dollar = fun(Yen) -> round(Yen / 104.288) end.
> b().
> Price(3).
> Yen_to_dollar(Price(4)).
> Num.
> Yen.
> Price1 = Fun(Num) -> trunc(348 * Num * 1.05) end.
> price2 = fun(Num) -> trunc(348 * Num * 1.05) end.
> Price3 = fun(num) -> trunc(348 * num * 1.05) end.
> Price3(10).
モジュールの定義

ファイル(仮に prices.erl とする)に以下の内容を保存。

-module(prices).
-export([price/1, yen_to_dollar/1]).

price(Num) -> trunc(348 * Num * 1.05).
yen_to_dollar(Yen) -> round(Yen / 104.288).

Erlang Shell から、そのモジュールを利用できる。

> ls().
> prices:price(3).
> c(prices).
> ls().    % どのような拡張子のファイルが生成されるか?
> prices:price(3).
> prices:yen_to_dollar(10000).
ドキュメント(EDoc)の生成

ファイル(prices.erl)の内容を更新。

%% @author mogproject [http://mogproject.blogspot.com]
%% @doc Functions calculating price of cakes.
%% @reference REFERENCE HERE
%% @copyright 2013 by mogproject
%% @version 0.1

-module(prices).
-export([price/1, yen_to_dollar/1]).

%% @doc Calculates price of cakes.
%% You should specify how many cakes you want.

-spec(price(integer()) -> integer()).

price(Num) -> trunc(348 * Num * 1.05).

%% @doc Exchange yen to dollar.

-spec(yen_to_dollar(integer()) -> integer()).

yen_to_dollar(Yen) -> round(Yen / 104.288).

Erlang Shell で以下のコマンドを実行。

> edoc:files(["prices.erl"], [{dir, "doc"}]).

doc サブディレクトリ配下に各種HTMLファイルが作られるので、その内容をブラウザで確認しよう。

Screenshot 12 25 13 03 16

12.24.2013

Monitoring JMX in Zabbix

Zabbix: JMX監視について

 

バージョンによって手順に違いがあったり、公式ドキュメントでも日本語化されていない部分があったりしたので
導入のポイントをメモしておく。 

 

環境

監視サーバ
  • zabbix-server 2.2
  • Zabbix Java Gateway (後述) を同居

 

監視対象サーバ
  • RedHat Enterprise Linux または Cent OS (もちろんこれ以外でも動作する)
  • zabbix-agent
  • 適当な JVM アプリケーション
    • 適当な JMX ポートを決定し、監視サーバから接続可能にすること

 

監視対象サーバの設定

 

JMX ポートの起動

JVM の標準機能である JMX を有効にする。
起動スクリプトなどで JAVA_OPTION を指定すればよい。

設定例 (セキュリティ関連の項目は必要に応じて書き換えること)

-Dcom.sun.management.jmxremote
-Dcom.sun.management.jmxremote.port=12345
-Dcom.sun.management.jmxremote.ssl=false
-Dcom.sun.management.jmxremote.authenticate=false

 

疎通確認

監視サーバからの疎通確認には、cmdline-jmxclient を使うと便利だった。

実行例 (適当なディレクトリ配下で)

curl -O http://crawler.archive.org/cmdline-jmxclient/cmdline-jmxclient-0.10.4.jar
java -jar cmdline-jmxclient-0.10.4.jar - xxx.xxx.xxx.xxx:12345
java -jar cmdline-jmxclient-0.10.4.jar - xxx.xxx.xxx.xxx:12345 java.lang:type=Threading

Exception が発生せず、何らかの情報が表示されればひとまずOK。

 

補足

ネットワーク関連の問題が発生した場合、JVM の起動オプションで以下のように自分自身のIPアドレスを明記することで解決する場合がある。

監視対象サーバ自身のIPアドレスを書く

-Djava.rmi.server.hostname=xxx.xxx.xxx.xxx

 

監視サーバの設定

 

Zabbix Java Gateway のインストール

Zabbix 2.2 の場合(であっても)、zabbix-server を入れただけでは JMX の監視はできない。

ソースをダウンロードしてビルドする方法もあるが、パッケージが公開されているのでそのままインストールしたほうが簡単だ。

実行例 (サービス登録および起動も実施)

# rpm -Uv http://repo.zabbix.com/zabbix/2.2/rhel/6/x86_64/zabbix-java-gateway-2.2.0-1.el6.x86_64.rpm
# chkconfig zabbix-java-gateway on
# service zabbix-java-gateway start

設定ファイルの編集
  • /etc/zabbix/zabbix_server.conf の修正 (一部抜粋)
    Timeout=30
    JavaGateway=127.0.0.1
    JavaGatewayPort=10052
    StartJavaPollers=5

    Java Gateway はデフォルトでは10052ポートで起動する。
    Timeout の修正(デフォルト5秒) については、デメリットもあるので問題が起きた場合にのみ書き換えたほうがよいかもしれない。

    参考: zabbix_server.confのTimeoutについて | ZABBIX-JP

設定ファイルを保存したら、zabbix-server から再読み込み (または再起動)。

監視設定

ここから先は Zabbix の管理画面(GUI)での操作となる。

ホスト設定

Configuration -> Hosts -> 監視対象サーバ を選択。
JMX interfaces の部分で Add をクリックし、IPアドレスとJMXポートを指定して Save。

テンプレート・アイテム設定

ひとまずは標準の Template JMX Generic を使ってみるのを勧める。

Configuration -> Templates -> Template JMX Generic を選択。
Group または Host の追加を行った後、Save。

ダッシュボード画面で ホストにひもづく JMX のアイコンが緑色になればOKだ。

References

 

12.13.2013

Installing Docker on CentOS 6.5 (with Vagrant and VirtualBox)

Vagrant+VirtualBox 環境の CentOS 6.5 に Docker をインストールする

 

こちらのブログポストの内容を実践してみた。

なぜ Docker か

Docker とは、Linux のホストOS上で複数の仮想 Linux OS(コンテナ)を実行するためのソフトウェア。

VMWare のようなハイパーバイザー型の仮想OSと異なり、ハードウェア層やカーネルの大部分が共通して使われるため、パフォーマンスのオーバーヘッドが少ない。

LXC (Linux Containers) と aufs (Advanced multi layered unification filesystem) という要素技術が使われており、
Docker自体は Go言語で記述されている。

Docker を使うモチベーションを挙げれば以下のような感じだ。

  • とにかく起動が速い
    aufs の恩恵により、差分ベースでファイルシステムが構築されていく。
    一瞬でOSが立ち上がる様は感動的ですらある。

    Immutable Infrastructure (出典: Trash Your Servers and Burn Your Code: Immutable Infrastructure and Disposable Components - Chad Fowler) の前に立ちはだかっていた壁の一つが音もなく崩れ去った瞬間を目の当たりにしている。

    仮想化技術によって、インフラの「作って捨てて」を非常に短いサイクルでできるようになった結果、
    我々はこれまで混然としていた Immutable (OS, ミドルウェアのバージョン、コンフィギュレーションなど) と Mutable (各種ログ、エラー通知、リソース推移など) の意味的な区別に専念できるようになったのだ。
  • 開発PCのローカル環境 -> CI環境 -> ステージング環境 -> プロダクション環境と、 同一性が保証されたインフラをハードウェア構成に依存せずに作成することができ、 しかもその内容をコードとして管理できる。 (Infrastructure as Code)

    Docker at eBay // Speaker Deck
    (プロダクション環境での利用実績はまだ少ないようだが)
  • 従って、たとえばCI環境で使えば、DB の状態に依存するテストでも並列かつ迅速に実行できる。

 

目的

Mac OS (Mavericks) 上で Vagrant を実行し、VirtualBox 上に CentOS 6.5 インスタンスを作成。
そこに Docker をインストールし、さらにその上に複数のゲストコンテナを実行できるようにする。

事前準備

  • Vagrant インストール
  • VirtualBox インストール

ホストOSのセットアップ

とりあえず今日は Mac 上で Vagrant を実行し、VirtualBox 内のホストOS(いわゆる母艦)に Docker をインストールするまで。

  • VirtualBox Guest Additions を更新するため、Vagrant プラグイン vagrant-vbguest をインストール
  • opscode のテンプレートを利用して vagrant init
  • Vagrantfile を編集し、後処理として epel から docker パッケージを取得しインストール、起動
  • vagrant up
  • Docker 上で Hello World!

 

 

References

12.12.2013

How to Format Line Numbers in Emacs

Emacs: 行番号表示のフォーマット指定

忘れがちなのでメモ。

Emacs における行番号表示は、init.el で global-linum-mode を指定すれば実現できるが、
以下のように linum-format を指定すればそのフォーマットをカスタマイズすることも可能だ。

(require 'linum)
(global-linum-mode t)
(setq linum-format "%4d ")

フォーマット文字列は C のアレと同じで、上記の例であれば
4桁分の領域に行番号の数字が表示され、その後に一個スペースが入る。

How to Clone a Large Git Repocitory

巨大な Git リポジトリを少しずつクローンする方法

ファイルサイズの非常に大きな Git リポジトリの場合、git clone を行った時に メモリが不足しエラーとなってしまうケースがある。

$ git clone git://xxxxxxxx.xxx:awesome-project.git
Cloning into 'awesome-project'...
remote: Counting objects: 9999, done.
remote: warning: suboptimal pack - out of memory
remote: fatal: Out of memory, malloc failed
error: git upload-pack: git-pack-objects died with error.
fatal: git upload-pack: aborting due to possible repository corruption on the remote side.
remote: aborting due to possible repository corruption on the remote side.
fatal: early EOF
fatal: index-pack failed

depth を指定して shallow copy を行うことで解決できる場合がある。

具体的な手順は、以下のブログが参考になった。

How to Solve Vagrant+CentOS+VirtualBox Mount Error

Vagrant+CentOS+VirtualBox: ゲストOS起動時のマウントエラーの調査

 

事象

Vagrant で CentOS 6 の VirtualBox 用イメージを立ち上げようとしたところ、以下のようなエラーが出てしまった。

$ vagrant up <HOSTNAME>

(略)

[HOSTNAME] Mounting shared folders...
[HOSTNAME] -- /vagrant
Failed to mount folders in Linux guest. This is usually beacuse
the "vboxsf" file system is not available. Please verify that
the guest additions are properly installed in the guest and
can work properly. The command attempted was:

mount -t vboxsf -o uid=`id -u xxxxxxxx`,gid=`getent group xxxxxxxx | cut -d: -f3` /vagrant /vagrant
mount -t vboxsf -o uid=`id -u xxxxxxxx`,gid=`id -g xxxxxxxx` /vagrant /vagrant

このメッセージだけでは、VirtualBox Guest Additions (以下、Guest Additions) の機能である共有フォルダのマウントに失敗していることくらいしか分からない。

ちなみに Guest Additions とは、簡単に言えば VirtualBox ゲストの管理に特化した便利ツールだ。

これを利用しないなら無視しても構わないのだろうが、やっぱり気になるので調べてみる。

 

調査

vagrant status コマンドを実行して、OS自体は起動していることは確認できた。

$ vagrant status

Current machine states:

HOSTNAME                  running (virtualbox)

SSH 接続をしてみよう。

$ vagrant ssh <HOSTNAME>

以下はゲストOS上のプロンプト。
Guest Additions の状態を確認すると、停止状態であることが分かる。

$ service vboxadd status
The VirtualBox Additions are not currently running.

Guest Additions のインストール自体が失敗している可能性があると考え、ログを確認する。

$ cat /var/log/vboxadd-install.log
/tmp/vbox.0/Makefile.include.header:97: *** Error: unable to find the sources of your current Linux kernel. Specify KERN_DIR=<directory> and run Make again.  中止.
Creating user for the Guest Additions.
Creating udev rule for the Guest Additions kernel module.

やはりここに答えがあった。
カーネルのソース (kernel-devel) が不足していたために、Guest Additions のビルドが失敗していたのだった。

対応

 

誤った対応

パッケージが足りないなら、yum でインストールすればよいと安直に

$ sudo yum install kernel-devel -y

と実行するのはよくない。

上記のコマンドでは (基本的に) 最新の kernel-devel がダウンロードされるため、
実際のカーネルバージョンと異なるものがインストールされてしまう可能性があるためだ。

カーネルバージョンと kernel-devel が食い違った状態で Guest Additions のセットアップをすると、やはりビルドは失敗となる。

$ sudo /etc/init.d/vboxadd setup
Removing existing VirtualBox non-DKMS kernel modules       [  OK  ]
Building the VirtualBox Guest Additions kernel modules
The headers for the current running kernel were not found. If the following
module compilation fails then this could be the reason.
The missing package can be probably installed with
yum install kernel-devel-2.6.32-358.el6.x86_64

Building the main Guest Additions module                   [失敗]
(Look at /var/log/vboxadd-install.log to find out what went wrong)
Doing non-kernel setup of the Guest Additions              [  OK  ]

それぞれのバージョンは以下のようなコマンドで確認できる。

$ uname -r
2.6.32-358.el6.x86_64
$ rpm -qa |grep kernel-devel
kernel-devel-2.6.32-431.el6.x86_64

アンインストール。

$ sudo yum remove kernel-devel

 

 

正しい対応

では、適切なバージョンの kernel-devel をインストールするにはどうしたらよいか。

残念ながら、このまま yum でバージョンを指定してもうまくいかない。

$ sudo yum install kernel-devel-$(uname -r) -y
Loaded plugins: fastestmirror
Loading mirror speeds from cached hostfile
 * base: ftp.riken.jp
 * extras: ftp.riken.jp
 * updates: ftp.riken.jp
Setting up Install Process
No package kernel-devel-2.6.32-358.el6.x86_64 available.
Error: Nothing to do

古いバージョンのパッケージは CentOS-Vault リポジトリに置かれている。
以下いずれかの方法で対応が可能だ。

  • /etc/yum.repos.d/CentOS-Vault.repo ファイルを編集
    適切なOSバージョンの記載を追加し、「enabled=0」 を「enabled=1」へ書き換える
  • URLを指定して直接ダウンロード
    $ sudo yum install http://vault.centos.org/6.4/os/x86_64/Packages/kernel-devel-$(uname -r).rpm

インストールを終えたらゲストOS上で、Guest Additions のセットアップを再度実行。

$ sudo /etc/init.d/vboxadd setup
Removing existing VirtualBox non-DKMS kernel modules       [  OK  ]
Building the VirtualBox Guest Additions kernel modules
Building the main Guest Additions module                   [  OK  ]
Building the shared folder support module                  [  OK  ]
Building the OpenGL support module                         [  OK  ]
Doing non-kernel setup of the Guest Additions              [  OK  ]
Starting the VirtualBox Guest Additions                    [  OK  ]

うまくいった。

$ service vboxadd status
The VirtualBox Additions are currently running.

目的は達成できたので、一度ゲストOSから抜け、Vagrant から再起動する。

$ vagrant reload <HOSTNAME>

マウントエラーは晴れて解消された。

 

 

References

11.16.2013

Python: Visualizing Histogram in Terminal

Python: ターミナル上でヒストグラムを可視化する

何本目の車輪か知らないが、ターミナル上でヒストグラムを可視化するスクリプトを再発明。

標準入力に対して、1行ずつ数字(整数or小数)を放り込むと 10個に分けた区間ごとの発生頻度を
「*」の数で可視化する。

1個または複数のファイルを指定して読み取ることも可能。(複数ファイルの場合は合算)

アクセスログや各種ログに含まれる数値の分布を即座に判断しなければならない場合などに使用している。
継続的に見るデータであれば、GrowthForecast などのツールを使った方がいいと思う。

コード

実行例

$ (for i in {1..10}; do echo $RANDOM; done) | ./print_histo.py
[  458.000,  3654.300): ************************                              1
[ 3654.300,  6850.600): ************************************************      2
[ 6850.600, 10046.900):                                                       0
[10046.900, 13243.200): ************************************************      2
[13243.200, 16439.500): ************************                              1
[16439.500, 19635.800):                                                       0
[19635.800, 22832.100): ************************                              1
[22832.100, 26028.400):                                                       0
[26028.400, 29224.700): ************************************************      2
[29224.700, 32421.000]: ************************                              1
$ (for i in {1..10000}; do echo $RANDOM; done) | ./print_histo.py
[    1.000,  3277.600): ********************************************        975
[ 3277.600,  6554.200): *********************************************      1002
[ 6554.200,  9830.800): *******************************************         949
[ 9830.800, 13107.400): ************************************************   1058
[13107.400, 16384.000): *********************************************      1011
[16384.000, 19660.600): **********************************************     1022
[19660.600, 22937.200): ********************************************        988
[22937.200, 26213.800): **********************************************     1016
[26213.800, 29490.400): **********************************************     1016
[29490.400, 32767.000]: *******************************************         963
$

11.08.2013

HBase: How to Change Count Printing Interval

HBase: hbase shell でのカウント間隔を変える

 

hbase shell で count コマンドを実行し行数をカウントする際、10,000件ごとに表示が出るのが煩わしければ

count '<テーブル名>', INTERVAL => 100000

のようにオプションを指定して表示間隔を変えることが可能。

HBase: How to Get the Size of a Table

HBase: テーブルのディスク使用量を調べる方法

 

hbase/テーブル名  ディレクトリの総容量を測ればよい。

OS のファイルシステムなら
  du -sh パス/hbase/テーブル名
など。

HDFS なら
  hadoop hdfs -du -s /hbase/テーブル名
でよい。

10.27.2013

Emacs: How to Insert Same String at the Beginning of Each Line

Emacs: 複数の行頭に文字を挿入する方法

  • まずリージョンを選択

    C-SPACE -> カーソル移動
    (文書全体を選択する場合は C-x h)
     
  • 各行の先頭にスペースを挿入する場合は

    C-x C-i
     
  • 各行の先頭に特定の文字列を挿入する場合は

    C-x r t

How to Install GNU Octave

GNU Octave のインストール方法

 

Machine Learning | Coursera の Week 2 の課題のため、Octave をインストールする。

Octave とは、フリーの数値解析ソフトウェア(プログラミング言語)。
行列の計算やグラフ描画(gnuplotと連携して可視化)が簡単にできることが特徴。

 

Windows

こちらからインストーラをダウンロードして実行。
Octave Forge - Browse /Octave Windows binaries at SourceForge.net 

Coursera の手順に書かれていたのは Octave-3.2.4_i686-pc-mingw32_gcc-4.4.0_setup.exe だった。

インストーラの Choose Components の画面で、"image" パッケージを追加するとよい。

 

Mac

こちらから Mac 用のディスクイメージをダウンロードしてマウント。
Octave Forge - Browse /Octave MacOSX Binary at SourceForge.net

最初、最新版(3.7.7)を入れたらグラフ表示でプログラムが落ちてしまう状態になったので
古いバージョン(3.4.0)をインストール。 

  • 事前に X.11 (XQuartz) をインストール
  • 例によって Octave.app を Applications フォルダにコピー。
  • 次に Gnuplot をインストールするのだが、ここに書いてあるとおり、MacOS Lion 以降だと実行時にエラーとなってしまう。
    Octave Forge - Browse /Octave MacOSX Binary/2011-04-21 binary of Octave 3.4.0 at SourceForge.net
  • Extras 配下の Gnuplot のディスクイメージもマウントし、Gnuplot.app を Applications フォルダにコピー。
  • シェルスクリプト /Applications/Gnuplot.app/Contents/Resources/bin/gnuplot をエディタで開き、
    「DYLD_LIBRARY_PATH」を「DYLD_FALLBACK_LIBRARY_PATH」に全て置換。
    (全部で4ヶ所。「=」の前後双方を置換する必要があるので注意。) 
  • .zshrc (.bashrc) にエイリアスを設定すると便利。
    alias octave="/Applications/Octave.app/Contents/Resources/bin/octave --persist --eval \"PS1('>> ')\""

 

実行例
octave-3.4.0:1> x=-5:5
x =

  -5  -4  -3  -2  -1   0   1   2   3   4   5

octave-3.4.0:2> y=2*x
y =

  -10   -8   -6   -4   -2    0    2    4    6    8   10

octave-3.4.0:3> plot(x,y)

Figure 1 

とりあえずグラフが描画できた。

10.15.2013

Algorithm: Bipartite Graph Matching

二部グラフの最大マッチング

 

output
[(0, 1), (1, 0)]
[(0, 1), (1, 0), (2, 2)]
[(1, 0)]
[(0, 1), (1, 0), (2, 2), (3, 4), (4, 3)]

10.14.2013

FizzBuzz Short Coding in Scala

Scala で FizzBuzz ショートコーディング

 

@lyrical_logical さんの素晴らしい資料からほぼ丸パクリ。

FizzBuzz golf in Scala - Google ドライブ

 

max を使う事で 1文字短縮でき、66 Bytes で書けた。

10.05.2013

Getting Started with Elixir - New Functional Programming Language

関数型言語 Elixir (エリクサー) を触ってみた

Erlang VM 上で動作する新しい関数型言語 Elixir (エリクサー) 。

FFファンならずともテンションの上がるネーミングだが
Ruby ライクなシンタックスで、動的型付けのカジュアルFPを目指しているようだ。

とりあえず環境を整えて、Hello world するまでの記録。

インストール

1 Introduction - Elixir に従って作業すればOK。

  • Erlang (R16B 以上) のインストール

    パッケージをここからダウンロードして実行
    Download Erlang OTP | Erlang Solutions

  • Elixir のインストール

    とりあえず、Mac にインストール。
    手っ取り早くインストールするなら HomeBrew で。

    $ brew install elixir

    最新版を入れるなら、以下の手順。

    $ cd <インストール先>
    $ git clone https://github.com/elixir-lang/elixir.git
    $ cd elixir
    $ make test
    $ bin/elixir -v    # Elixir のバージョンが表示されればOK
    $ sudo make install
    

    /usr/local/bin 配下にコマンドへのリンクが作成された。

iex - インタラクティブ シェル

モダンな言語なので当然(?)、REPL が標準で付いている。

  • 起動
    $ iex
    Erlang R16B02 (erts-5.10.3) [source-b44b726] [64-bit] [smp:4:4] [async-threads:10] [hipe] [kernel-poll:false]
    
    Interactive Elixir (0.10.4-dev) - press Ctrl+C to exit (type h() ENTER for help)
    iex(1)>
  • Hello world
    iex(1)> "Hello Elixir!"
    "Hello Elixir!"
    iex(2)> "こんにちは エリクサー"
    "こんにちは エリクサー"
    iex(3)> 'こんにちは エリクサー'
    [12371, 12435, 12395, 12385, 12399, 12288, 12456, 12522, 12463, 12469, 12540]
    

    ダブルクオートで囲むと UTF-8 でエンコードされたバイナリとして、
    シングルクオートだと 1文字ずつの数値のリストとして認識される。

  • FizzBuzz

    手探り状態で書いてみた。もっと改善できるはず。

    f = fn
      x when rem(x, 15) == 0 -> "FizzBuzz"
      x when rem(x, 3) == 0 -> "Fizz"
      x when rem(x, 5) == 0 -> "Buzz"
      x -> to_string(x)
    end
    
    1..20 |> Enum.map(f) |> Enum.map(&1 <> "\n") |> IO.write
    

    文字列の連結(<>)が分からずに小一時間悩んだ。

    output
    iex:58: partial application without capture is deprecated
    1
    2
    Fizz
    4
    Buzz
    Fizz
    7
    8
    Fizz
    Buzz
    11
    Fizz
    13
    14
    FizzBuzz
    16
    17
    Fizz
    19
    Buzz

    警告が出たけど、解決策がすぐには分からない。

 

まとめ

Erlang も Ruby も慣れていない私にはかなり異次元の文法に見える。
とはいえ、Erlang の強力な機能を利用したプログラムを手軽に実装できるなら魅力的だ。

日本人は最後までエリクサーを使わないという定説もあるけど、やっぱりそれはもったいない。

 

References

Combinatorial Optimization: Merge-Sort Algorithm

組合せ最適化: アルゴリズム 1.2 マージソートアルゴリズム

B.コルテ/J.フィーゲン 著「組合せ最適化 理論とアルゴリズム 第2版」の例を Python で実装してみる。

 

output
[-2, -1, 0, 1, 2, 3, 4, 5, 90]
[-2, -1, 0, 1, 2, 3, 4, 5, 90]
[-2, -1, 0, 1, 2, 3, 4, 5, 90]
['ac', 'b', 'bb', 'bc', 'c', 'ca']
['ac', 'b', 'bb', 'bc', 'c', 'ca']
['ac', 'b', 'bb', 'bc', 'c', 'ca']
[0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9]
[0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9]
[0.0, 1.1, 2.2, 3.3, 4.4, 5.5, 6.6, 7.7, 8.8, 9.9]
identity が出てくるのが面白い。

10.04.2013

Combinatorial Optimization: Path Enumeration Algorithm

組合せ最適化: アルゴリズム 1.1 パス列挙アルゴリズム

B.コルテ/J.フィーゲン 著「組合せ最適化 理論とアルゴリズム 第2版」の例を Python で実装してみる。

 

output
[0, 1, 2, 3]
[0, 1, 3, 2]
[0, 2, 1, 3]
[0, 2, 3, 1]
[0, 3, 1, 2]
[0, 3, 2, 1]
[1, 0, 2, 3]
[1, 0, 3, 2]
[1, 2, 0, 3]
[1, 2, 3, 0]
[1, 3, 0, 2]
[1, 3, 2, 0]
[2, 0, 1, 3]
[2, 0, 3, 1]
[2, 1, 0, 3]
[2, 1, 3, 0]
[2, 3, 0, 1]
[2, 3, 1, 0]
[3, 0, 1, 2]
[3, 0, 2, 1]
[3, 1, 0, 2]
[3, 1, 2, 0]
[3, 2, 0, 1]
[3, 2, 1, 0]
120
(0, 1, 2, 3)
(0, 1, 3, 2)
(0, 2, 1, 3)
(0, 2, 3, 1)
(0, 3, 1, 2)
(0, 3, 2, 1)
(1, 0, 2, 3)
(1, 0, 3, 2)
(1, 2, 0, 3)
(1, 2, 3, 0)
(1, 3, 0, 2)
(1, 3, 2, 0)
(2, 0, 1, 3)
(2, 0, 3, 1)
(2, 1, 0, 3)
(2, 1, 3, 0)
(2, 3, 0, 1)
(2, 3, 1, 0)
(3, 0, 1, 2)
(3, 0, 2, 1)
(3, 1, 0, 2)
(3, 1, 2, 0)
(3, 2, 0, 1)
(3, 2, 1, 0)
(13, [(5, 2), (3, 3), (1, 1), (1, 4), (4, 8), (2, 10)])

9.29.2013

Representation of Floating-Point Numbers

浮動小数点数のまとめ

概要

  • 限られたビットの中で小数を表現する方法の一つが浮動小数点数
  • 今日の実装は処理系、言語を問わずIEEE方式(IEEE 754)が標準
  • とりあえずIEEE方式の倍精度浮動小数点数(C言語のdouble)の仕組みを覚えておけばいい
 
Wikipedia

浮動小数点数 - Wikipedia
IEEE 754 - Wikipedia

IEEE 754

IEEE 754: Standard for Binary Floating-Point Arithmetic

 

ビットの表現

小数を「(符号) 基数2の指数×仮数」で表現するのが基本的な考え方。
倍精度浮動小数点数の場合、64ビットを以下の3つの部分に分けて意味を持たせる。

 

Sign (符号部, 1bit)
  • 0 なら +, 1 なら - を表す
Exponent (指数部, 11bits)
  • 11ビットの符号無し整数で表現できるのは 0〜2047(=2^11-1)。
  • 0(全てのビットが0)と2047(全てのビットが1)は特殊な用途(後述)で使用される。
  • 1〜2046の範囲を、1023 のバイアス付き整数(ゲタ履き表現)で表す。
    例えば符号無し整数の値が 1 であれば -1022、1023 であれば 0、2046 であれば 1023 を意味する。
  • だいたい ±1000 と覚えておけば、ビット数を忘れても思い出しやすい
  • 基数を 10 で考えると、だいたい 1e-308 〜 1e+308 の範囲を表せる
Significand (仮数部, 52bits)
  • 指数部を掛け合わせる前の絶対値
  • 整数部分が 1 になるように指数部を調整する(正規化)ので、整数部分の1は明らかであり表現しない。(hidden bitと呼ばれる)
  • 例えば仮数が10進表記で 1.75 である場合は、2進表記だと 1.11。
    整数部分を除外して、仮数部の表現は 11000000...(以下0が続く) となる。
  • 0付近のごく小さい数を表すために、非正規化表現も用意されている。
    (アンダーフローギャップを埋めるための重要な仕組み)
 

表現の種類

IEEE 754 では5種類の表現が定義されている。

s = sign (0 or 1)
q = exponent (指数部の符号無し整数表記)
c = significand (仮数部の符号無し整数表記) <=小数ではなく整数として見た場合の値

としたときの計算式と合わせて書くと以下のようになる。

種類exponent(q)significand(c)表している値
ゼロ 0 0 +0, -0 (符号の区別がある)
非正規化数 0 1〜 NewImage
正規化数 1〜2046 0〜 NewImage
無限大 2047 0 NewImage
NaN(非数) 2047 1〜 基本的に符号の区別はない (詳細はWikipedia参照)

 

実装の確認

C言語でも可能だが、手っ取り早く Python で確認してみた。
(PyPIからbitarrayをインストールする) 

出力例
                   sign
      double      : v <exponent > <                   significant                    >
======================================================================================
               0.0: 0 00000000000 0000000000000000000000000000000000000000000000000000
              -0.0: 1 00000000000 0000000000000000000000000000000000000000000000000000
               2.0: 0 10000000000 0000000000000000000000000000000000000000000000000000
               3.0: 0 10000000000 1000000000000000000000000000000000000000000000000000
               1.0: 0 01111111111 0000000000000000000000000000000000000000000000000000
               0.1: 0 01111111011 1001100110011001100110011001100110011001100110011010
               nan: 0 11111111111 1000000000000000000000000000000000000000000000000000
               inf: 0 11111111111 0000000000000000000000000000000000000000000000000000
              -inf: 1 11111111111 0000000000000000000000000000000000000000000000000000
2.22507385851e-308: 0 00000000001 0000000000000000000000000000000000000000000000000001
1.79769313486e+308: 0 11111111110 1111111111111111111111111111111111111111111111111111
2.22507385851e-308: 0 00000000000 1111111111111111111111111111111111111111111111111111
4.94065645841e-324: 0 00000000000 0000000000000000000000000000000000000000000000000001

9.28.2013

TopCoder: Setting up KawigiEdit

TopCoder: KawigiEdit のセットアップ手順

 

KawigiEdit とは

Kawigi氏が作成した、TopCoder 用のエディタプラグイン。(最新版は Pivanof 氏がメンテ)
以下の特徴を持つ。

  • 全ての言語(Java, C++, C#, VT, Python)に対応
  • FileEdit のように外部ファイルと同期できる
  • テンプレートからコードを生成できる
  • 問題文からシグニチャとテストコードを自動生成できる

SRMでこのようなプラグインを利用するのは許可されており、チートとは見なされない。 
Competing in a Rated Algorithm Competition - TopCoder Wiki

ドキュメント
KawigiEdit Documentation

 

ダウンロード

KawigiEdit_x.x.jar を適当な場所に保存。 (私はDropbox上に置いている)

 

エディタの追加

  • Arena アプレットを起動
  • メニューから Options -> Editor を選択
  • Add ボタンを押下し、以下の設定を入力
    • Name: KawigiEdit
    • EntryPoint: kawigi.KawigiEdit
    • ClassPath: ダウンロードした jar ファイルのパス
  • 好みに応じて Default, At Startup のチェックを付けて Save

 

各種設定

  • Editor Preferences の画面で KawigiEdit を選択し Configure ボタンを押下
    • General/Testing
      • 作業ディレクトリの指定
        IDEを使ってコードを書く場合には、そのソースディレクトリを指定するとよい。
      • Synchronization with external file
        外部ファイルとの連携。チェックONにする。
      • Always prefer external file to TC source
        外部ファイルを優先ソースとする。チェックONに。
      • Save problem statement to external file
        外部ファイルにコメントとして問題文を記述。チェックONに。
         

他はデフォルトのままでも基本的に問題なさそう。

テンプレートを変えたい場合は言語ごとに .ket ファイルを作成する。

また、デフォルトのプログラミング言語の変更はこの画面ではなく
Arena のメニューから Options -> Setup User Preferences を開き、
Editors タブ -> Default Language で行うのを忘れがち。

9.17.2013

Coding Python in Emacs

Emacs で Python コーディング

 

Emacs で Python 開発環境を整える手順。
ただ挫折しそうになったので今は IntelliJ IDEA (ultimate) がメイン。

対象環境

  • Emacs 2.4

プラグインのインストール

  • init.el の編集
    以下の内容を追加し、ダウンロード先を追加。
    (require 'package)
    (add-to-list 'package-archives '("melpa" . "http://melpa.milkbox.net/packages/") t)
    (add-to-list 'package-archives '("marmalade" . "http://marmalade-repo.org/packages/"))
    (package-initialize)
  • Emacsを起動し、「M-x package-list-packages」でパッケージの一覧を取得
  • 「python-mode」「pep8」をインストール
    (C-n などで画面を移動し、Enter、C-x o などのコマンドで遷移。

基本的な操作

  • C-c C-c: バッファの内容を実行
  • C-c C-z: Pythonプログラムの実行バッファを表示

Flymake などの設定は以下を参照。

References

9.12.2013

Scala: How to Compare Array Contents

Scala: Array の内容を比較する方法

 

Scala における Array の実装は Java の配列である。

["collections"] - 配列 - Scala Documentation

そのため List などと異なって(*1)、Array どうしを比較した場合、内容が同じでも true が返ることはない。
Array の equals() メソッドが単純な参照の比較しかしないからだ。

scala> val a = Array(1,2,3)
a: Array[Int] = Array(1, 2, 3)

scala> val b = Array(1,2,3)
b: Array[Int] = Array(1, 2, 3)

scala> a == b
res0: Boolean = false

scala> a equals b
res1: Boolean = false

scala> a eq b
res2: Boolean = false

内容の比較を行う際には、以下のように sameElements() を利用するのが最善とされている。

scala> a sameElements b
res3: Boolean = true

deep どうしを比較したり、corresponds を使ったりしても同じことが実現できる。

scala> a.deep == b.deep
res4: Boolean = true

scala> a.corresponds(b)(_ == _)
res5: Boolean = true

 

 

*1: GenSeqLike.scala で equals メソッドがオーバーライドされている。

Scala: Converting From Number List To Cumulative List

Scala: 数列から累積値のリストを作る

 

目的

a[0], a[1], a[2], ... , a[n] のような数値が入ったリストを元に、

b[0] = a[0]
b[1] = a[0] + a[1]
b[2] = a[0] + a[1] + a[2]
...
b[n] = a[0] + a[1] + a[2] + ... + a[n] 

が成り立つ累積値のリスト b[0], b[1], b[2], ... , b[n] を作成したい。

 

コード

scanLeft (scan でも可) メソッドがまさに適役である。

scala> List(1, 3, 5, 2, 4).scanLeft(0)(_ + _)
res0: List[Int] = List(0, 1, 4, 9, 11, 15)

scala> List(1, 3, 5, 2, 4).scanLeft(0)(_ + _).tail
res1: List[Int] = List(1, 4, 9, 11, 15)

初期値 0 を元手に累積的に加算を行った後、tail で先頭の 0 を取り除いている。

 

数値を右から足し込みたい場合には、scanRight が使える。

scala> List(1, 3, 5, 2, 4).scanRight(0)(_ + _).init
res2: List[Int] = List(15, 14, 11, 6, 4)

体感としても、計算量 Θ(n) になっている模様。

9.08.2013

C++: How to Count the Frequency of the Elements in a Container

C++: コンテナ中の要素の出現頻度をカウントする

 

コード

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

template <class InputIterator>
std::vector<std::pair<typename InputIterator::value_type, int> >
frequency(InputIterator first, InputIterator last) {
  typedef typename InputIterator::value_type ValType;
  typedef std::map<ValType, int> MapType;
  typedef std::vector<std::pair<ValType, int> > VecType;

  MapType m;
  for (InputIterator it = first; it != last; ++it) {
    if (m.find(*it) == m.end()) {
      m.insert(typename MapType::value_type(*it, 1));
    } else {
      ++m[*it];
    }
  }

  return VecType(m.begin(), m.end());
}

// for utility
template <typename T>
std::ostream & operator<<(std::ostream & stream, std::vector<T> & v) {
  stream << "[";
  for (typeof(v.begin()) i = v.begin(); i != v.end(); ++i) {
    if (i != v.begin()) { stream << ", "; }
    stream << *i;
  }
  stream << "]";
  return stream;
}
template <typename T, typename U>
std::ostream & operator<<(std::ostream & stream, std::pair<T, U> & p) {
  stream << "(" << p.first << ", " << p.second << ")";
  return stream;
}
#define print(a) std::cout << a << std::endl
#define all(a) (a).begin(),(a).end()

// main
using namespace std;

int main(int argc, char **argv) {
  string apple = "apple";
  vector<pair<char, int> > a = frequency(all(apple));
  print(apple << ": " << a);

  int xs[] = { 1, 3, 5, 4, 3, 2 };
  vector<int> v(xs, xs + sizeof(xs) / sizeof(xs[0]));
  vector<pair<int, int> > b = frequency(all(v));
  print(v << ": " << b);
}

 

出力例

apple: [(a, 1), (e, 1), (l, 1), (p, 2)]
[1, 3, 5, 4, 3, 2]: [(1, 1), (2, 1), (3, 2), (4, 1), (5, 1)]

やはり、Scalaとかに比べるとストレスフルだなあ。

9.04.2013

Scala: Trimming Trailing Elements - List, Array and Vector

シーケンスから末尾のゼロ要素を削除する処理の性能測定

 

こちらの投稿が気になったので手元でも実験してみる。 

How do I remove trailing elements in a Scala collection? - Stack Overflow

 

計測コード

時間計測用のトレイトと、トリミング関数 2種類を用意した。

トリミング関数に渡す数列は、ランダムな数列の後ろに一定数の「0」を付け加えたもの。
List, Array, Vector のそれぞれで所要時間を計測する。 

10,000回のループを 3セット実行し、実行時間が最も短かった結果を評価する。

import scala.util.Random

trait TimeIt {
  def timeit(description: String = "", repeat: Int = 3, number: Int = 10000)(proc: => Unit) {
    def loop[A](n: Int)(f: => A) { if (n > 0) { f; loop(n - 1)(f) } }

    val elapsed = List.fill(repeat){
      val start = System.currentTimeMillis
      loop(number)(proc)
      System.currentTimeMillis - start
    }.min
    println(s"${description}: ${elapsed} msec")
  }
}

object TrimArray extends TimeIt {
  def trimA[A](a: Seq[A]) = a.reverse.dropWhile(_ == 0).reverse
  def trimB[A](a: Seq[A]) = a.take(a.lastIndexWhere(_ != 0) + 1)

  def main(args: Array[String]) {
    for (
      randoms <- List(10, 100, 1000);
      zeros <- List(10, 100, 1000)
    ) {
      // Create random sequence.
      val list = List.fill(randoms)(Random.nextInt) ++ List.fill(zeros)(0)
      val array = list.toArray
      val vector = list.toVector

      println(s"randoms: ${randoms}, zeros: ${zeros}")
      timeit("[1] List   -> reverse + dropWhile  "){ trimA(list) }
      timeit("[2] List   -> take + lastIndexWhere"){ trimB(list) }
      timeit("[3] Array  -> reverse + dropWhile  "){ trimA(array) }
      timeit("[4] Array  -> take + lastIndexWhere"){ trimB(array) }
      timeit("[5] Vector -> reverse + dropWhile  "){ trimA(vector) }
      timeit("[6] Vector -> take + lastIndexWhere"){ trimB(vector) }
    }
  }
}

 

実行結果

計測してみると、全体的に take + lastIndexWhere バージョンが明らかに速い結果となった。

ただし、List だけは take 処理で性能劣化が発生するため、末尾のゼロ要素が少なければ reverse バージョンの方が逆転して速くなることもあった。(ex. randoms: 1000, zeros: 10)

また、全体のシーケンスが長ければ長いほど、Vector の強さが際立ってくるのが面白い。

randoms: 10, zeros: 10
[1] List   -> reverse + dropWhile  : 11 msec
[2] List   -> take + lastIndexWhere: 4 msec
[3] Array  -> reverse + dropWhile  : 7 msec
[4] Array  -> take + lastIndexWhere: 3 msec
[5] Vector -> reverse + dropWhile  : 12 msec
[6] Vector -> take + lastIndexWhere: 13 msec
randoms: 10, zeros: 100
[1] List   -> reverse + dropWhile  : 22 msec
[2] List   -> take + lastIndexWhere: 13 msec
[3] Array  -> reverse + dropWhile  : 18 msec
[4] Array  -> take + lastIndexWhere: 6 msec
[5] Vector -> reverse + dropWhile  : 38 msec
[6] Vector -> take + lastIndexWhere: 9 msec
randoms: 10, zeros: 1000
[1] List   -> reverse + dropWhile  : 177 msec
[2] List   -> take + lastIndexWhere: 89 msec
[3] Array  -> reverse + dropWhile  : 93 msec
[4] Array  -> take + lastIndexWhere: 28 msec
[5] Vector -> reverse + dropWhile  : 235 msec
[6] Vector -> take + lastIndexWhere: 54 msec
randoms: 100, zeros: 10
[1] List   -> reverse + dropWhile  : 25 msec
[2] List   -> take + lastIndexWhere: 21 msec
[3] Array  -> reverse + dropWhile  : 45 msec
[4] Array  -> take + lastIndexWhere: 12 msec
[5] Vector -> reverse + dropWhile  : 48 msec
[6] Vector -> take + lastIndexWhere: 4 msec
randoms: 100, zeros: 100
[1] List   -> reverse + dropWhile  : 37 msec
[2] List   -> take + lastIndexWhere: 29 msec
[3] Array  -> reverse + dropWhile  : 53 msec
[4] Array  -> take + lastIndexWhere: 15 msec
[5] Vector -> reverse + dropWhile  : 68 msec
[6] Vector -> take + lastIndexWhere: 9 msec
randoms: 100, zeros: 1000
[1] List   -> reverse + dropWhile  : 187 msec
[2] List   -> take + lastIndexWhere: 108 msec
[3] Array  -> reverse + dropWhile  : 130 msec
[4] Array  -> take + lastIndexWhere: 55 msec
[5] Vector -> reverse + dropWhile  : 276 msec
[6] Vector -> take + lastIndexWhere: 59 msec
randoms: 1000, zeros: 10
[1] List   -> reverse + dropWhile  : 235 msec
[2] List   -> take + lastIndexWhere: 244 msec
[3] Array  -> reverse + dropWhile  : 525 msec
[4] Array  -> take + lastIndexWhere: 156 msec
[5] Vector -> reverse + dropWhile  : 385 msec
[6] Vector -> take + lastIndexWhere: 4 msec
randoms: 1000, zeros: 100
[1] List   -> reverse + dropWhile  : 303 msec
[2] List   -> take + lastIndexWhere: 240 msec
[3] Array  -> reverse + dropWhile  : 503 msec
[4] Array  -> take + lastIndexWhere: 152 msec
[5] Vector -> reverse + dropWhile  : 435 msec
[6] Vector -> take + lastIndexWhere: 11 msec
randoms: 1000, zeros: 1000
[1] List   -> reverse + dropWhile  : 406 msec
[2] List   -> take + lastIndexWhere: 314 msec
[3] Array  -> reverse + dropWhile  : 559 msec
[4] Array  -> take + lastIndexWhere: 170 msec
[5] Vector -> reverse + dropWhile  : 659 msec
[6] Vector -> take + lastIndexWhere: 101 msec

8.29.2013

Scala: Making List of the Result of 'n' Times Function Calls with Stream

Scala: 関数をn回適用した結果のリストを作る

 

scala.collection.immutable.Stream を使うと簡単にできる。

以下は、適当な文字列の左右を「#」で囲む関数を 1回, 2回, ... と適用した結果をリストにして返す例。
(Scala 2.10, REPLで実行) 

 

scala> def f(s: String) = s"#${s}#"
f: (s: String)String

scala> def g(s: String): Stream[String] = s #:: g(f(s))
g: (s: String)Stream[String]

scala> g("x").tail.take(5).toList
res0: List[String] = List(#x#, ##x##, ###x###, ####x####, #####x#####)

 

 

2013-08-30 追記

今回の目的であれば、iterate メソッドを使った方が適しているとご指摘をいただきました。
List#iterate, Iterator#iterate, Stream#iterate を使った例です。 

scala> def f(s: String) = s"#${s}#"
f: (s: String)String

scala> List.iterate(f("x"), 5)(f)
res0: List[String] = List(#x#, ##x##, ###x###, ####x####, #####x#####)

scala> Iterator.iterate("x")(f).drop(1).take(5).toList
res19: List[String] = List(#x#, ##x##, ###x###, ####x####, #####x#####)

scala> Stream.iterate("x")(f).tail.take(5).toList
res26: List[String] = List(#x#, ##x##, ###x###, ####x####, #####x#####)

こちらの方が素敵ですね。

Mac: How to Improve Your Performance with Alfred

Mac: Alfred 活用術

 

Alfred は、Mac を使うなら是非インストールしておきたいフリーソフト。

呼び出し用のキーバインド(私は option + SPACE に設定)を叩いた後、テキストを数文字打って
Enter を押すだけで様々なアプリケーション・OS機能を呼び出すことができる。

WEB のカスタムサーチは特に秀逸で、

  • 「ds キーワード」と打って Dash と連携させたり
  • 「r チケット番号」と打って Redmine のチケットを直接呼び出したり
    • Search URL: (ご利用中のRedmineのURL)/{query}
    • Keyword: r
  • 「a 英単語」または「a 日本語の単語」と打って アルク の和訳・英訳辞書を直接呼び出したり
    • Search URL: http://eow.alc.co.jp/search?q={query}
    • Keyword: a

することが可能だ。 

有料の PowerPack を使えば、より生産性が上がるらしいので目下検討中。

8.26.2013

Mac: How to Use Option as Meta Key in KeySnail

Mac: KeySnail で option キーを メタキーとして使う方法

 

Firefox の (主にEmacsユーザ向けの) キーボード・ブラウジング環境構築プラグイン KeySnail を使っている。

これを Mac 環境で使用したところ、option キーをメタキーとして使おうとしてもうまくいかず、
メタキーを使うキーバインドが一切動作しない状況に陥った。

試行錯誤の末、正しく動作するようになったのでその方法を記録しておく。

 

環境

  • Hardware: MacBook Air (USキーボード)
  • OS: OS X 10.8
  • Firefox: 23.0.1
  • KeySnail: 2.0.1

事象

デフォルト状態の KeySnail では、Altキー・Command キーの入力がメタキーとして解釈される。
keysnail/wiki/howto.ja.wiki at master · mooz/keysnail

Firefox では、Mac の optionキーが Altキーの働きと同等となるので、
optionキーを使ってメタキーのキーバインド (M-w, M-x など) ができると期待した。

(Command キーをメタキーとして扱うのは違和感があるのであまり使いたくない。) 

ところが optionキーを使ったメタキー操作は全く動作しない。

  • control と option を同時に押した時のキーバインドは正しく動作する。(C-M-r など)
  • C-q でエスケープしたあとに option+x などと入力しても、表示されるのは「null」

 

原因

OS X では (デフォルト状態では)、option キーを押しながら他のキーを入力すると特殊文字(å∫ç∂...)の入力が
行われる。

これらのキーを押下したときのイベントでは event.altKey が true にならないので
メタキーかどうかを判定する key.isMetaKey 関数を素通りしてしまう。

 

対応方法

key.keyEventToString 関数をフックして、イベントを特定するための文字列を書き換えればそれなりに動くようだ。

charCode を取得し、特殊文字 かどうかを判定した上で "M-" で始まる文字列に置換する。
(例えば、∑ (charCode=8721) が入力されたらなら "M-w" に置き換える)

このような処理を行う option-as-meta というプラグインが既に存在していたので、それをそのまま利用する。

これで optionキーをメタキーとして使えるようになった。

 

補足

optionキーではなく ESCキーをメタキーとして使用したいのであれば、「Metaplus」プラグインを利用するのが
最も確実な方法と思われる。

Plugin · mooz/keysnail Wiki 

 

8.24.2013

How to Use Option as Meta Key in iTerm2

iTerm2 で Mac の option キーを Meta キーとして使う方法

iTerm -> Preferences -> Profiles -> Keys

Preferences

設定としては、「Meta」よりも「+Esc」が推奨されるとのこと。

これで Emacs 周りの操作性が改善された。

Python: Increasing All Numbers in Text File

Python: テキスト中の数字を全てインクリメントする

目的

Vim における Ctrl-A (Increasing or decreasing numbers - Vim Tips Wiki) のように
テキスト中の数字を全てインクリメントする処理を Python で行いたい。

コード

textprocessor を利用する。

正規表現モジュールの split 関数を利用して1行分の文字列を「数字部分」と「数字以外」に切り分けて、
数字部分のみを +1 することでシンプルに書けた。 

今回は「0」で始まる2文字以上の数字(00, 01 など)は特別にインクリメント対象から除外している。

また、マイナス記号は単なる「数字以外の文字」として扱われるため、負数のインクリメントには対応していない。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import re
import textprocessor

tokenizer = re.compile(r'(\d+)').split


def convert(token):
    if token != '0' and token.startswith('0'):
        return token
    return str(int(token) + 1)


def increment(line):
    tokens = tokenizer(line)
    tokens = [x if i % 2 == 0 else convert(x) for (i, x) in enumerate(tokens)]
    print(''.join(tokens))


if __name__ == '__main__':
    textprocessor.process(increment)

実行例

  • 準備したファイル
    a
    1
    b2
    3c
    d4e
    5f6
    7 8 9
    w0rd
    -5 -4 -3 -2 -1 0 1 2 3 4 5
    [0, 00, 01, 02, 03, 04, 05]
    0.0 1.1 2.2 3.3 4.4 5.5
    9.99 999.9999 99999.999999
    
  • 実行結果
    $ ./increment.py ./test.txt
    a
    2
    b3
    4c
    d5e
    6f7
    8 9 10
    w1rd
    -6 -5 -4 -3 -2 1 2 3 4 5 6
    [1, 00, 01, 02, 03, 04, 05]
    1.1 2.2 3.3 4.4 5.5 6.6
    10.100 1000.10000 100000.1000000
    
GitHub

 

Related Posts

Python: Helper Function for Text Processing

Python: テキスト処理のためのヘルパー関数

AWKのようなテキスト処理に特化した作業を Python で楽に行うための関数を作った。

#!/usr/bin/env python
# -*- coding: utf-8 -*-
"""
Helper function for text stream processing
"""

import sys


def process(function):
    paths = (sys.argv + [None])[1:max(2, len(sys.argv))]
    for path in paths:
        try:
            fp = sys.stdin if path is None else open(path)
            for line in fp:
                function(line.rstrip("\n"))
        except (KeyboardInterrupt, EOFError):
            pass
        except Exception:
            exc_type, exc = sys.exc_info()[:2]
            print('%s: %s: %s' % (sys.argv[0], exc_type.__name__, exc))

コマンドライン引数が指定されない場合は標準入力から、指定された場合はそれぞれの引数をファイルパスと
見なして全ての入力を順に1行ずつ読み込み、何らかの処理を行う。

process 関数の引数にはパラメータを1個取る関数を渡す。
そのパラメータには、読み込まれた入力が1行ずつ、末尾の改行が除去された文字列として渡される。 

 

利用例

入力をそのまま標準出力へ出力するだけの処理

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import textprocessor


def identity(line):
    print(line)


if __name__ == '__main__':
    textprocessor.process(identity)

 

実行例
    • 準備したファイル
line1
line2

 

  • 標準入力から流し込む

 

$ cat ./test.txt | ./identity.py
line1
line2

 

  • ファイルパスを指定して実行

 

$ ./identity.py ./test.txt
line1
line2

 

  • 複数のファイルを指定して実行

 

$ ./identity.py ./test.txt ./test.txt
line1
line2
line1
line2

 

  • エラーケース

 

$ ./identity.py xxxxxx
./identity.py: IOError: [Errno 2] No such file or directory: 'xxxxxx'

 

Related Posts

8.23.2013

Getting Started with KeySnail - Mouseless Browsing on Firefox

Firefox + KeySnail でマウスレス・ブラウジングを始める

 

今更ながらマウスレス・ブラウジングの便利さに目覚めた。

Firefox でのキーボード操作拡張プラグインは以下の2つが主流のようである。

Emacs 修行中の私としては、KeySnail を選ばざるを得ない。

 

本体のインストール

こちらのページから keysnail.xpi をダウンロードして Firefox で開き、インストールする。

keysnail japanese · mooz/keysnail Wiki

とても簡単。

 

初回起動

Firefox を再起動すると、設定ファイルを新規作成するか尋ねられる。

新規作成の場合、設定ファイルのパス、デフォルトのキーバインドを選択。
今回はとりあえず Dropbox 上にファイルを作っておいた。 

Screenshot 8 23 13 03 14

 

プラグイン導入

今日のところは、キーボードでリンク遷移を行うための HoK をインストールするところまで。

  • HoK
    こちらのページから、HoK を右クリックして Install this plugin。
    Plugin · mooz/keysnail Wiki 

    インストールが済んだら、.keysnail.js (_keysnail.js) の末尾に以下の内容を追記。
    key.setViewKey('e', function (aEvent, aArg) {
        ext.exec("hok-start-foreground-mode", aArg);
    }, 'Hok - Foreground hint mode', true);
    
    key.setViewKey('E', function (aEvent, aArg) {
        ext.exec("hok-start-background-mode", aArg);
    }, 'HoK - Background hint mode', true);
    
    key.setViewKey(';', function (aEvent, aArg) {
        ext.exec("hok-start-extended-mode", aArg);
    }, 'HoK - Extented hint mode', true);
    
    key.setViewKey(['C-c', 'C-e'], function (aEvent, aArg) {
        ext.exec("hok-start-continuous-mode", aArg);
    }, 'Start continuous HaH', true);
    
    key.setViewKey('c', function (aEvent, aArg) {
        ext.exec("hok-yank-foreground-mode", aArg);
    }, 'Hok - Foreground yank hint mode', true);
    

    そして、設定ファイルをリロードすれば準備完了。(Tools -> KeySnail -> Reload init file)

    Webサイトを開いて「e」キーを押せば、各リンク先に対応したショートカットキーが表示され、
    そのキーボード操作でリンクを開けるようになる。 

 

これから慣れていきたい。

 

References

 

8.22.2013

How to Convert Int to ByteArray in Python

Python: 数値などをバイト配列に変換する方法

Python 2.5 より登場した struct モジュールを使うと便利。

詳細は以下を参照。
7.3. struct — 文字列データをパックされたバイナリデータとして解釈する — Python 2.7ja1 documentation 

下記は全てリトルエンディアンのマシン下での実行例。

>>> import struct
  • Int からバイト配列の変換
    >>> struct.pack('i', 1)
    '\x01\x00\x00\x00'
    >>> [struct.pack('i', x) for x in (0, 1, 65, -1, 2000000000)]
    ['\x00\x00\x00\x00', '\x01\x00\x00\x00', 'A\x00\x00\x00', '\xff\xff\xff\xff', '\x00\x945w']
    >>> [len(struct.pack('i', x)) for x in (0, 1, 65, -1, 2000000000)]
    [4, 4, 4, 4, 4]
  • ビッグエンディアンで格納
    >>> struct.pack('>i', 1)
    '\x00\x00\x00\x01'
    >>> struct.pack('!i', 1)
    '\x00\x00\x00\x01'
    
  • Int 以外の型のエンコード
    >>> struct.pack('3?Q', True, False, True, 5L)
    '\x01\x00\x01\x00\x00\x00\x00\x00\x05\x00\x00\x00\x00\x00\x00\x00'
    >>> struct.pack('dc10s', 0.025, 'X', 'python')
    '\x9a\x99\x99\x99\x99\x99\x99?Xpython\x00\x00\x00\x00'
  • バイト配列から Int へのデコード
    >>> struct.unpack('i', '\x01\x02\x03\x04')
    (67305985,)
    
    要素が一つでもタプルが返る。
  • Struct クラスを使う
    >>> s = struct.Struct('i')
    >>> s.pack(1)
    '\x01\x00\x00\x00'
    
    フォーマット文字列がコンパイルされた状態で保持される。
    同じフォーマットを何度も使い回す場合に効率的。

8.04.2013

How to Find Invisible Characters in Emacs/Vim

Emacs/Vim: 特定のASCIIコードを検索する方法

0x0c (改ページ) を検索する場合

  • Emacs
    Ctrl-s Ctrl-q Ctrl-l
    または
    Ctrl-s Ctrl-q 1 4 Enter
    (8進数で指定する(0x0c(16進)=014(8進))、16進で指定する方法はないのだろうか?) 
  • Vim
    /\%x0c

Handling UTF-8 in Python 2.x

Python 2系で UTF-8 を取り扱う際の心得

 

Python 2系での日本語の扱い方について、忘れた頃に忘れてしまうのでメモ。

ソースで日本語(UTF-8)を使う

まずは基本から。

ソースの1行目または2行目にコメントを入れ、正規表現 coding[:=]\s*([-\w.]+) にマッチする文字列を書けばよい。

普通は以下のように書く。

# -*- coding: utf-8 -*-

shebang 付き (ここで Python のバージョンを指定したほうがよい場合もある)

#!/usr/bin/env python
# -*- coding: utf-8 -*-

 

3つの文字列クラス

Python 2系の場合、今扱っているオブジェクトが何者かを意識することが大切。

  • str
    ASCII文字列向けに設計された文字列クラスだが、その中にはテキスト以外も格納できるので
    実態はバイト配列のようなものとなっている。
    >>> 'abc'
    'abc'
    >>> '\x03'
    '\x03'
    >>> 'あいう'
    '\xe3\x81\x82\xe3\x81\x84\xe3\x81\x86'
    >>> type('abc')
    <type 'str'>
    
  • unicode
    あらゆる文字コードのUnicode文字列を抽象化したクラス。 
    >>> u'abc'
    u'abc'
    >>> u'\x03'
    u'\x03'
    >>> u'あいう'
    u'\u3042\u3044\u3046'
    >>> print u'\u3042\u3044\u3046'
    あいう
    >>> type(u'abc')
    <type 'unicode'>
    
  • basestring
    基底の抽象クラス。
    文字列クラスかどうかを判定する場合に使用。
    >>> isinstance('abc', str)
    True
    >>> isinstance(u'abc', str)
    False
    >>> isinstance('abc', basestring)
    True
    >>> isinstance(u'abc', basestring)
    True

 

2つのメソッド

str 型から unicode 型への変換をデコード、その逆をエンコードと呼ぶ。
その変換処理は str クラスのメソッドとして定義されている。

これらのメソッドは、encoding と errors という 2つの引数を取る。

  • encoding: 変換に使用する codec 名。
        デフォルトは defaultencoding の値。
        defaultencoding は sys.getdefaultencoding() で取得できるもので、そのデフォルトは 'ascii'。 
  • erros: エラーハンドラ名。デフォルトは 'strict' (変換に失敗したら例外を発生)

 

明示的にエンコードする

厄介なエンコードエラーが発生する主な要因は、暗黙的なエンコード・デコード処理と
エンコーディングのミスマッチにある。 

>>> str(u'あいう')
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
UnicodeEncodeError: 'ascii' codec can't encode characters in position 0-2: ordinal not in range(128)

これは前述の str.encode() メソッドにおける encoding が省略された状態で実行されたのと同じ現象が起きている。
この場合は utf-8 でデコードされた unicode オブジェクト(u'あいう')が、
defaultencoding である ascii でエンコードされたためにエラーとなってしまったのだ。

とはいえ実行時に defaultencoding を変更するのは、不可能ではないが特別な理由が無い限りすべきではない。
他のモジュールへもその影響が波及してしまうため、思わぬトラブルを引き起こすリスクがある。

解決策の一つは、以下のように明示的にエンコード・デコードを行うこと。そうすればエラーは起こらない。

>>> str(u'あいう'.encode('utf-8'))
'\xe3\x81\x82\xe3\x81\x84\xe3\x81\x86'

"Zen of Python" の『曖昧さにあたっては推測をしたがるな』に従おう。 

>>> import this
(略)
In the face of ambiguity, refuse the temptation to guess.
(略)

 

IO境界でラップする

Unicode の取り扱いに関するたった一つのベストプラクティスは、IO境界 --
つまりファイルの読み書きや、ネットワーク通信、画面出力などのタイミングで変換することだ。

 

  • 入力のタイミングで、str から unicode にデコード
  • 出力のタイミングで、unicode から str にエンコード
  • 内部処理は全て unicode 文字列として取り扱う

Python 2.6 から利用可能になった io モジュールを使えばラッピングを簡便にしてくれる。

  • ファイル入出力
    >>> import io
    >>> with io.open(FILEPATH, mode='w', encoding='utf-8') as file:
    ...     file.write(u'あいう\n')
    ...
    4L
    
  • 標準入出力
    標準出力を io.open() で開き直せば、適切なエンコーディングが選択される。 
    >>> import io, sys
    >>> stdout = io.open(sys.stdout.fileno(), 'w')
    >>> stdout.write(u'あいう\n')
    あいう
    4L
    
    io.open() の場合、encoding パラメータを指定しなくても、環境に応じてよしなに
    エンコーディングを判断してくれるのが素晴らしい。
    実際には後述の locale.getpreferredencoding() の値が参照されているようだ。

Python クックブック(1.22章)には codecs.lookup を使った以下のような方法も掲載されていた。

>>> import codecs, sys
>>> old = sys.stdout
>>> sys.stdout = codecs.lookup('utf-8')[-1](sys.stdout)

 

環境に応じたエンコーディングを取得する

Python が実行された環境の標準的なエンコーディングを動的に取得するにはどうすればよいか。

完全な方法ではないものの、以下の2種類のアプローチを順に試せば大半の環境で意図した動作となるようだ。

  • ファイルの encoding 属性
    属性が存在しない場合もあるので、getattr() を使ったほうが安全。 
    • 例) Mac (utf-8)
      >>> import sys
      >>> getattr(sys.stdout, 'encoding', None)
      'UTF-8'
    • 例) Windows (SJIS)
      >>> import sys
      >>> getattr(sys.stdout, 'encoding', None)
      'cp932'
    • 例) Solaris (SJIS)
      >>> import sys
      >>> getattr(sys.stdout, 'encoding', None)
      >>>
  • locale.getpreferredencoding()
    • 例) Mac (utf-8)
      >>> import locale
      >>> locale.getpreferredencoding()
      'UTF-8'
    • 例) Windows (SJIS)
      >>> import locale
      >>> locale.getpreferredencoding()
      'cp932'
    • 例) Solaris (SJIS)
      >>> import locale
      >>> locale.getpreferredencoding()
      'PCK'

 

まとめ

  1. まず始めに、プログラムの設計段階で全てのIO境界を洗い出す

    (図に書くのが一番よい)
     
  2. それぞれのIO境界において、どのエンコーディング(utf-8等)で
    変換(decode, encode)を行うのか整理する

    (同時に、環境に依存する部分や動的に取得する部分を明確にする)
     
  3. 明示的な変換(decode, encode)、明示的なエンコーディングの指定をする

    (実行環境の defaultencoding (デフォルトはUS-ASCII) に依存しない実装をする)
    (ライブラリ or 自作のラッパーを利用してもよい)
     
  4. それでも UnicodeDecodeError, UnicodeEncodeError が発生してしまったら、
    変換前のデータ・データ型・変換しようとしたエンコーディングを再確認する 

 

 

References

7.28.2013

Reading Event Data on Google Calendar in Python

Python: Google Calendar のイベント情報を読み取るスクリプト

 

ライブラリのインストール

google-api-python-client を利用する。

google-api-python-client - Google APIs Client Library for Python - Google Project Hosting

$ sudo pip install google-api-python-client

 

認証用のファイルを準備

このような画面操作でサンプルを手に入れることができる。それを参考にする。

Installation  Google APIs Client Library for Python  Google Developers

認証は、client_secrets.json というJSON形式のファイルを使うのが推奨されているようだ。
このファイルも手打ちする必要はなく、ダウンロードボタン一発で入手できる。 

Client Secrets - Google APIs Client Library for Python — Google Developers

サンプルをたたくと、初回に client_secrets.json を元にFlow オブジェクトが生成される。

このとき、どのAPIにどのレベルでアクセスするかを指定する。
今回はカレンダーの読み取りだけなので、'https://www.googleapis.com/auth/calendar.readonly' があれば十分。

その内容が Storage オブジェクトとなり、ファイルに保存される。
今回は read_calendar.dat というファイル名にした。 

認証情報(credentials)が完成したら、httplib2、build() 関数を使って Calendar API v3 にアクセスすればよい。 

 

コード

今日一日の予定を出力するコード。
プログラムの第一引数に整数を入れれば、n日後の予定を取得できる。

対象のカレンダーIDは予め調べて、ハードコーディング。

予定の開始時刻、終了時刻、内容、作成者をソートして出力するため、OneDayEvent というクラスを作っている。

タイムゾーンの調整はしていない。(手抜き)
もっとコメント書いた方がいいけどこれも手抜き。

Calendar API のサービスを取得した後、
service.events()list(...).execute() で条件に見合ったイベントのリストを取得している。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import httplib2
import os
import sys
import datetime

from apiclient.discovery import build
from oauth2client.file import Storage
from oauth2client.client import AccessTokenRefreshError
from oauth2client.client import flow_from_clientsecrets
from oauth2client.tools import run

# Calendar id for reading.
CALENDAR_ID = 'xxxxxxxxxxxxxxxxxxxxxxxxxx@xxxxx.calendar.google.com'

# Path to the credential files.
BASE_DIR = lambda x: os.path.join(os.path.dirname(__file__), x)

CLIENT_SECRETS_PATH = BASE_DIR('client_secrets.json')
STORAGE_PATH = BASE_DIR('read_calendar.dat')

# Set up a Flow object to be used for authentication.
FLOW = flow_from_clientsecrets(CLIENT_SECRETS_PATH, scope=[
    'https://www.googleapis.com/auth/calendar.readonly',
])


def get_calendar_service():
    storage = Storage(STORAGE_PATH)
    credentials = storage.get()

    if credentials is None or credentials.invalid:
        credentials = run(FLOW, storage)

    http = httplib2.Http()
    http = credentials.authorize(http)

    service = build('calendar', 'v3', http=http)
    return service


class OneDayEvent(object):
    def __init__(self, start_time, end_time, summary, creator):
        if start_time is None:
            assert(end_time is None)
        self.start_time = start_time
        self.end_time = end_time
        self.summary = summary
        self.creator = creator

    def __lt__(self, that):
        if self.start_time is None and that.start_time is None:
            return self.summary < that.summary
        if self.start_time is None or that.start_time is None:
            return self.start_time is None
        return (self.start_time, self.end_time, self.summary, self.creator) < (
            that.start_time, that.end_time, that.summary, that.creator)

    def __str__(self):
        if self.start_time is None:
            tm = u'終日'
        else:
            f = lambda x: datetime.datetime.strftime(x, '%H:%M')
            tm = '%s-%s' % (f(self.start_time), f(self.end_time))
        return u'[%s] %s (%s)' % (tm, self.summary, self.creator)


def read_events(date):
    """Returns sorted list of OneDayEvent objects."""

    def format(x):
        return datetime.datetime.strftime(x, '%Y-%m-%dT%H:%M:%SZ')

    time_min = datetime.datetime.combine(date, datetime.time())
    time_max = time_min + datetime.date.resolution

    time_min, time_max = map(format, (time_min, time_max))

    service = get_calendar_service()
    events = service.events().list(
        calendarId=CALENDAR_ID, timeMin=time_min, timeMax=time_max).execute()

    def f(x):
        y = x.get('dateTime')
        if y:
            z = datetime.datetime.strptime(y[:-6], '%Y-%m-%dT%H:%M:%S')
            return datetime.datetime.combine(date, z.time())

    ret = [OneDayEvent(
        f(event['start']), f(event['end']), event['summary'],
        event['creator']['displayName']) for event in events['items']]
    ret.sort()
    return ret


def main(argv):
    offset = int(argv[1]) if len(argv) >= 2 else 0

    for event in read_events(
            datetime.date.today() + datetime.date.resolution * offset):
        print(unicode(event))

if __name__ == '__main__':
    main(sys.argv)

 

 

  • 出力例
    [終日] 有給休暇 (James LaBrie)
    [11:00-12:00] ○○様来社 (John Petrucci)
    [14:00-15:00] [外出] △△訪問 (John Myung)
    [17:30-22:00] □□勉強会 (Jordan Rudess)
    [17:30-23:00] ☆☆飲み会 (Mike Mangini)

 

References

 

Python: Sending IRC Message, Improved

Python: IRCメッセージ送信処理の改善

 

こちらのエントリの改善。
mog project: How to Send an IRC Message with SSL in Python

複数のメッセージを一度に送れるようにした。

あと、disconnect() の時にサーバでエラーが出ていたので削除した。

# -*- coding: utf-8 -*-
 
import ssl
 
SERVER_ADDRESS = 'xxx.xxx.xxx.xxx'
SERVER_PORT = 6667
SERVER_PASS = 'xxxxxx'
 
LOGIN_NAME = 'xxxxxx'
LOGIN_CHANNEL = '#xxxxxx'


def send(message):
    try:
        import irc.client
        import irc.connection

        if isinstance(message, basestring):
            message = [message]

        client = irc.client.IRC()
        server = client.server()
        factory = irc.connection.Factory(wrapper=ssl.wrap_socket)

        c = server.connect(
            SERVER_ADDRESS, SERVER_PORT, LOGIN_NAME, SERVER_PASS,
            connect_factory=factory)

        for m in message:
            c.privmsg(LOGIN_CHANNEL, m)
    except Exception as e:
        print('WARN: Failed to send IRC message. (%s)' % e)

7.22.2013

Counting Bits in Python, C++ and Scala (Pt.2)

各プログラミング言語で バイナリファイルの中にある 1 のビットの数をカウントする (その2)

 

こちらのエントリの続き
mog project: Counting Bits in Python, C++ and Scala (Pt.1)

 

C++ 実測 (3)

方法(1)を途中の段階まで実施して配列を横断して加算していく方法。
Hacker's Delight の実装を参考にした。

8ビット単位まで各個計算を行うバージョンを METHOD 3、16ビット単位のバージョンを METHOD 4 としている。

コード

これまでのコードも含め、全体を掲載する。

#define METHOD 3

#include <fstream>
#include <vector>
#include <string>
#include <ctime>
#include <cassert>

using namespace std;

int const kChunkSize = 1 << 14;

// METHOD 1
int POP(unsigned long long x) {
  unsigned long long const y = 0x3333333333333333ULL;
  x -= (x >> 1) & 0x5555555555555555ULL;
  x = (x & y) + ((x >> 2) & y);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
  x += x >> 8;
  x += x >> 16;
  x += x >> 32;
  return x & 0x7f;
}

// METHOD 2
int table[1 << 16];

void init_table() {
  for (int i = 0; i < (1 << 16); ++i) table[i] = POP(i);
}

int POP2(unsigned long long x) {
  return table[x & 0xffff] +
      table[(x >> 16) & 0xffff] +
      table[(x >> 32) & 0xffff] +
      table[(x >> 48)];
}

// METHOD 3
int POP_ARRAY(unsigned long long a[], int n) {
  unsigned long long s, s8, x;
  unsigned long long const y = 0x3333333333333333ULL;

  s = 0;
  for (int i = 0; i < n; i += 31) {
    int lim = min(n, i + 31);
    s8 = 0;
    for (int j = i; j < lim; ++j) {
      x = a[j];
      x -= (x >> 1) & 0x5555555555555555ULL;
      x = (x & y) + ((x >> 2) & y);
      x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
      s8 += x;
    }
    x = (s8 & 0x00ff00ff00ff00ffULL) + ((s8 >> 8) & 0x00ff00ff00ff00ffULL);
    x += x >> 16;
    x += x >> 32;
    s += x & 0xffff;
  }
  return s;
}

// METHOD 4
int POP_ARRAY2(unsigned long long a[], int n) {
  unsigned long long s, s16, x;
  unsigned long long const y = 0x3333333333333333ULL;

  s = 0;
  for (int i = 0; i < n; i += 4095) {
    int lim = min(n, i + 4095);
    s16 = 0;
    for (int j = i; j < lim; ++j) {
      x = a[j];
      x -= (x >> 1) & 0x5555555555555555ULL;
      x = (x & y) + ((x >> 2) & y);
      x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
      x = (x + (x >> 8)) & 0x00ff00ff00ff00ffULL;
      s16 += x;
    }
    x = (s16 & 0x0000ffff0000ffffULL) + ((s16 >> 16) & 0x0000ffff0000ffffULL);
    x += x >> 32;
    s += x & 0xffffffff;
  }
  return s;
}

template <typename T, typename U>
double time_it(int iter, int count, T func, U val) {
  double elapsed = 1e30;
  for (int i = 0; i < iter; ++i) {
    clock_t t = clock();
    for (int j = 0; j < count; ++j) {
      func(val);
    }
    clock_t s = clock();
    elapsed = min(elapsed, static_cast<double>(s - t) / CLOCKS_PER_SEC);
  }
  return elapsed;
}

int count_bit(string path) {
  int ret = 0;
  unsigned long long x[kChunkSize];

  ifstream fin(path.c_str(), ios::in | ios::binary);
  while (true) {
    fin.read(reinterpret_cast<char *>(&x), sizeof(unsigned long long) * kChunkSize);
    if (fin.eof()) break;
#if METHOD == 1
    for (int i = 0; i < kChunkSize; ++i) ret += POP2(x[i]);
#elif METHOD == 2
    for (int i = 0; i < kChunkSize; ++i) ret += POP2(x[i]);
#elif METHOD == 3
    ret += POP_ARRAY(x, kChunkSize);
#elif METHOD == 4
    ret += POP_ARRAY2(x, kChunkSize);
#endif
  }
  fin.close();
  return ret;
}

int main(int argc, char *argv[]) {
  string paths[] = {"00.bin", "01.bin", "02.bin", "03.bin", "04.bin", "05.bin",
      "06.bin", "07.bin", "08.bin", "09.bin", "10.bin", "11.bin"};
  string prefix = "../data/";
  int expected[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
      100000000, 1000000000, 1 << 30};

  init_table();
  for (int i = 0; i < 12; ++i) {
    string path = prefix + paths[i];
    assert(count_bit(path) == expected[i]);
    printf("%s: %f sec\n", paths[i].c_str(), time_it(3, 10, count_bit, path));
  }
  return 0;
}

 

実行結果
00.bin: 0.571133 sec
01.bin: 0.563557 sec
02.bin: 0.562696 sec
03.bin: 0.559637 sec
04.bin: 0.563524 sec
05.bin: 0.567378 sec
06.bin: 0.567318 sec
07.bin: 0.563231 sec
08.bin: 0.561556 sec
09.bin: 0.563927 sec
10.bin: 0.566986 sec
11.bin: 0.563692 sec

1 回の処理あたり 約 56ms。テーブル検索版よりも速い結果となった。

 

C++ 実測 (4)

実測(3) の配列横断処理を行う前処理の単位を 8ビットから 16ビットに変更して計測。
コードの1行目を #define METHOD 4 とする

実行結果
00.bin: 0.646128 sec
01.bin: 0.645220 sec
02.bin: 0.640301 sec
03.bin: 0.638049 sec
04.bin: 0.636916 sec
05.bin: 0.634473 sec
06.bin: 0.638034 sec
07.bin: 0.649389 sec
08.bin: 0.642163 sec
09.bin: 0.639769 sec
10.bin: 0.635853 sec
11.bin: 0.637499 sec

1 回の処理あたり 約 63ms。8ビット版よりも遅くなってしまった。

 

 

Scala の並列処理の実測はまた後日。

7.21.2013

mogtype - The Simplest Kana Typing Training Tool

mogtype - 最もシンプルなタイピングソフト

 

かな入力で、さらさら日本語の文章が書けるようになりたい!と最近思っているのだが
英語キーボードでも動く「かな入力」の練習ソフトがなかなか見当たらない。(まぁ相当なニッチ需要だけど) 

という訳で、かな入力に特化した、
コマンドラインで動く簡単なタイピングソフトを Python + curses で作ってみた。

Mac でのみ動作確認済み。

  • GitHub
    mogproject/mogtype
  • ヘルプ
    $ ./mogtype.py -h
    Usage: mogtype.py [options]
    
    Options:
      --version             show program's version number and exit
      -h, --help            show this help message and exit
      -f PATH, --file=PATH  path to the sentence database (default: mogtype.txt)
      -c COUNT, --count=COUNT
                            number of exercises (default: 8)
  • 使用方法

    引数(-f)で指定したテキストファイル(省略時は mogtype.txt)の内容がランダムでお題になる。

    $ ./mogtype.py -f ./mogtype.txt
  • 画面サンプル
    Screenshot 7 21 13 22 12 2
    カーソルで現在入力中の位置を表現。

    Screenshot 7 21 13 22 14 4
    ミスをするとこんな感じ。

    なお、画面上のtypoは修正済み。(Accurancy->Accuracy)
     
  • このファイルを変更すれば、異なるキーマッピングにも対応できる
    mogtype/keymap.py at master · mogproject/mogtype 

 

とりあえず動く状態になったけど、今後随時バージョンアップしていきたい。

 

 

References

ひらがな/カタカナの変換はこちらを参考にさせて頂きました。

7.18.2013

Counting Bits in Python, C++ and Scala (Pt.1)

各プログラミング言語で バイナリファイルの中にある 1 のビットの数をカウントする (その1)

 

目的

128 MB のバイナリファイル中にある 1 のビットの数を知りたい。
なお、128 MB = 2^7 MB = 2^17 KB = 2^27 Byte = 2^30 Bit なので求める値は 0 以上 2^30 以下となる。 

これを、並列処理なしの Python, C++, 並列処理ありの Scala でコードを書き、
手元の Mac で所要時間を調べてみる。

 

おことわり
実施環境も処理内容も、(私自身の勉強のために)とりあえず今作れるもので試しただけですので
言語自体の性能を比較する意図はございません。

  

データ作成

実測の前に、1のビットが n 個含まれるランダムなバイナリデータを予め用意しておく。

これは Python で、bitarray ライブラリを利用して行った。
さらに、大きな bitarray に対して random.shuffle を行うと所要時間が恐ろしく長くなるので
2^12 ビットのサイズのバケットを予めランダムに作っておくことで処理時間を短縮した。

参考:
mog project: Python: Random Partition of Integer 

 

bitarray のインストール

bitarray 0.8.1 : Python Package Index

$ sudo pip install bit array
コード
import random
import math
import timeit
from bitarray import bitarray
from random_partition import random_partition

ARRAY_SIZE = 1 << 30
CHUNK_SIZE = 1 << 12

TEST_COUNTS = [
    (0, '00.bin'), (1, '01.bin'), (10, '02.bin'), (100, '03.bin'),
    (1000, '04.bin'), (10000, '05.bin'), (100000, '06.bin'),
    (1000000, '07.bin'), (10000000, '08.bin'), (100000000, '09.bin'),
    (1000000000, '10.bin'), (1 << 30, '11.bin')]


def make_bitarray(size, count):
    assert(count <= size)

    ret = bitarray(size)
    if count == size:
        ret.setall(True)
    else:
        ret.setall(False)
        if count != 0:
            ret[:count] = True
            random.shuffle(ret)
    return ret


def make_file(count, path):
    # Create buckets.
    num_buckets = int(math.ceil(float(ARRAY_SIZE) / CHUNK_SIZE))
    buckets = random_partition(num_buckets, count, CHUNK_SIZE)

    # Write to file.
    with open(path, 'wb') as fh:
        for b in buckets:
            make_bitarray(CHUNK_SIZE, b).tofile(fh)
    print('Created: %s' % path)


if __name__ == '__main__':
    timeit.__dict__.update(make_file=make_file)
    for t in TEST_COUNTS:
        time = timeit.Timer('make_file(%d, "%s")' % (t[0], t[1])).timeit(1)
        print('%f sec' % time)

 

実行結果

AWS (t1.micro) で一晩コトコト煮込んだデータ。(約7.2時間)
gzip 圧縮して全部で 41 MB。 

$ python ./make_test_file.py
Created: 00.bin
3.845612 sec
Created: 01.bin
3.803929 sec
Created: 02.bin
3.650161 sec
Created: 03.bin
4.306574 sec
Created: 04.bin
10.518001 sec
Created: 05.bin
47.784271 sec
Created: 06.bin
213.532356 sec
Created: 07.bin
716.523029 sec
Created: 08.bin
4907.577745 sec
Created: 09.bin
8589.099633 sec
Created: 10.bin
11360.644969 sec
Created: 11.bin
30.384724 sec

Python 実測

bitarray の count 関数を使うだけ。

コード
import timeit
from bitarray import bitarray


TEST_COUNTS = [
    (0, '00.bin'), (1, '01.bin'), (10, '02.bin'), (100, '03.bin'),
    (1000, '04.bin'), (10000, '05.bin'), (100000, '06.bin'),
    (1000000, '07.bin'), (10000000, '08.bin'), (100000000, '09.bin'),
    (1000000000, '10.bin'), (1 << 30, '11.bin')]
PATH_PREFIX = '../data/'


def count_bit(path):
    x = bitarray()
    with open(path, 'rb') as fh:
        x.fromfile(fh)
    return x.count()

if __name__ == '__main__':
    for t in TEST_COUNTS:
        path = PATH_PREFIX + t[1]
        assert(count_bit(path) == t[0])
        timeit.__dict__.update(count_bit=count_bit)
        time = min(timeit.Timer('count_bit("%s")' % path).repeat(3, 10))
        print('%s: %f sec' % (t[1], time))

 

実行結果
00.bin: 1.858225 sec
01.bin: 1.860906 sec
02.bin: 1.858306 sec
03.bin: 1.846741 sec
04.bin: 1.853473 sec
05.bin: 1.840856 sec
06.bin: 1.836229 sec
07.bin: 1.852755 sec
08.bin: 1.864767 sec
09.bin: 1.851672 sec
10.bin: 1.839153 sec
11.bin: 1.824429 sec

1 回の処理あたり 約 185ms。
ちなみにそのおよそ半分がファイル読み込みに要する時間。

 

C++ 実測 (1)

まずは普通のカウント方法で。
一度にストリームから読み込むサイズは試行錯誤の末、2^14 (個の long long int) に落ち着いた。

if stream は read() した後で EOFチェックしないと正しい値にならない。

コード
#include <fstream>
#include <vector>
#include <string>
#include <ctime>
#include <cassert>

using namespace std;

int const kChunkSize = 1 << 14;

int POP(unsigned long long x) {
  unsigned long long const y = 0x3333333333333333ULL;
  x -= (x >> 1) & 0x5555555555555555ULL;
  x = (x & y) + ((x >> 2) & y);
  x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;
  x += x >> 8;
  x += x >> 16;
  x += x >> 32;
  return x & 0x7f;
}

template <typename T, typename U>
double time_it(int iter, int count, T func, U val) {
  double elapsed = 1e30;
  for (int i = 0; i < iter; ++i) {
    clock_t t = clock();
    for (int j = 0; j < count; ++j) {
      func(val);
    }
    clock_t s = clock();
    elapsed = min(elapsed, static_cast<double>(s - t) / CLOCKS_PER_SEC);
  }
  return elapsed;
}

int count_bit(string path) {
  int ret = 0;
  unsigned long long x[kChunkSize];

  ifstream fin(path.c_str(), ios::in | ios::binary);
  while (true) {
    fin.read(reinterpret_cast<char *>(&x), sizeof(unsigned long long) * kChunkSize);
    if (fin.eof()) break;
    for (int i = 0; i < kChunkSize; ++i) ret += POP(x[i]);
  }
  fin.close();
  return ret;
}

int main(int argc, char *argv[]) {
  string paths[] = {"00.bin", "01.bin", "02.bin", "03.bin", "04.bin", "05.bin",
      "06.bin", "07.bin", "08.bin", "09.bin", "10.bin", "11.bin"};
  string prefix = "../data/";
  int expected[] = {0, 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000,
      100000000, 1000000000, 1 << 30};

  for (int i = 0; i < 12; ++i) {
    string path = prefix + paths[i];
    assert(count_bit(path) == expected[i]);
    printf("%s: %f sec\n", paths[i].c_str(), time_it(3, 10, count_bit, path));
  }
  return 0;
}

 

実行結果
00.bin: 0.821018 sec
01.bin: 0.808333 sec
02.bin: 0.809245 sec
03.bin: 0.809044 sec
04.bin: 0.809715 sec
05.bin: 0.809076 sec
06.bin: 0.813601 sec
07.bin: 0.813362 sec
08.bin: 0.812772 sec
09.bin: 0.808916 sec
10.bin: 0.811492 sec
11.bin: 0.811594 sec

1 回の処理あたり 約 81ms。

 

C++ 実測 (2)

テーブル検索を行うバージョン。

コード
int table[1 << 16];

void init_table() {
  for (int i = 0; i < (1 << 16); ++i) table[i] = POP(i);
}

int POP2(unsigned long long x) {
  return table[x & 0xffff] +
      table[(x >> 16) & 0xffff] +
      table[(x >> 32) & 0xffff] +
      table[(x >> 48)];
}

 

実行結果
00.bin: 0.608648 sec
01.bin: 0.598598 sec
02.bin: 0.597612 sec
03.bin: 0.601898 sec
04.bin: 0.600394 sec
05.bin: 0.596191 sec
06.bin: 0.595793 sec
07.bin: 0.600928 sec
08.bin: 0.615904 sec
09.bin: 0.622860 sec
10.bin: 0.629954 sec
11.bin: 0.600881 sec

1 回の処理あたり 約 60ms。だいぶ速くなった。

 

 

残り(C++で配列中のビットを累積的に調べる/Scala実測を行う予定)はまた次回。

7.16.2013

Installing tmux with Fabric

Fabric で tmux をインストール

yum でインストールするだけだけど。

# -*- coding: utf-8 -*-
"""
Installing tmux.
"""

from fabric.api import *
from fabric.decorators import runs_once, roles, task

env.user = 'ec2-user'
env.use_ssh_config = True

@task
def install():
    """Install tmux."""
    sudo('yum -y install tmux')

これで、寝ている間も安心して AWS に仕事を任せられる。

 

References

tmux 公式

AWS: EC2 Restore Script

AWS: EC2インスタンスをスナップショットから復元するスクリプト

 

スナップショットのリストアに伴う一連の操作をスクリプト化。

デバイスが EBS 1個だけの場合にのみ対応。

コード

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import subprocess
import time
try:
    import json
except ImportError:
    print('You need python 2.6 or later to run this script.')
    sys.exit(1)


def usage():
    print('Usage: %s <instance-id> <snapshot-id>' % sys.argv[0])
    sys.exit(2)


def run_command(*args):
    output = subprocess.check_output(['aws', 'ec2'] + list(args))
    return json.loads(output)


def get_volume_id(instance):
    assert(len(instance['BlockDeviceMappings']) == 1)
    return instance['BlockDeviceMappings'][0]['Ebs']['VolumeId']


def get_zone(instance):
    return instance['Placement']['AvailabilityZone']


def get_device(instance):
    assert(len(instance['BlockDeviceMappings']) == 1)
    return instance['BlockDeviceMappings'][0]['DeviceName']


def is_running(instance):
    return instance['State']['Code'] == 16


def is_stopped(instance):
    return instance['State']['Code'] == 80


def get_instance(instance_id):
    j = run_command('describe-instances', '--instance-ids', instance_id)
    return j['Reservations'][0]['Instances'][0]


def start_instance(instance_id):
    sys.stdout.write('Starting instance: %s ...' % instance_id)
    run_command('start-instances', '--instance-ids', instance_id)

    for i in range(20):
        sys.stdout.write('.')
        time.sleep(10)
        if is_running(get_instance(instance_id)):
            break
    else:
        raise(RunTimeError('Timed out for waiting.'))
    print('OK')


def stop_instance(instance_id):
    sys.stdout.write('Stopping instance: %s ...' % instance_id)
    run_command('stop-instances', '--instance-ids', instance_id)

    for i in range(20):
        sys.stdout.write('.')
        time.sleep(10)
        if is_stopped(get_instance(instance_id)):
            break
    else:
        raise(RunTimeError('Timed out for waiting.'))
    print('OK')


def detach_volume(volume_id):
    sys.stdout.write('Detaching volume: %s ...' % volume_id)
    run_command('detach-volume', '--volume-id', volume_id)
    print('OK')


def create_volume(zone, snapshot):
    sys.stdout.write('Creating volume from snapshot: %s ...' % snapshot)
    j = run_command(
        'create-volume', '--availability-zone', zone,
        '--snapshot-id', snapshot)
    print('OK')
    return j['VolumeId']


def attach_volume(volume_id, instance_id, device):
    sys.stdout.write('Attaching volume: %s ...' % volume_id)
    run_command(
        'attach-volume', '--volume-id', volume_id,
        '--instance-id', instance_id, '--device', device)
    print('OK')


def delete_volume(volume_id):
    sys.stdout.write('Deleting volume: %s ...' % volume_id)
    run_command('delete-volume', '--volume-id', volume_id)
    print('OK')


if __name__ == '__main__':
    if len(sys.argv) != 3:
        usage()

    instance_id = sys.argv[1]
    snapshot = sys.argv[2]

    sys.stdout.write('Checking instance: %s ...' % instance_id)
    ins = get_instance(instance_id)

    old_vol = get_volume_id(ins)
    print('OK')

    stop_instance(instance_id)
    detach_volume(old_vol)
    new_vol = create_volume(get_zone(ins), snapshot)
    attach_volume(new_vol, instance_id, get_device(ins))
    start_instance(instance_id)
    delete_volume(old_vol)

実行例

$ ./aws_restore.py i-xxxxxxxx snap-XXXXXXXX
Checking instance: i-xxxxxxxx ...OK
Stopping instance: i-xxxxxxxx .......OK
Detaching volume: vol-yyyyyyyy ...OK
Creating volume from snapshot: snap-XXXXXXXX ...OK
Attaching volume: vol-zzzzzzzz ...OK
Starting instance: i-xxxxxxxx .....OK
Deleting volume: vol-yyyyyyyy ...OK

7.15.2013

Python: Random Partition of Integer

Python: ランダムな整数分割の実装

目的

  • 非負整数 n を 和を保ったまま m 個のバケットにランダムに分割したい
  • そのとき、各バケットの内容が上限 k を超えないようにする。
  • 制約
    • 0 <= n < 2^31
    • 1 <= m < 2^19
    • 0 <= k < 2^31
    • n <= m * k
  • 言い換えれば、n, m, k が与えられた時に、以下を満たす数値のリスト x[i] (0 <= i < m) を
    ランダムに求めたい。
    • ∀i (0 <= x[i] <= k)
    • Σ x[i] = n
 

アイデア

二分木と再帰を使ってリストを作る。

動作イメージは以下のとおり。

 Blog 20130715

m = 1 ならばそれは葉なので計算終了。(値は n)
それ以外は、ほぼ半数になるように m を左右に振り分ける。

振り分ける個数を左から順に m1, m2、振り分ける数値を n1, n2 とした場合、制約から

  • a) n1 + n2 = n
  • b) 0 <= n1
  • c) 0 <= n2
  • d) n1 <= m1 * k
  • e) n2 <= m2 * k
を満たす必要がある。
 
e) に a) の n2 = n - n1 を代入すれば、n1 >= n - m2 * k という不等式が導けるので
n1 は以下の制約を持つことになる。 
  • 0 <= n1 <= n    a), b), c) から
  • n - m2 * k <= n1 <= m1 * k    a), d), e) から

この範囲内でランダムに n1 を選択すれば、再帰的に木を構築することができる。

 

なお、木構造ではなく線形に順次リストを作っていく方法も可能だが
再帰にした場合にスタック溢れが起きてしまうこと、また大きな値が前方に偏ってしまうことから採用を見送った。

  

コード

import random


def random_partition(size, total, upper):
    assert(1 <= size <= 0x0007ffff)
    assert(0 <= total <= 0x7fffffff)
    assert(0 <= upper <= 0x7fffffff)
    assert(total <= size * upper)

    if size == 1:
        return [total]

    s1 = size / 2
    s2 = size - s1
    t1 = random.randint(max(0, total - s2 * upper), min(total, s1 * upper))
    t2 = total - t1

    return random_partition(s1, t1, upper) + random_partition(s2, t2, upper)
    • 実行例
print(random_partition(1, 0, 0))
print(random_partition(1, 1, 1))
print(random_partition(10, 1000, 100))
print(random_partition(10, 1, 1))
print(random_partition(7, 10, 10000))
print(random_partition(0x0007ffff, 0x7fffffff, 0x7fffffff)[:10])
print(random_partition(0x0007ffff, 0x7fffffff, 0x7fffffff)[-10:])
print(random_partition(0x0007ffff, 0, 0)[:10])
print(random_partition(10000, 1000000000, 100000)[:10])
print(random_partition(1 << 18, 0, 1 << 12)[:10])
print(random_partition(1 << 18, 1, 1 << 12)[:10])
print(random_partition(1 << 18, 100000000, 1 << 12)[:10])
print(random_partition(1 << 18, 1000000000, 1 << 12)[:10])
print(random_partition(1 << 18, 1 << 18, 1)[:10])
print(random_partition(1 << 18, 1 << 30, 1 << 12)[:10])
    • 出力例
[0]
[1]
[100, 100, 100, 100, 100, 100, 100, 100, 100, 100]
[0, 0, 0, 0, 0, 0, 0, 1, 0, 0]
[1, 3, 3, 0, 0, 0, 3]
[16, 14, 5, 2, 5, 3, 4, 0, 1, 0]
[1, 0, 0, 1, 0, 1, 0, 1, 0, 1]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000, 100000]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[176, 546, 366, 86, 1032, 169, 28, 155, 518, 188]
[3934, 3915, 4078, 4082, 4095, 4095, 4094, 4095, 4038, 4015]
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
[4096, 4096, 4096, 4096, 4096, 4096, 4096, 4096, 4096, 4096]