pythonでrun-length decode

Prologの練習問題サイトにrun-length encodingがあったのでやってみます。
PrologSite

問題はこれ。

1.12 (**) Decode a run-length encoded list.
Given a run-length code list generated as specified in problem 1.11. Construct its uncompressed version.

難易度がエンコードのより高いらしいんですが、とっても簡単な気がします。。。

コードはこちら。

l = ((4, 'a'), (1, 'b'), (2, 'c'), (2, 'a'), (1, 'd'), (4, 'e'))

def decode(data):
    return ''.join([it[1] * it[0] for it in data])

print(decode(l))

今回もとってもシンプルにできました。

リスト内包表記とジェネレータの比較

エキPy読書会でジェネレータお勧め！どんどん使うべし的な話がありました。
ジェネレータの使いどころとしては、膨大なデータを扱うときや実行に時間がかかるときということでした。
リスト内包と比べるとメモリの使用量が少なくて済むことや、複雑な処理もかけるというところが優位といったところでしょうか。
逆にリスト内包では速度面でジェネレータより優位でしょう。
ということで、リスト内包がジェネレータよりどれくらい速度面で有利か実際に速度を比較してみました。

文字列'1'を大量に生成して連結するものと、
1をひたすら足していくもので比較してみました。
コードは以下のとおり

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

import timeit

import gc
gc.disable()

print("JOIN SMALL LIST : ", timeit.Timer("'+'.join(['1' for x in range(0,1000)])").timeit(number=1000))
print("JOIN SMALL GEN  : ", timeit.Timer("'+'.join(('1' for x in range(0,1000)))").timeit(number=1000))
print("JOIN LARGE LIST : ", timeit.Timer("'+'.join(['1' for x in range(0,1000000)])").timeit(number=10))
print("JOIN LARGE GEN  : ", timeit.Timer("'+'.join(('1' for x in range(0,1000000)))").timeit(number=10))

print("SUM SMALL LIST : ", timeit.Timer("sum([1 for x in range(0,1000)])").timeit(number=1000))
print("SUM SMALL GEN  : ", timeit.Timer("sum((1 for x in range(0,1000)))").timeit(number=1000))
print("SUM LARGE LIST : ", timeit.Timer("sum([1 for x in range(0,1000 * 1000 * 10)])").timeit(number=10))
print("SUM LARGE GEN  : ", timeit.Timer("sum((1 for x in range(0,1000 * 1000 * 10)))").timeit(number=10))

結果は次のとおり

$ python3 time.py
JOIN SMALL LIST : 0.172473907471
JOIN SMALL GEN : 0.254935979843
JOIN LARGE LIST : 2.00245213509
JOIN LARGE GEN : 2.79136586189
SUM SMALL LIST : 0.168716192245
SUM SMALL GEN : 0.216814041138
SUM LARGE LIST : 18.0934979916
SUM LARGE GEN : 22.7823500633

joinに関してはリスト内包の方が1.4倍近く、sumに関しては1.3倍近く早いようです。
ジェネレータだとnextメソッドの呼び出しがどうしても入るのでその分が響くんだろうと予想してます。
リストのC実装は見てないのでわかりません・・・w
python3ではジェネレータの速度が早くなったと聞いていたんですが、
まだまだリスト内包には及ばない用です。
やはり状況によってうまく使い分けることが必要ですね。

• • -

以下余談ですが、
配列を同じ値で初期化するには以下のような方法もあります。

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

import timeit

import gc
gc.disable()

print("JOIN SMALL OTHER: ", timeit.Timer("'+'.join(['1'] * 1000)").timeit(number=1000))
print("JOIN LARGE OTHER: ", timeit.Timer("'+'.join(['1'] * 1000000)").timeit(number=10))

print("SUM SMALL OTHER: ", timeit.Timer("sum([1] * 1000)").timeit(number=1000))
print("SUM LARGE OTHER: ", timeit.Timer("sum([1] * (1000 * 1000 * 10))").timeit(number=10))

これを実行すると以下のような結果になります。

$ python3 time.py
JOIN SMALL OTHER: 0.0509331226349
JOIN LARGE OTHER: 0.722629070282
SUM SMALL OTHER: 0.0472800731659
SUM LARGE OTHER: 5.57367396355

join、sumの両方ともに約3-4倍ほど高速です。
今回の用な単純なデータを生成するときにしか使えませんが、
リスト内包、ジェネレータにとらわれず色々試行錯誤することが大切ですね。

• • -

追記 2010/09/13 11:25

