銀月の符号

Python 使い見習いの日記・雑記

素因数分解

Python

割り切れるかどうか試してみる、という力業の方法で。

http://tsumuji.cocolog-nifty.com/tsumuji/2009/05/post-af3f.html を参考に作成。素因数分解は素数で割ってみることでできる。しかし、素数を求めることそのものに時間がかかるため単に 2 と 3 以上の奇数で割ってみてしまったほうが早い、そして 2, 3 と 6 * n ± 1 (n は 1 以上の整数）で割ったほうがさらに早い、という内容。

factorize.py

# coding: utf-8

u"""素因数分解"""

import itertools

def _ifactorize_p():
    u"""2, 3, および素数の可能性がある奇数 p = 6 * n ± 1"""

    yield 2
    yield 3
    num = 1
    for add in itertools.cycle((4, 2)):
        num += add
        yield num

def ifactorize(num):
    u"""素因数分解
    
    素因数を小さい順に一つずつ返すイテレータ。"""

    num = int(num)
    if num < 1:
        raise ValueError(u'%d is not positive number' % num)
    elif num == 1:
        yield 1
        return

    for fact in _ifactorize_p():
        if num < fact ** 2:
            if num > 1:
                yield num
            break
        q, r = divmod(num, fact)
        while not r:
            num = q
            yield fact
            q, r = divmod(num, fact)

def factorize(num):
    u"""素因数分解
    
    素因数をまとめた tuple を返す
    
    >>> factorize(360)
    (2, 2, 2, 3, 3, 5)
    """

    return tuple(ifactorize(num))

def ifactorize_groupby(num):
    u"""素因数分解
    
    素因数とこれが含まれる数の組を順次返すイテレータ。"""

    for prime, g in itertools.groupby(ifactorize(num)):
        #c = 0
        for c, _ in enumerate(g, 1):
            pass
        yield prime, c

def factorize_groupby(num):
    u"""素因数分解
    
    素因数とこれが含まれる数の組をまとめたタプルを返す。
    
    >>> factorize_groupby(360)
    ((2, 3), (3, 2), (5, 1))
    """

    return tuple(ifactorize_groupby(num))

def main():
    import os
    import sys
    from optparse import OptionParser

    usage = '%prog integer_number [...]\nex: %prog 360'
    parser = OptionParser(usage=usage)
    parser.add_option('-g', '--groupby',
            action='store_true', dest='groupby')
    parser.set_defaults(groupby=False)
    options, args = parser.parse_args()

    if len(args) < 1:
        parser.print_help()
        parser.exit()

    f = factorize_groupby if options.groupby else factorize
    for arg in args:
        try:
            num = int(arg, 10)
            print '%d: %s' % (num, f(num))
        except ValueError, e:
            print e

if __name__ == '__main__':
    main()

実行結果

>factorize.py 360
360: (2, 2, 2, 3, 3, 5)

>factorize.py --groupby 360
360: ((2, 3), (3, 2), (5, 1))

素数列の生成3

Python

素数列の生成2 - 銀月の符号 を微修正。3 以上の奇数の生成方法を itertools.islice(itertools.count(3), 0, None, 2) に変更。うちの実行環境 CPython 2.6.4 on Win32 ではこちらのほうが早かった。 CPython 全般でこちらのほうが早いと予想しているが Jython, IronPython でどうかは見当つかず。あと CPython でも長整数の領域に入ったとき、遅いような気がするが、未確認。

prime.py

# coding: utf-8

u"""素数列の生成 - 遅延評価によるエラトステネスの篩
"""

import itertools

def prime_numbers():
    u"""素数列"""

    yield 2
    odds = itertools.islice(itertools.count(3), 0, None, 2)
    sequences = {4: 2}
    sequences_pop = sequences.pop
    for i in odds:
        d = sequences_pop(i, None)
        if d is None:
            yield i
            i, d = i ** 2, i * 2
        else:
            i += d
            while i in sequences:
                i += d
        sequences[i] = d

def main():
    import sys
    from itertools import takewhile

    max_ = int(sys.argv[1]) if len(sys.argv) > 1 else 30
    for i, prime in enumerate(
            takewhile(lambda x: x < max_, prime_numbers())):
        print i, prime

if __name__ == '__main__':
    main()

実行結果

