editdistance: 高速に編集距離を求めるPythonパッケージ

をリリースしました。

この間書いたQiitaの記事の実装をそのままPythonのライブラリとしてまとめたものです。 Cythonでラップしてあるので高速に動作するはず。 Python2とPython3両対応です。

インストールはpipなどで。

pip install editdistance

簡単なドキュメントはリポジトリへどうぞ。

git-ticket: コマンドラインからIssueを管理する

git-ticketというツールの紹介です。

https://github.com/aflc/git-ticket

git-ticketはgitリポジトリに紐付いたチケット(Issue)の管理をターミナルから行えるgitのプラグインです。 github, bitbucket, redmineに対応しています。 スクリーンショットと簡単な使い方は上記リンク先に書いてありますので良かったら使ってみてください(英語ですが) Python製のツールなので、pipでインストールしていただく必要があります。

pip install gitticket

後々はhome直下とかに入れられるようになるといいんですが、他のライブラリに依存しているので難しいかも・・・ インストールすると、git-ticketというコマンドが使えるようになります。つまり、

git ticket <コマンド>

のようにしてgitのサブコマンドの一つとして使います。

コマンド

  • github-authorize 自分のgithubアカウントを登録します
  • bitbucket-authorize 自分のbitbucketアカウントを登録します
  • list 今いるリポジトリの最新のチケット(Issue)一覧を表示します
  • show ある一つのチケットの詳細を表示します
  • add 新しいチケットを追加します
  • update チケットの内容を更新します
  • comment チケットにコメントをします
  • close チケットをクローズします。updateコマンドのショートカットのようなものです
  • locals チケット名でローカルブランチが切られている場合、そのチケットの一覧を表示します
  • show-config git-ticketに関連する設定内容を表示します

ご意見やプルリクエスト随時募集中です。

標準ライブラリoperatorを使おう

sortの時によく使うkeyオプション。
あれをlambda式使って、

for k, v in sorted(dic.items(), key=lambda x: x[1]):
    ...

とか書いていると遅いので、operatorを使いましょうという話。

import operator
for k, v in sorted(dic.items(), key=operator.itemgetter(1)):
    ...

その他にもoperator.attrgetterやoperator.methodcallerなどがあって色々便利ですよ。
勿論標準の__add__やpowなんかもあるので、一々lambda式渡していた人はこれをやるととても速いはず。

まあこの話はpythonwikiに既出ですが。

http://wiki.python.org/moin/HowTo/Sorting/

組み込み関数idは信用できない?

2012-01-22 追記

下記現象の説明がしてありました。
http://d.hatena.ne.jp/atsuoishimoto/20110426/1303772157

どうやらinstance methodというかbound methodは、束縛されるたびに新しくオブジェクトを
生成しているので、id(a.imtd1) == id(a.imtd2)は、
1. imtd1を生成する
2. imtd1はどこにも束縛されず、すぐに消えてなくなる
3. imtd2を生成する。この時、ちょうどいい感じに空いていたidを再取得(メモリ割り当て)
4. 両者とも同じidになる

という結末のようだ。

これはコードの最適化で、頻繁に行われるメソッド呼び出しをループの外に出す
、という事がよく行われるのとも関係するのかな。
その時はメソッド呼び出しのコストを無くすためだと思ってたけど。

      • -

ある日、id関数で遊んでいたら奇妙な現象を発見した。
Python2.7の日本語ドキュメントの言語リファレンス > データモデルから引用すると、

オブジェクトが一度生成されると、そのオブジェクトの アイデンティティ値 は決して変化することがありません;
アイデンティティ値をオブジェクトのメモリ上のアドレスと考えてもかまいません。
演算子 ‘is‘ は、二つのオブジェクト間のアイデンティティ値を比較します;
関数 id() は、オブジェクトのアイデンティティ値を表す整数 (現在の実装ではオブジェクトのメモリ上のアドレス) を返します。

とされている。また、id関数の項目には、

オブジェクトの “識別値” を返します。
この値は整数 (または長整数) で、このオブジェクトの有効期間は一意かつ定数であることが保証されています。
オブジェクトの有効期間が重ならない 2 つのオブジェクトは同じ id() 値を持つかもしれません。

との事。

さて、ここからが本題。上の説明をみると、メモリのアドレス云々はともかく、オブジェクトの識別値を返すんだから

class A(object):
    def imtd1(self):
        print 'i1'
    def imtd2(self):
        print 'i2'

というクラスAのimtd1とimtd2というインスタンスメソッドは違うオブジェクトだと普通は思う。
だがしかし。この2つはidが同じなのである。

a = A()
id(a.imtd1) == id(a.imtd2)  # True

幸いなことに?isや==での比較はFalseを返す

a.imtd1 == a.imtd2 # False
a.imtd1 is a.imtd2 # False

また、辞書のキーにメソッドを指定している人がいるかもしれないが、その場合にはhashが使われるので大丈夫。

hash(a.imtd1) == hash(a.imtd2) # False

極めつけには、id関数の戻り値が"変わる"。isで比較を行ったあとにもう一度idを呼んでみると

print 'first:', id(a.imtd1)
a.imtd1 is a.imtd2
print 'second', id(a.imtd1)