methaneさんより、gcをonにしたらジェネレータの方が早くならないか？というコメントをいただいたので、on-off時の速度も載せてみます。
ちなみに、gcをoffにした理由は、methaneさんもおっしゃっているように、
オブジェクトを一気に作る（メモリを消費する）とgcが動いて、
gcが介在しない「純粋な」速度比較ができないからといった理由からです。
コードは以下のとおり。

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

import timeit

print("GC ON")
print("JOIN SMALL LIST : ", timeit.Timer("'+'.join(['1' for x in range(0,1000)])").timeit(number=1000))
print("JOIN SMALL GEN  : ", timeit.Timer("'+'.join(('1' for x in range(0,1000)))").timeit(number=1000))
print("JOIN SMALL OTHER: ", timeit.Timer("'+'.join(['1'] * 1000)").timeit(number=1000))
print("JOIN LARGE LIST : ", timeit.Timer("'+'.join(['1' for x in range(0,1000000)])").timeit(number=10))
print("JOIN LARGE GEN  : ", timeit.Timer("'+'.join(('1' for x in range(0,1000000)))").timeit(number=10))
print("JOIN LARGE OTHER: ", timeit.Timer("'+'.join(['1'] * 1000000)").timeit(number=10))

print("SUM SMALL LIST : ", timeit.Timer("sum([1 for x in range(0,1000)])").timeit(number=1000))
print("SUM SMALL GEN  : ", timeit.Timer("sum((1 for x in range(0,1000)))").timeit(number=1000))
print("SUM SMALL OTHER: ", timeit.Timer("sum([1] * 1000)").timeit(number=1000))
print("SUM LARGE LIST : ", timeit.Timer("sum([1 for x in range(0,1000 * 1000 * 10)])").timeit(number=10))
print("SUM LARGE GEN  : ", timeit.Timer("sum((1 for x in range(0,1000 * 1000 * 10)))").timeit(number=10))
print("SUM LARGE OTHER: ", timeit.Timer("sum([1] * (1000 * 1000 * 10))").timeit(number=10))

import gc
gc.disable()

print("GC OFF")
print("JOIN SMALL LIST : ", timeit.Timer("'+'.join(['1' for x in range(0,1000)])").timeit(number=1000))
print("JOIN SMALL GEN  : ", timeit.Timer("'+'.join(('1' for x in range(0,1000)))").timeit(number=1000))
print("JOIN SMALL OTHER: ", timeit.Timer("'+'.join(['1'] * 1000)").timeit(number=1000))
print("JOIN LARGE LIST : ", timeit.Timer("'+'.join(['1' for x in range(0,1000000)])").timeit(number=10))
print("JOIN LARGE GEN  : ", timeit.Timer("'+'.join(('1' for x in range(0,1000000)))").timeit(number=10))
print("JOIN LARGE OTHER: ", timeit.Timer("'+'.join(['1'] * 1000000)").timeit(number=10))

print("SUM SMALL LIST : ", timeit.Timer("sum([1 for x in range(0,1000)])").timeit(number=1000))
print("SUM SMALL GEN  : ", timeit.Timer("sum((1 for x in range(0,1000)))").timeit(number=1000))
print("SUM SMALL OTHER: ", timeit.Timer("sum([1] * 1000)").timeit(number=1000))
print("SUM LARGE LIST : ", timeit.Timer("sum([1 for x in range(0,1000 * 1000 * 10)])").timeit(number=10))
print("SUM LARGE GEN  : ", timeit.Timer("sum((1 for x in range(0,1000 * 1000 * 10)))").timeit(number=10))
print("SUM LARGE OTHER: ", timeit.Timer("sum([1] * (1000 * 1000 * 10))").timeit(number=10))

で、結果は以下のとおり。

$ python3 time.py
GC ON
JOIN SMALL LIST : 0.180270195007
JOIN SMALL GEN : 0.263254165649
JOIN SMALL OTHER: 0.0492539405823
JOIN LARGE LIST : 1.99416089058
JOIN LARGE GEN : 2.78649997711
JOIN LARGE OTHER: 0.726522922516
SUM SMALL LIST : 0.173731803894
SUM SMALL GEN : 0.229410171509
SUM SMALL OTHER: 0.0544180870056
SUM LARGE LIST : 17.9849619865
SUM LARGE GEN : 24.5595469475
SUM LARGE OTHER: 5.52004003525
GC OFF
JOIN SMALL LIST : 0.175493001938
JOIN SMALL GEN : 0.252235889435
JOIN SMALL OTHER: 0.0482840538025
JOIN LARGE LIST : 1.97846293449
JOIN LARGE GEN : 2.78740787506
JOIN LARGE OTHER: 0.715709924698
SUM SMALL LIST : 0.183133125305
SUM SMALL GEN : 0.236751794815
SUM SMALL OTHER: 0.0463128089905
SUM LARGE LIST : 18.0269918442
SUM LARGE GEN : 24.1297588348
SUM LARGE OTHER: 5.46452307701