>prime.py 30
0 2
1 3
2 5
3 7
4 11
5 13
6 17
7 19
8 23
9 29

N 個の組

Python

L[0:2], L[1:3], L[2:4] …のような値を返すイテレータについてのメモ。ほぼ itertools ライブラリドキュメントのレシピ のまま。

L[0:2], L[1:3], L[2:4] … のようなイテレータ

レシピにそのものが載っていたので転載。

from itertools import *

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

L[0:n], L[1:n+1], L[2:n+2] … のようなイテレータ

さきほどの pairwise と consume, repeatfunc というレシピらを参考に作成してみた。

今、疑問に思っている点は値の読み捨てに for 文、 for _ in xrange(n): next(it) ではなく collections.deque を使う理由について。こちらのほうが早いのだろうか？ CPython の collections.deque は C 実装なので for 文より早い、とか？ 後でベンチとってみようっと。

import itertools
import collections

def setwise(iterable, n=2):
    "s -> (s0,s1, ...), (s1,s2,...), (s2,s3,...), ..."
    its = itertools.tee(iterable, n)
    for i, it in enumerate(its):
        collections.deque(
                itertools.imap(next, itertools.repeat(it, i)),
                maxlen=0)
    return itertools.izip(*its)
使用例、連続する値を見つける

setwise を用いて整数値イテレータブルから、連続する値を見つけてみる。 itertools.ifilter 併用。

>>> from itertools import ifilter, izip, count, starmap
>>> from operator import eq
>>> def is_consecutive_numbers(nums):
...   it = iter(nums)
...   num = next(it)
...   return all(starmap(eq, izip(it, count(num + 1))))
...
>>> data = [1,  4,5,  9,10,11,  16,17,18,19]
>>> for n in ifilter(is_consecutive_numbers, setwise(data, 2)):
...   print n
...
(4, 5)
(9, 10)
(10, 11)
(16, 17)
(17, 18)
(18, 19)
>>> for n in ifilter(is_consecutive_numbers, setwise(data, 3)):
...   print n
...
(9, 10, 11)
(16, 17, 18)
(17, 18, 19)

別解、 itertools.groupby 併用。

>>> from itertools import groupby, imap
>>> from operator import itemgetter
>>> data = [1,  4,5,  9,10,11,  16,17,18,19]
>>> for k, g in groupby(enumerate(data), lambda (i,x):i-x):
...   for n in setwise(imap(itemgetter(1), g), 2):
...     print n
...
(4, 5)
(9, 10)
(10, 11)
(16, 17)
(17, 18)
(18, 19)
>>> for k, g in groupby(enumerate(data), lambda (i,x):i-x):
...   for n in setwise(imap(itemgetter(1), g), 3):
...     print n
...
(9, 10, 11)
(16, 17, 18)
(17, 18, 19)

L[n*0:n*1], L[n*1:n*2], L[n*2:n*3] … のようなイテレータ

これも載っているので、ついでに転載。

from itertools import *

def grouper(n, iterable, fillvalue=None):
    "grouper(3, 'ABCDEFG', 'x') --> ABC DEF Gxx"
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

gettext モジュールメモ

Python

Python gettext モジュールと戯れる。多言語対応 Python アプリを作るためのモジュール。しかし、オレには日本語以外まともに使える語がない罠。いや、日本語も怪しいけれど。

前提

次のコードを hello.py とする。実行すると「Hello」と挨拶するだけのスクリプト。これをいろんな語の挨拶に代えられるようにしたい、とする。たとえば日本語環境だと「こんにちは」。

# coding: utf-8

def main():
    print u'Hello'

if __name__ == '__main__':
    main()

手順1、マーキング

翻訳対象となる語を _ でマーキングする。次のようになる。

# coding: utf-8

def main():
    print _(u'Hello')

if __name__ == '__main__':
    main()

しかし、この段階で実行すると、 _ ってなに？ というエラーが起こる。

>python hello.py
Traceback (most recent call last):
  File "hello.py", line 7, in <module>
    main()
  File "hello.py", line 4, in main
    print _(u'Hello')
NameError: global name '_' is not defined

手順2、 _ をインストール

_ に文字列を置き換えてくれるなんらかの呼び出し可能オブジェクトを対応付ける。ひとつの方法は gettext.translation 関数で得られた「翻訳オブジェクト」の ugettext メソッドを _ とすること。その他の方法については http://pythonjp.sourceforge.jp/dev/library/gettext.html#id3 参照。

