エラトステネスの篩

Ruby でやってる人がいたので Python でやってみた。

cf. エラトステネスの篩 - Mae向きな日記

以前 Haskell でやったことがあるんだけどすっかり忘れててちょっと苦労したよ。
最初に書いたのはこのコード。1,000,000までの素数を列挙している。素直というか素朴というか力技。

def prime_list(n):
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        lis = [x for x in lis if x % p != 0]


primes = prime_list(1000000)

for i in primes:
    print i

ところが答えはあってるみたいだけどやたらと遅い。正確には計ってないけど4分半くらいかかる。
で、以前の Haskell のコードを見ながら改良したのがこれ。

def prime_list(n):
    limit = int(n ** 0.5) + 1
    lis = range(1, n + 1, 2)
    lis[0] = 2
    while True:
        if len(lis) == 0:
            break
        p = lis.pop(0)
        yield p
        if p <= limit:
            lis = [x for x in lis if x % p != 0]


primes = prime_list(1000000)

for i in primes:
    print i

篩にかけるのを1,000,000の二乗根までに限っている。それ以上は篩にかけても意味がないからね。これを思い出すまでに時間がかかってしまった。 で、結果はといえば劇的に速くなって約4秒程度。こんなに違うとは。

ファイルの文字数、ワード数、行数を数える

というのをやってる人がいたので、やってみた。

cf. 何とかPython版完成 - しんちゃんの日記

import sys

def count(str):
    words = str.split()
    word_cnt = len(words)
    char_cnt = len(str)
    lines = str.split("\n")
    line_cnt = len(lines)
    if lines[-1] == '':
        line_cnt -= 1
    return char_cnt, word_cnt, line_cnt

for file in sys.argv[1:]:
    content = open(file, "r").read()
    char_count, word_count, line_count = count(content)
    print "chars =", char_count, " words =", word_count, " lines =", line_count, " filename =", file

実行:

^o^ > mywc.py mywc.py
chars = 466  words = 59  lines = 19  filename = mywc.py

wcコマンドと比べてみる。

^o^ > wc mywc.py
 19  59 485 mywc.py

なんか文字数が違うな。ちょうど行数の分だけ違う、ってことは改行文字のせいか?
ためしに mywc.py の改行をCR+LFからLFだけに変えてみと:

^o^ > wc mywc.py
 19  59 466 mywc.py

文字数も合った。wcコマンドはCR+LFを2文字と数えて、(少なくともWindowsの)Pythonは1文字と数えるみたいだ。

正規表現をつかう

Python の正規表現は Ruby や Perl のように組み込みではなくて、reモジュールとして提供されている。使い方は2通りあって、ひとつはreモジュールの関数を使うやり方、もうひとつはre.compile関数で正規表現オブジェクトを作って使うやり方だ。

reモジュールの関数を使う

ここでは関数を使うやり方を試してみよう。

re.findall は文字列中で正規表現にマッチする部分すべてをリストとして返す。

>>> re.findall("a.", "abcacbcba")
['ab', 'ac']

re.split は文字列を分割する。

>>> re.split("b", "abcacbcba")
['a', 'cac', 'c', 'a']

re.sub は正規表現にマッチする部分を置き換える。

>>> re.sub("a", "A", "abcacbcba")
'AbcAcbcbA'

re.search は文字列中にマッチする部分を見つけて、マッチオブジェクトを返す。最初に見つかって部分しか返ってこないみたい。

>>> m = re.search("b.", "abcacbcba")
>>> m.group()
'bc'

re.match は re.serch と同様だけど、文字列の先頭だけを対象とする。マッチオブジェクトを返す。

>>> m = re.match("a.", "abcacbcba")
>>> m.group()
'ab'

先頭にマッチしない場合は m.group() がエラーになる。

>>> m = re.match("b.", "abcacbcba")
>>> m.group()
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: 'NoneType' object has no attribute 'group'

re.finditer はマッチオブジェクトを返すイテレータを返す。