gc-offの時の方がgc-onの時より全体的に早くなってますが、（一部遅くなってる！？）
ジェネレータの方がやはり遅いみたいです。。。
なにか根本的に考え方（コード）が間違ってるのだろうか・・・

pythonでrun-length encoding

Prologの練習問題サイトにrun-length encodingがあったのでやってみます。
PrologSite

問題はこれ。

1.10 (*) Run-length encoding of a list.
Use the result of problem 1.09 to implement the so-called run-length encoding data compression method. Consecutive duplicates of elements are encoded as terms [N,E] where N is the number of duplicates of the element E.

Example:
?- encode([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [ [4,a],[1,b],[2,c],[2,a],[1,d][4,e] ]

import itertools

def encode(seq):
    return ((len(list(group)), c) for c, group in itertools.groupby(seq))

さすがにこれだけだとおもしろくないので、次の問題も。

1.11 (*) Modified run-length encoding.
Modify the result of problem 1.10 in such a way that if an element has no duplicates it is simply copied into the result list. Only elements with duplicates are transferred as [N,E] terms.

Example:
?- encode_modified([a,a,a,a,b,c,c,a,a,d,e,e,e,e],X).
X = [ [4,a],b,[2,c],[2,a],d,[4,e] ]

import itertools

def encode(seq):
    return ((len(list(group)), c) for c, group in itertools.groupby(seq))

def encode_modified(seq):
    return (x[1] if x[0] == 1 else x for x in encode(seq))

itertools.groupbyは連続する値ごとに区切った値をタプルで取得できます。
itertoolsはほんと強力ですね・・・

初トラックバックだ。

ブログ読んでたら0と1を次々と返したいなんていうのがあったのでやってみた。
Algorithm - 0と1を次々と返す簡単なお仕事

class Cycle(object):
    def __init__(self, vals=[0,1]):
        import itertools
        self.it = itertools.cycle(vals)

    def __call__(self):
        return self.it.next()

cycle = Cycle()
print cycle()
print cycle()
print cycle()

cycle = Cycle([True, False])
print cycle()
print cycle()
print cycle()

なんちゅうか、cycleをラップしただけwww
itertoolsが汎用性高くて困る。
さて、仕事だ。。。

pythonでuniq

今日はpythonでuniqを実装してみましたよ。

def iuniq(it):
    if hasattr(it, '__iter__'):
         readed = set()
         for i in it:
             if i in readed:
                 continue
             else:
                 readed.add(i)
                 yield i
    else:
        raise TypeError('argument has not __iter__.')

書いてから思ったけど、、、、

list(set(it))

で一発ですね・・・orz
ま、まぁ一気にメモリ上に展開しないだけ省エネってことで＾＾；

pythonでflatten

rubyには配列を平滑化するflattenなんていうメソッドがありますが、
意外にもpythonにはありませんでした。（当然あるものと思ってましたが＾＾；）
ググってみるとやっぱいろんな人がサンプルコード書いてますね。
そこで、自分でもflattenかいてみました。
引数がイテレータであれば平滑化します。
再帰でしかもジェネレータなんでちょっとわかりにくい？

def flatten(item):
    if hasattr(item, '__iter__'):
        for it in item:
            for _ in flatten(it):
                yield _
    else:
        yield item

オレオレIPアドレス範囲表記のパース

ツールとかを作っているとIPアドレスの範囲を指定して書きたいことがたまにあります。
例えば192.168.1.10 - 192.168.1.20の範囲の生きているPCをpingで調べたいときなど。
このIP範囲を表すとき、192.168.1.[10-20]なんて指定したいわけです。
こんな表記の文字列をパースして192.168.1.10から192.168.1.20までの10個のIPを生成する時のpythonコードを書いてみました。
なかなかうまくかけてるんじゃないかと思ったので公開してみます。

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

if __name__ == '__main__':
    import sys
    import re
    import itertools

    pattern = re.compile('\[(\d+)\-(\d+)\]')

    args = sys.argv[1:]

    def _iprange(range_str):
        """
        [start-end]表記を展開して返すジェネレータ。
        役割的にはrange(start, end+1)みたいなもの。
        """
        match = pattern.match(range_str)
        if match is not None:
            start, end = sorted(map(int, match.groups()))
            for i in range(start, end + 1):
                yield str(i)
        else:
            yield range_str

    for ip_pattern in args:
        # 各IPのセグメント単位に_iprangeを適用して展開してそれの積を取る（展開）
        for ip in itertools.product(*map(_iprange, ip_pattern.split('.'))):
            print '.'.join(ip)

itertools便利ですよね。