# coding: utf-8

import os
import gettext

_ = gettext.translation(
        domain='hello',
        localedir=os.path.join(os.path.dirname(__file__), 'locale'),
        fallback=True).ugettext

def main():
    print _(u'Hello')

if __name__ == '__main__':
    main()

translation 関数の引数の内容はこう。

domain
.mo ファイルの名前
localedir
.mo ファイルの置き場所（省略可能）
fallback
.mo ファイルが見つからなかったとき、翻訳せずに続行するかどうか（デフォルトは False で例外が発生する。 True だとなにもしない NullTranslations オブジェクトが返る。 NullObject パターン。）

この段階で実行すると、まだ翻訳を収めた .mo ファイルが作成されていないため、そのまま Hello と表示される。

>python hello.py
Hello

手順3、.pot ファイルの作成

翻訳対象となる語をまとめた .pot ファイルを作成する。これには pygettext.py スクリプトを用いる。 Windows 版 Python 2.6.4 には入ってなかったのでソースの Tools\i18n から持ってきた。 pygettext.py hello.py とすると次のような messages.pot ができあがる。

# SOME DESCRIPTIVE TITLE.
# Copyright (C) YEAR ORGANIZATION
# FIRST AUTHOR <EMAIL@ADDRESS>, YEAR.
#
msgid ""
msgstr ""
"Project-Id-Version: PACKAGE VERSION\n"
"POT-Creation-Date: 2010-03-19 21:34+東京 (標準時)\n"
"PO-Revision-Date: YEAR-MO-DA HO:MI+ZONE\n"
"Last-Translator: FULL NAME <EMAIL@ADDRESS>\n"
"Language-Team: LANGUAGE <LL@li.org>\n"
"MIME-Version: 1.0\n"
"Content-Type: text/plain; charset=CHARSET\n"
"Content-Transfer-Encoding: ENCODING\n"
"Generated-By: pygettext.py 1.5\n"


#: hello.py:12
msgid "Hello"
msgstr ""

次の .po ファイル作成は翻訳担当者の作業。

手順4、.po ファイルの作成

.po ファイルを作成する。まずは先ほどの messages.pot をコピーして hello.po という名のファイルを作る。そして翻訳作業に入る。たとえばこんな感じ。

# Hello
# Copyright (C) 2010 fgshun
# fgshun <fgshun.lazy-moon.jp>, 2010.
#
msgid ""
msgstr ""
"Project-Id-Version: 0.1\n"
"POT-Creation-Date: 2010-03-19 19:44+JST\n"
"PO-Revision-Date: 2010-03-19 19:57+JST\n"
"Last-Translator: fgshun <fgshun@lazy-moon.jp>\n"
"Language-Team: \n"
"MIME-Version: 1.0\n"
"Content-Type: text/plain; charset=UTF-8\n"
"Content-Transfer-Encoding: 8bit\n"
"Generated-By: pygettext.py 1.5\n"


#: hello.py:12
msgid "Hello"
msgstr "こんにちは"

.po ファイルのヘッダ部分については http://www.gnu.org/software/gettext/manual/gettext.html#Header-Entry 参照。

なお、 .po ファイルを編集するエディタもあるみたい。 poedit など。

手順5、.mo ファイルの作成

hello.po が出来上がったら、これを元に hello.mo ファイルを作ることができる。変換には msgfmt.py スクリプトを用いる。 msgfmt.py も Windows 版にはないので pygettext.py 同様に用意。 msgfmt.py hello.po とすると hello.mo ファイルができる。

次の .mo ファイルの設置はユーザーもしくはインストーラー作成者の作業。

手順6、.mo ファイルの設置

hello.mo ファイルを gettext が読める位置におく。日本語用 .mo は ja\LC_MESSAGES\hello.mo という階層におくべし。

完成

以上で終了。早速日本語で挨拶させてみる。

>python hello.py
こんにちは

md5sum の模倣

Python

Python で md5sum 。車輪の再発明遊び、兼 C コードリーディング。参考にしたのは GNU coreutils-8.4.tar.gz の md5sum.c 。

先日の「md5 のチェックを Python で - 銀月の符号」なんかと違って、ちゃんと各種オプションもある。