>>> for m in re.finditer("a.", "abcacbcba"):
...     print m.group()
...
ab
ac

正規表現オブジェクトを使う

同じ正規表現を何度も使う場合は、正規表現オブジェクトを作ったほうが速度的に有利みたい。正規表現オブジェクトを作るには re.compile 関数を使う。

>>> r = re.compile("a.")
>>> r.findall("abcacbcba")
['ab', 'ac']

r が正規表現オブジェクト。正規表現オブジェクトには reモジュールの関数と同じ動作をするメソッドがあって、使い方も同じ(引数に正規表現パターンがない以外は)。

マッチオブジェクト

search や match はマッチオブジェクトを返す。マッチオブジェクトには、マッチした文字列やサブグループの情報が保存されている。

>>> r = re.compile("a(..)a(..)")
>>> m = r.match("abcacbcba")
>>> m.groups()
('bc', 'cb')
>>> m.group()
'abcacb'
>>> m.group(0)
'abcacb'
>>> m.group(1)
'bc'
>>> m.group(2)
'cb'

これはたぶん後方参照やなんかに使えるんだろう。

MD5ハッシュを計算する

今回は小ネタ。md5モジュールを使って MD5ハッシュを計算する。

import md5
import sys

file = sys.argv[1]
content = open(file, "rb").read()

m = md5.new(content)
print m.hexdigest()

実行例:

^o^ > python mkmd5.py sample.txt
26b2953c0dd7a8b6052c8f76385ee5c4

以前 Ruby で作ったスクリプトでチェックしてみる。

^o^ > python mkmd5.py sample.txt > sample.txt.md5

^o^ > type sample.txt.md5
26b2953c0dd7a8b6052c8f76385ee5c4

^o^ > chkmd5.rb sample.txt.md5
valid:      sample.txt

OKみたいだ。

CSVファイルを読み書きする

CSVファイルの読み込み

CSVファイルを読み書きするには csv モジュールを使う。

csv.reader関数は、CSVファイルを読み込むオブジェクトを返す。これを使って1行ずつ処理するわけだ。次の例は、名前とメールアドレスからなるCSVファイルを読み込んで、変換して出力する。

import csv

csvfile = open("mail.csv", "r")
reader = csv.reader(csvfile)
for row in reader:
    print '"%s" <%s>' % (row[0], row[1])

実行:

^o^ > type mail.csv
Andy,[email protected]
Bill,[email protected]
Charlie,[email protected]

^o^ > python csv_read.py
"Andy" <[email protected]>
"Bill" <[email protected]>
"Charlie" <[email protected]>

CSVファイルの書き込み

csv.reader があれば csv.writer もある。csv.writer関数は、CSVファイルに書き込むオブジェクトを返す。そして writerowメソッドで1行ずつ書き込むって感じだ。

import csv

data = [("Andy", "[email protected]"),
        ("Bill", "[email protected]"),
        ("Charlie", "[email protected]")]

csvfile = open("sample.csv", "wb")
writer = csv.writer(csvfile)
for d in data:
    writer.writerow(d)

上の例では書き込むデータとしてタプルのリストを用意しているけど、リストのリストでもいいらしい。注意点としては、書き込み用ファイルをopenするときにバイナリモード “wb” で開くこと。そうでないと余計な改行が出力されてしまう。
実行:

^o^ > python csv_write.py

^o^ > type sample.csv
Andy,[email protected]
Bill,[email protected]
Charlie,[email protected]

その他細かいことは省略

実はCSVファイルには標準というものがない。値がクオートしてあるとかないとか、そういう細かい違いがソフトごとにある。そういう違いを吸収するために、csv.reader や csv.writer には dialect とかその他のパラメータがあるんだけど、ここでは省略する。
詳しい情報はこのあたり。

cf. http://docs.python.jp/2.7/library/csv.html

とりあえず Excel 互換の CSV なら上の例のような簡単な書き方で大丈夫みたいだ。

