文字列を適当な長さで区切って diff を表示する

python algorithm

Python の標準ライブラリに difflib というものがあります。これを使うと、いろいろなフォーマットの diff を表示できます。ちょっと使ってみたいだけなら difflib – シーケンスを比較する - Python Module of the Week のチュートリアルを見てみると分かり易いです。

最もシンプルな diff を取るのは以下になります。

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

import difflib

def diff():
    s1 = unicode("difflib は差異を検出するライブラリです", "utf-8")
    s2 = unicode("diffflib は差分を検出するライブリです", "utf-8")
    d = difflib.Differ()
    print "\n".join(d.compare([s1], [s2]))

def main():
    diff()

if __name__ == "__main__":
    main()

実行結果。

- difflib は差異を検出するライブラリです
?           ^        -

+ diffflib は差分を検出するライブリです
?   +        ^

マルチバイト文字の差異がある場所の位置はちょっとずれてますね。まぁ、よくある(？)話ですかね。

1行がとても長い文字列の diff を取りたい

ある出力の diff を取ろうと思ったら、その出力が1行で2000文字ぐらいありました。ほとんど一緒なんだけど、どこかが違う。目で追うには目が疲れる。適当な長さに区切って diff のある部分だけを見たい。そんな動機から Python だったら difflib あるから簡単にできるんじゃ、、、と思いました。difflib の扱いは上述したように簡単です。しかしやしかし、これが私的に結構はまってしまいました。

適当な長さに文字列を区切る処理を格好良く書きたい！

私は Web やコマンドといった、主に業務アプリを開発してきたのですが、私が携わったアプリではアルゴリズムをあまり必要としません。もちろん、アーキテクチャ的に効率の良い仕組みは考えますが、計算量といった視点から最適化を行うような処理を扱ったことがありません。数学が得意な人は本当にうらやましいです。そんな私でも、このぐらいの処理なら、、、と気持ちの良いアルゴリズムを考えてみようと思ったのがことの始まりです。

まずは普通に考えてみました。

def limit_characters1(s, start, maximum, end=None):
    """
    >>> limit_characters1("12345", 0, 2)
    ['12', '34', '5']
    """
    from math import ceil
    _s = end and s[start:end] or s[start:]
    r = []
    div_num = int(ceil(len(_s) / float(maximum)))
    for i in xrange(div_num):
        _start = i * maximum
        r.append(_s[_start:_start + maximum])
    return r

文字列がいくつのサブ文字列に分割されるかが分かれば、普通のループ処理になります。普通に普通です。何か可もなく不可もなく、当たり障りのない、おもしろみのない人間だと思われそうな雰囲気を醸し出しています。

ここで悪魔の囁きが、、、。

ジェネレータとか使ったら格好良くコーディングできるんじゃないかな

本当に！？ よしやってみよう。

def limit_characters2(s, start, maximum, end=None):
    """
    >>> limit_characters2("12345", 0, 2)
    ['12', '34', '5']
    """
    def _divide(s, maximum):
        yield s[:maximum]
        if s[maximum:]:
            for div in _divide(s[maximum:], maximum):
                yield div
    _s = end and s[start:end] or s[start:]
    r = []
    for div in _divide(_s, maximum):
        r.append(div)
    return r

えぇーーー。ごめんなさい、本当にごめんなさい。身の丈にあわないことをやってはいけません(> <)

ぱっ見て何か訳の分からないコードになってしまいました。普通に考えたら1回のループで済む処理が2つに増えて、さらに再起呼び出してて訳が分かりません。

ジェネレータはやめて再起呼び出しでやってみようかな。

def limit_characters3(s, start, maximum, end=None):
    """
    >>> limit_characters3("12345", 0, 2)
    ['12', '34', '5']
    """
    def _divide(s, maximum):
        if s[maximum:]:
            return [s[:maximum]] + _divide(s[maximum:], maximum)
        return [s[:maximum]]
    _s = end and s[start:end] or s[start:]
    return _divide(_s, maximum)

何かそれっぽい感じのコードになりました。エンタープライズなプログラマだと、基本的に再起呼び出し書くな的なイメージがありますが、これならコードも見易いし、ちょい悪な感じがして良さそうですね。

どれが効率良いのか、スタックオーバーフローしないように気を付けながらプロファイルを取ってみましょう。

In [2]: s = "s" * 3000

In [3]: timeit -n 3 limit_characters1(s, 0, 80)
3 loops, best of 3: 41.6 us per loop

In [4]: timeit -n 3 limit_characters2(s, 0, 80)
3 loops, best of 3: 204 us per loop

In [5]: timeit -n 3 limit_characters3(s, 0, 80)
3 loops, best of 3: 99.7 us per loop

当たり前と言えば、当たり前ですが、余計なことをしない普通のループ処理が1番速かったです。

神様にお前は普通にコードを書いていなさいと言われた気分でした(> <)
もっと効率の良いやり方があったら教えてください。