試しにインタプリタで試してみて欲しい(何回か試さないとダメかも)。firstとsecondで変わっているから。
仕様なら仕様でどっかに書いておいて欲しいなあ。
という訳であまり信用出来ないid関数なのでした。

組み込み関数idは信用できない?

ある日、id関数で遊んでいたら奇妙な現象を発見した。
Python2.7の日本語ドキュメントの言語リファレンス > データモデルから引用すると、

オブジェクトが一度生成されると、そのオブジェクトの アイデンティティ値 は決して変化することがありません;
アイデンティティ値をオブジェクトのメモリ上のアドレスと考えてもかまいません。
演算子 ‘is‘ は、二つのオブジェクト間のアイデンティティ値を比較します;
関数 id() は、オブジェクトのアイデンティティ値を表す整数 (現在の実装ではオブジェクトのメモリ上のアドレス) を返します。

とされている。また、id関数の項目には、

オブジェクトの “識別値” を返します。
この値は整数 (または長整数) で、このオブジェクトの有効期間は一意かつ定数であることが保証されています。
オブジェクトの有効期間が重ならない 2 つのオブジェクトは同じ id() 値を持つかもしれません。

との事。

さて、ここからが本題。上の説明をみると、メモリのアドレス云々はともかく、オブジェクトの識別値を返すんだから

class A(object):
    def imtd1(self):
        print 'i1'
    def imtd2(self):
        print 'i2'

というクラスAのimtd1とimtd2というインスタンスメソッドは違うオブジェクトだと普通は思う。
だがしかし。この2つはidが同じなのである。

a = A()
id(a.imtd1) == id(a.imtd2)  # True

幸いなことに?isや==での比較はFalseを返す

a.imtd1 == a.imtd2 # False
a.imtd1 is a.imtd2 # False

また、辞書のキーにメソッドを指定している人がいるかもしれないが、その場合にはhashが使われるので大丈夫。

hash(a.imtd1) == hash(a.imtd2) # False

極めつけには、id関数の戻り値が"変わる"。isで比較を行ったあとにもう一度idを呼んでみると

print 'first:', id(a.imtd1)
a.imtd1 is a.imtd2
print 'second', id(a.imtd1)

試しにインタプリタで試してみて欲しい(何回か試さないとダメかも)。firstとsecondで変わっているから。
仕様なら仕様でどっかに書いておいて欲しいなあ。
という訳であまり信用出来ないid関数なのでした。

大きい二つのリストをマージする

たまに、二つのソート済みリストを大きい一つのソート済みリストにしたいときがある。

具体的にはこんな状況:

>>> a = [1, 3, 6, 8, 12]
>>> b = [2, 4, 5, 9, 10]
>>> sorted(a + b)
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]

2つのリストaとbが比較的小さいリストならいいけど、
例えばイテレータ・ジェネレータオブジェクトだったり巨大なリストだったりするときに
役に立つのがheapq。

>>> import heap

各々のリストはソートしてある必要があるけど、
2つのリストをマージしてくれる。

>>> import itertools
>>> a = itertools.takewhile(lambda x: x < 10 ** 7, (5 * x for x in itertools.count(1)))  # range(5, 10 ** 7, 5) と一緒
>>> b = itertools.takewhile(lambda x: x < 10 ** 7, (7 * x for x in itertools.count(1)))  # range(7, 10 ** 7, 7) と一緒
>>> list(itertools.islice(heapq.merge(a, b), 100))
[5, 7, 10, 14, 15, 20, 21, 25, 28, 30, 35, 35, 40, 42, 45, 49, 50, 55, 56, 60, 63, 65, 70, 70, 75, 77, 80, 84, 85, 90, 91, 95, 98, 100, 105, 105, 110, 112, 115, 119, 120, 125, 126, 130, 133, 135, 140, 140, 145, 147, 150, 154, 155, 160, 161, 165, 168, 170, 175, 175, 180, 182, 185, 189, 190, 195, 196, 200, 203, 205, 210, 210, 215, 217, 220, 224, 225, 230, 231, 235, 238, 240, 245, 245, 250, 252, 255, 259, 260, 265, 266, 270, 273, 275, 280, 280, 285, 287, 290, 294]

マージソートとかに大変役に立つ。あとは無駄にリストを作りたくない場合とか。

ついでに、groupbyを使えばuniqも同時にかけられる。

>>> list(itertools.islice((x for x, _ in itertools.groupby(heapq.merge(a, b))), 100))
[5, 7, 10, 14, 15, 20, 21, 25, 28, 30, 35, 40, 42, 45, 49, 50, 55, 56, 60, 63, 65, 70, 75, 77, 80, 84, 85, 90, 91, 95, 98, 100, 105, 110, 112, 115, 119, 120, 125, 126, 130, 133, 135, 140, 145, 147, 150, 154, 155, 160, 161, 165, 168, 170, 175, 180, 182, 185, 189, 190, 195, 196, 200, 203, 205, 210, 215, 217, 220, 224, 225, 230, 231, 235, 238, 240, 245, 250, 252, 255, 259, 260, 265, 266, 270, 273, 275, 280, 285, 287, 290, 294, 295, 300, 301, 305, 308, 310, 315, 320]

2つあった35に注目。

ということで、itertoolsも便利だなと。