例外処理

例外の捕捉

たとえば、存在しないファイルを読み込もうとするとエラー(例外)が発生する。

import sys

file = sys.argv[1]

content = open(file, "r").read()
size = len(content)
print file + ": " + str(size)
^o^ > python exception1.py sample.dat
Traceback (most recent call last):
  File "exception1.py", line 5, in 
    content = open(file, "r").read()
IOError: [Errno 2] No such file or directory: 'sample.dat'

上の例では sample.dat を読み込もうとしているが、存在しないファイルなので IOError が発生してプログラムが終了している。
ここでプログラムが終了しないようにするには、try ~ except 文を使って例外を適切に処理してやればいい。

import sys

file = sys.argv[1]

try:
    content = open(file, "r").read()
    size = len(content)
    print file + ": " + str(size)
except IOError:
    print "Cannot open file: " + file

例外が発生するかもしれない処理をtry節に書き、発生した例外はexcept節で捕捉する。こうすると例外が発生したときの処理を書くことができる。この例では単純にメッセージを出力して終わっているだけだけど。
実行結果:

^o^ > python exception2.py sample.dat
Cannot open file: sample.dat

except節の処理が実行されているのがわかる。

例外の発生

何らかの理由で例外を発生させたい場合には、raise 文を使う。一番単純な使い方としては 「raise メッセージ」とすればいい。

try:
    raise "Someting error."
except:
    print "Error occured."
^o^ > python exception3.py
Error occured.

この場合、発生する例外は StandardError みたい。特定の種類の例外を発生するには「raise 例外の種類(メッセージ)」という形式にする。

クラス (3)新スタイルクラス

__slots__

Python のクラスには旧スタイルクラスと新スタイルクラスがあるらしい。ややこしいな。
新スタイルクラスを作るには、ビルトイン型を継承するか、もしくは最上位のクラスであるobjectを継承する。

class Person(object):

    __slots__ = ["name", "age"]

    def __init__(self, name, age):
        self.name = name
        self.age = age

    def greeting(self):
        print "Hello, I'm " + self.name + "!"

新スタイルクラスの機能の一つとして、__slots__によってアクセスできるアトリビュートを制限できるというのがある。上の例では、アクセス可能なアトリビュートを name と age に制限している。これで勝手なアトリビュートを追加したりはできなくなったはずだ。やってみよう。

>>> from person2 import Person
>>> andy = Person("Andy", 32)
>>> andy.name
'Andy'
>>> andy.age
32
>>> andy.job = "programmer"
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: 'Person' object has no attribute 'job'

__slots__ で指定している name と age にはアクセスできるけど、job に代入しようとしたら ‘job’なんてアトリビュート無いよ、と怒られた。

プロパティ

ただし、まだ name と age には値を代入できてしまう。

>>> andy.name = "Bill"
>>> andy.name
'Bill'

名前は変わらないのだから、参照はできても代入はできてほしくない。こういうときはプロパティにすればいいらしい。

class Person(object):

    __slots__ = ["_name", "age"]

    def __init__(self, name, age):
        self._name = name
        self.age = age

    def greeting(self):
        print "Hello, I'm " + self._name + "!"

    def get_name(self):
        return self._name

name = property(get_name, None)

名前用のアトリビュートを _name に変更して、参照用の get_name メソッドを作った。そしてproperty関数を使ってnameというアクセサを作っている。property関数の引数にはゲッター、セッターのメソッド指定する。セッターとしては None を指定しているから、これで name は参照だけできるようになったはずだ。

>>> from person2a import Person
>>> andy = Person("Andy", 32)
>>> andy.name
'Andy'
>>> andy.name = "Bill"
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: can't set attribute

name に代入しようとしたら、アトリビュートをセットできない、といわれた。うまくいってるようだ。

でもまてよ。_name アトリビュートにはアクセスできるはずだから、代入もできてしまうんじゃないか?

>>> andy._name = "Bill"
>>> andy.name
'Bill'