得られたもの

  • optparse モジュールのコールバックオプションの使い方
  • （作成過程における）自己満足（完成品に需要がないのは明らか。先日のは即席でもつくれそうなほど簡単なところがメリットになりえたが、これは無理。）

TODO

  • テスト（これはひどい。予定に入っていちゃだめだろ、終わってないと）
  • docstring, コメント（同上）
  • stdin からの入力

以下着手するかどうか未定。

  • リファクタリング（読みやすいコード、テストしやすいコードに。元コードの構造に引きずられて、 Python らしからぬ状態になっているのかも。）
  • 複数のアルゴリズムへの対応（md5sum.c は、これひとつで md5sum, sha1sum, sha256sum, sha224sum, sha512sum, sha384sum のビルドができるようだ。プリプロセッサで振り分けている。 Python 流だとどう料理すべきか？）
  • 多言語対応のための下地作り（たしか _("standard input") の _ は gettext というものだったような。詳しく知らないけれど実行環境のロケールに合った .mo ファイルをもとに一部の表示用テキストを置き換えるものだったっけ。 Python にも gettext モジュールがあることだし、これの使い方の勉強もできる？）

md5sum.py

# coding: utf-8

u"""GNU md5sum の模倣
"""

import sys
import re
import hashlib
import optparse

def split3(line):
    mo = re.match(r'([a-fA-F0-9]{32}) ([ \*])(.*)', line)
    if not mo:
        return None
    digest, is_bin, name = mo.groups()
    if u'\\' in name:
        L = []
        append = L.append
        it = iter(name)
        for c in it:
            if c != u'\\':
                append(c)
            else:
                try:
                    c = next(it)
                except StopIteration:
                    return None
                if c == u'\\':
                    append(u'\\')
                elif c == u'n':
                    append(u'\n')
                else:
                    return None
        name = u''.join(L)
    return digest, is_bin, name

def digest_stream(f, buf_size=2097152):
    ha = hashlib.md5()
    while True:
        data = f.read(buf_size)
        if not data:
            break
        ha.update(data)
    return ha

def digest_file(filename, binary):
    is_stdin = filename == '-'

    if is_stdin:
        # TODO: 標準入力からの入力をなんとかする
        raise Exception(u'Reading from stdin is not supported yet.')
    else:
        with open(filename, 'rb' if binary else 'r') as f:
            ha = digest_stream(f)
        return ha

def digest_check(filename, warn=False):
    is_stdin = filename == '-'

    if is_stdin:
        # TODO: 標準入力からの入力をなんとかする
        raise Exception(u'Reading from stdin is not supported yet.')
    else:
        with open(filename, 'r') as f:
            for line_number, line in enumerate(f, 1):
                if line[0] == '#':
                    continue
                if line[-1] == '\n':
                    line = line[:-1]
                try:
                    digest, is_bin, name = split3(line)
                except TypeError:
                    if warn:
                        print >> sys.stderr, u'%s: %d: improperly formatted MD5 checksum line' % (filename, line_number)
                    continue

                mode = 'rb' if is_bin == '*' else 'r'
                try:
                    with open(name, mode) as g:
                        he = digest_stream(g)
                    result = digest.lower() == he.hexdigest().lower()
                    result_s = u'OK' if result else u'FAILED'
                except IOError, e:
                    print >> sys.stderr, e
                    result = False
                    result_s = u'FAILED open or read'
                yield name, result, result_s

usage = '''%prog [OPTION]... [FILE]...
Print or check MD5(128-bit) checksums.
With no File, or when FILE is -, read standard input.'''

# TODO: version および説明文を考え直すこと
version = '''%prog 0.1
Written by fgshun'''

def status_callback(option, opt, value, parser, *args, **kwargs):
    parser.values.status_only = True
    parser.values.warn = False
    parser.values.quiet = True

def quiet_callback(option, opt, value, parser, *args, **kwargs):
    parser.values.status_only = False
    parser.values.warn = False
    parser.values.quiet = True

def warn_callback(option, opt, value, parser, *args, **kwargs):
    parser.values.status_only = False
    parser.values.warn = True
    parser.values.quiet = False