できちゃうじゃん。だめじゃん。
じゃあ、__slots__ から _name を取り去ったらどうだ。

class Person(object):

    __slots__ = ["age"]

    def __init__(self, name, age):
        self._name = name
        self.age = age

    def greeting(self):
        print "Hello, I'm " + self._name + "!"

    def get_name(self):
        return self._name

name = property(get_name, None)
>>> from person2b import Person
>>> andy = Person("Andy", 32)
Traceback (most recent call last):
  File "", line 1, in 
  File "person2b.py", line 6, in __init__
    self._name = name
AttributeError: 'Person' object has no attribute '_name'

だめだ。今度は _name アトリビュートがないって怒られた。どうすりゃいいんだ。

クラス (2)継承

クラスの継承

Python ではクラスの継承に多重継承ができる。クラスを継承するには、class 文のクラス名のあとの括弧の中に継承したいクラス名を列挙すればいい。

class Foo:
    def foo(self):
        print "This is foo."

class Bar:
    def bar(self):
        print "This is bar."

class Baz(Foo, Bar):
    def baz(self):
        print "This is baz."

if __name__ == '__main__':
    baz = Baz()
    baz.foo()
    baz.bar()
    baz.baz()

BazクラスはFooクラスとBarクラスを継承していて、加えて独自のメソッドbarを持っている。
これを実行すると:

^o^ > python inheritance.py
This is foo.
This is bar.
This is baz.

FooクラスとBarクラスそれぞれのメソッドが使えることがわかる。

メソッドのオーバーライド

次に、Bazクラスでbarメソッドを書き換え(オーバーライド)てみる。

class Foo:
    def foo(self):
        print "This is foo."

class Bar:
    def bar(self):
        print "This is bar."

class Baz(Foo, Bar):
    def baz(self):
        print "This is baz."

    def bar(self):
        print "This is baz, instead bar."

if __name__ == '__main__':
    baz = Baz()
    baz.foo()
    baz.bar()
    baz.baz()

実行結果:

^o^ > python inheritance2.py
This is foo.
This is baz, instead bar.
This is baz.

barメソッドが書き換わっている。こんな風に、継承したクラス(サブクラス)で継承もとのクラス(スーパークラス)のメソッドをオーバーライドすることができる。

メソッド名の衝突と継承の順番

ところで、多重継承するとメソッド名が衝突することが考えられる。つまり2つのスーパークラスそれぞれに同じ名前のメソッドが定義されていた場合だ。ちょっと試してみよう。

class Foo:
    def hello(self):
        print "Hello, this is Foo."

class Bar:
    def hello(self):
        print "Hello, this is Bar."

class Baz(Foo, Bar):
    pass

if __name__ == '__main__':
    baz = Baz()
    baz.hello()

二つのスーパークラスFooとBarには同じ名前のhelloメソッドがあって、サブクラスBazから呼び出している。実行すると:

^o^ > python inheritance3.py
Hello, this is Foo.

Fooクラスのメソッドが実行された。これはクラスを継承するときにFooを先に書いたせい、なのか?ためしにFooとBarを逆にしてみよう。

class Foo:
    def hello(self):
        print "Hello, this is Foo."

class Bar:
    def hello(self):
        print "Hello, this is Bar."

class Baz(Bar, Foo):
    pass

if __name__ == '__main__':
    baz = Baz()
    baz.hello()

さっきと変わっているのは11行目だけだ。スーパークラスの指定にBarを先に書いている。これを実行すると:

^o^ > python inheritance3a.py
Hello, this is Bar.

今度はBarクラスのメソッドが実行された。スーパークラスでメソッド名が衝突している場合、サブクラスでどちらが呼び出されるのかは、継承するときに列挙した順番によるみたいだ。

クラス

クラスの定義とインスタンスの作成

クラスを定義するには、class 文を使う。もちろん定義の中身はインデントされたブロックになっている。

class Person:
    def __init__(self, name):
        self.name = name

    def greeting(self):
        print "Hello, I'm " + self.name + "!"

if __name__ == '__main__':
    andy = Person("Andy")
    andy.greeting()
    print andy.name

__init__ は特殊メソッドのひとつで、インスタンスの初期化に使われる。Ruby の initialize みたいなもんだな。ここでは name アトリビュート(インスタンス変数みたいなもの)を設定している。
メソッドはもうひとつ、greeting を定義してみた。それにしても、いちいち self を引数に含めなきゃいけないのは面倒だよなぁ。

インスタンスの作成は、クラス名を関数のように呼び出して行う。new とかはない。

実行結果:

^o^ > python person.py
Hello, I'm Andy!
Andy

1行目の出力が greeting メソッドを呼び出した結果で、2行目の出力が name アトリビュートにアクセスした結果だ。

アトリビュートの追加

アトリビュートは Ruby インスタンス変数と違って勝手に新しいものを追加できる。やってみよう。

>>> from person import Person
>>> andy = Person("Andy")
>>> andy.age
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: Person instance has no attribute 'age'
>>> andy.age = 32
>>> andy.age
32

andy.age に代入する前の段階では、アクセスしてもエラー(’age’なんてアトリビュート無いよ)が出ているが、いったん代入すると、今度は代入した値が返ってくる。これは、インスタンスにアトリビュートを追加したのであって、クラスに追加したのではないことに注意。その証拠に別のインスタンスを作ってみても age アトリビュートはない。

>>> bill = Person("Bill")
>>> bill.age
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: Person instance has no attribute 'age'

クラスの定義にないアトリビュートをインスタンスに追加できるというのは面白い。

インスタンスにメソッドを代入する

インスタンスに代入できるのはアトリビュートだけじゃない。メソッドだって代入できる。

>>> andy.hello()
Traceback (most recent call last):
  File "", line 1, in 
AttributeError: Person instance has no attribute 'hello'
>>> andy.hello = andy.greeting
>>> andy.hello()
Hello, I'm Andy!

これってどうなんだよ。さすがに違和感があるぞ。もしかして bill に andy のメソッドを代入もできるのか?

>>> bill.hello = andy.hello
>>> bill.hello()
Hello, I'm Andy!

できた。うわぁ、これは気持ちが悪い。
なんか妙に自由度が高すぎるように思うなぁ。

dir関数

dir 関数を使うとインスタンスの持っているアトリビュートの一覧を得ることができる。

>>> dir(andy)
['__doc__', '__init__', '__module__', 'age', 'greeting', 'hello', 'name']

これをみると、アトリビュート(name、age)とメソッド(greeting、hello)が一緒に並んでいる。要するに Python ではメソッドもアトリビュートの一種ってことらしい。だから代入ができるのも道理ってわけだ。

ジェネレータ

ジェネレータはイテレータオブジェクトを返す関数だ。def を使って通常の関数と同じように定義できるけど、ひとつ違うのは return で値を返す代わりに、yield で計算途中の値を返すことができる点。ジェネレータから返されたイテレータオブジェクトは、nextが呼び出されると yield が出てくるまで計算を進めて値を返す。そしてまたnextが呼び出されると、続きの計算をして yield が出てきた時点でまた値を返す。これを繰り返すわけだ。だから、ジェネレータでは while ループの中で yield を使うのが常套手段、というかそうしないとうまく作れないんじゃないかな。

次の例はフィボナッチ数列を出力する。

def fib():
    a = 1
    b = 1
    while True:
        yield a
        a, b = b, a+b


i = fib()

for c in range(10):
    print i.next()

実行結果:

^o^ > python fib.py
1
1
2
3
5
8
13
21
34
55

うまくいった。この例では10個までしか出力してないけど、コードをよく見ればわかるとおり、終了しない無限ループになっている。言い換えると無限に値を生成できるってこと。これはリストやファイルオブジェクトから作るイテレータとは違うところだ。