def main():
    parser = optparse.OptionParser(usage=usage, version=version)
    parser.add_option('-b', '--binary',
            action='store_true', dest='binary',
            help='read in binary mode')
    parser.add_option('-c', '--check',
            action='store_true', dest='do_check',
            help='read MD5 sums from the FILEs and check them')
    parser.add_option('-t', '--text',
            action='store_false', dest='binary',
            help='read in text mode (default)')
    parser.add_option('--quiet',
            action='callback', callback=quiet_callback,
            help="don't print OK for each successfully verified file")
    parser.add_option('--status',
            action='callback', callback=status_callback,
            help="don't output anything, status code shows success")
    parser.add_option('-w', '--warn',
            action='callback', callback=warn_callback,
            help='warn about improperly formatted checksum lines')
    parser.set_defaults(
            binary=None,
            do_check=False,
            status_only=False,
            warn=False,
            quiet=False)

    options, args = parser.parse_args()

    if options.binary is not None and options.do_check:
        parser.error('the --binary and --text options are meaningless when'
                     'verifying checksums')
    if options.status_only and not options.do_check:
        parser.error('the --status option is meaningful only'
                     'when verifying checksums')
    if options.warn and not options.do_check:
        parser.error('the --warn option is meaningful only'
                     'when verifying checksums')
    if options.quiet and not options.do_check:
        parser.error('the --quiet option is meaningful only'
                     'when verifying checksums')

    if not args:
        args.append('-')

    ok = True

    if options.do_check:
        lines = 0
        computed = 0
        failures = 0
        mismatched = 0
        for arg in args:
            for name, result, result_s in digest_check(arg, options.warn):
                lines += 1
                if result:
                    computed += 1
                else:
                    if result_s == u'FAILED':
                        computed += 1
                        mismatched += 1
                    elif result_s == u'FAILED open or read':
                        failures += 1
                    else:
                        assert True
                    ok = False
                if not (options.status_only or (result and options.quiet)):
                    print u'%s: %s' % (name, result_s)
        if failures and not options.status_only:
            print >> sys.stderr, 'WARNING: %d of %d listed files could not be read' % (failures, lines)
        if mismatched and not options.status_only:
            print >> sys.stderr, 'WARNING: %d of %d computed checksums did Not match' % (mismatched, computed)
    else:
        for arg in args:
            try:
                ha = digest_file(arg, options.binary)
                digest = ha.hexdigest()
                parg = arg.replace(u'\\', u'\\\\')
                parg = parg.replace(u'\n', u'\\n')
                print u'%s %c%s' % (
                        digest, u'*' if options.binary else u' ', parg)
            except IOError, e:
                print >> sys.stderr, e
                ok = False

    sys.exit(0 if ok else 1)

if __name__ == '__main__':
    main()

md5 のチェックを Python で

Python

md5sum なんて入ってないけれども Python (2.5 以上の 2系)ならある、という奇特なパソコンで役に立つかもしれないスクリプト。 md5sum -b spam.txt っぽい動作をする。 -t や -c 相当の動作はない。引数なし時や - 指定時に標準入力から読むという動作もない。

import sys
import hashlib

def md5hexdigest(path):
    ha = hashlib.md5()
    with open(path, 'rb') as f:
        while True:
            data = f.read(8192)
            if not data:
                break
            ha.update(data)
    return ha.hexdigest()

def main():
    import sys
    for arg in sys.argv[1:]:
        try:
            md5digest = md5hexdigest(arg)
            print u'%s *%s' % (arg, md5digest)
        except IOError, e:
            print >> sys.stderr, e

if __name__ == '__main__':
    main()

追記、ソースの Tools/scripts に md5sum.py というスクリプトが存在する。上記コードよりも高度。しかし、ちょっと古い(2003年製。 md5, getopt モジュール使用）。あと、 -c オプションはない。

Ubuntu インストール失敗、と騒ぐ前に md5 チェックくらいしようぜ、オレ

日記

Windows の Virtual Box 3.1.4 に Ubuntu 9.10 (Ubuntu Japanese Team の）をインストールしようとしたときのこと。

インストーラの質問にいろいろ答えてファイルコピーを待つのみ、となったのだけれども 80% ほど進んだところで、ディスクへのコピー失敗のダイアログが出現。もう一度繰り返してみたものの同じ症状。

その 10 分後、原因判明。ダウンロードした際に CD イメージが壊れただけというオチ。

md5: 96423ffca42388c0acb7f45256082e1f 。うん、ちがうね md5: d65b381492153402a7276a8551247619 にならないと。