教えて!goo で面白い問題があった。
Pythonのプログラムについて教えてください。
a = [0,1,1,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0]
例えば上記のようなリストがあった際に、1の連続量を導出したいです。
上記の場合は、3、2、5、1という結果を導出したいです。
なにか良い方法はございませんでしょうか？
うん、こういう事をやりたい、って言うシチュエーションはあるかもしんない。
ところで、実はこの質問、ある普遍的なテクニックのサブセットなんだ。この問題の本質的なスーパーセットをランレングス圧縮、と言う。
圧縮って分かるでしょ?例えばHDDに保存したエロ画像がいっぱいになってきて(笑)。「やべ、HDD容量が足りねぇ!」とかなった時に、HDDの使用容量を小さくする為にエロ画像がいっぱいになったフォルダをzip圧縮する、とか言うその圧縮だ(笑)。
詳しくはWikipediaを参照してもらいたいんだけど、このランレングス圧縮ってのは圧縮技法の基礎中の基礎なのね。
ポール・グレアムは自著、ANSI Common Lispで次のような例を語っている。
レストランでは(ランレングス圧縮のアルゴリズム)は次のように働く。ウェイトレスが4人組の客のテーブルへとやってくる。「ご注文は何にしますか?」とウェイトレスが尋ねる。「日替わりを。」と最初の客が答える。「私も同じモノを。」と二人目の客。「それ、良さそうね。」と三人目。皆が四人目を見る。「コリアンダースフレが食べたい。」と彼は静かに答える。ウェイトレスは鼻を鳴らし、ヒールの向きを変え、カウンターへと戻っていく。「日替わり3つ」と彼女はコックに大声で注文し、「それとコリアンダースフレ1つ」と続ける。
つまり、Lispで言うと「流れてきた注文」、'(日替わり 日替わり 日替わり コリアンダースフレ) と言うリストを例えば '((3 日替わり) コリアンダースフレ) と圧縮する事をランレングス圧縮、と言うんだ。Pythonなら ["日替わり" "日替わり" "日替わり" "コリアンダースフレ"] と言うリストを例えば [[3 "日替わり"] "コリアンダースフレ"] に直す事だ。それぞれ、後者は「データが圧縮されてる」事が分かるだろう。
まさしく、問いに対する「一般的な方法論/テクニック」になっている(あとはフィルタリングするだけ、と言う事だ)。
そして、ランレングス圧縮は基礎的なんだけど、例えばエロ画像とか(笑)、究極的にはバイナリ(0と1の羅列でのデータ形式)なんで、「あー、なるほど、そうすればデータ圧縮が可能なんだ」と何となく分かるんじゃないか。
ポール・グレアムのANSI Common Lispでは殆ど最初の方でANSI Common Lispで書かれたランレングス圧縮のコード例を示している。
Racketに翻訳すれば、こういうコードがランレングス圧縮の基本的なコードになる。
(define (compress x)
(if (pair? x)
(compr (car x) 1 (cdr x))
x))
(define (compr elt n lst)
(let loop ((elt elt) (n n) (lst lst) (acc '()))
(if (null? lst)
(reverse (cons (n-elts elt n) acc))
(let ((next (car lst)))
(let ((it (eqv? next elt)))
(loop (if it elt next)
(if it (+ n 1) 1)
(cdr lst)
(if it acc (cons (n-elts elt n) acc))))))))
(define (n-elts elt n)
(if (> n 1)
`(,n ,elt)
elt))
あるいは、もうちょっとSchemeっぽくローカル関数を適用すればこんなカンジになるだろう。
(define (compress x)
(define (compr elt n lst acc)
(if (null? lst)
(reverse (cons (n-elts elt n) acc))
(let ((next (car lst)))
(let ((it (eqv? next elt)))
(compr (if it elt next)
(if it (+ n 1) 1)
(cdr lst)
(if it acc (cons (n-elts elt n) acc)))))))
(define (n-elts elt n)
(if (> n 1)
`(,n ,elt)
elt))
(if (pair? x)
(compr (car x) 1 (cdr x) '())
x))
もっとScheme臭くすればこうか。
(define (compress x)
(define (n-elts elt n)
(if (> n 1)
`(,n ,elt)
elt))
(if (pair? x)
(let loop ((elt (car x)) (n 1) (lst (cdr x)) (acc '()))
(if (null? lst)
(reverse (cons (n-elts elt n) acc))
(let* ((next (car lst)) (it (eqv? next elt)))
(loop (if it elt next)
(if it (+ n 1) 1)
(cdr lst)
(if it acc (cons (n-elts elt n) acc))))))
x))
要するに受け取ったリストの先頭を調べ、継続的にその値が出てくればカウンター(n)の値を増やしつつ再帰し、現在持ってる要素とリストの先頭の値が食い違えばカウンターの値を1へと戻す。その時点で関数n-eltsで生成したリスト(ここにはそれまでの「要素名」とカウンターの値が保持されている)をアキュムレータにconsして、与えられたリストが空になるまで再帰を継続する。
コードは若干厳しいが、発想は単純だ。やってることは何てことがない。
元々のお題はPythonなんで、ポール・グレアムのコードのPython版も見てみよう。
def compress(x):
if isinstance(x, list):
return compr(x[0], 1, x[1:])
else:
return x
def compr(elt, n, lst):
acc = []
while True:
if lst == []:
return acc + [n_elts(elt, n)]
else:
nxt = lst[0]
it = nxt == elt
acc += [] if it else [n_elts(elt, n)]
lst = lst[1:]
n = n + 1 if it else 1
elt = elt if it else nxt
def n_elts(elt, n):
if n > 1:
return [n, elt]
else:
return elt
これはRacket版の翻訳に過ぎないが、何度も言うけど、Pythonは再帰が苦手な言語なんで、「人力で末尾再帰最適化」を施してループはwhileで書いてある。また、それに沿って、関数comprの引数処理の順番が、Racketの末尾再帰のそれと逆転してる事に気をつけよう。Lispは原則、前方参照を許さないが、PythonはLisp観点だとそれを許すように見える言語の為、引数処理の順番を間違えると、以降の処理が思わぬ影響を受けてバグる事になる。これを避ける為には、Racket/Schemeの末尾再帰での引数処理の順序と真逆の順序で処理をした方が良い。
また、Racket/Schemeはリストに要素を付け加えるのは基本的にconsな為、最終的にアキュムレータをreverseして返さないとならないが、Pythonのリスト結合は前からでも後ろからでもO.K.と言うアバズレ女みたいな性質があるので(笑)、結合順序さえ気をつければreverseするような余計な演算は端折れる。アバズレ女は色んな意味で都合がいいんだ(笑)。
Racketと同様にローカル関数使用版を作りたければ、次のようになるだろう。
def compress(x):
def compr(elt, n, lst, acc = []):
while True:
if lst == []:
return acc + [n_elts(elt, n)]
else:
nxt = lst[0]
it = nxt == elt
acc += [] if it else [n_elts(elt, n)]
lst = lst[1:]
n = n + 1 if it else 1
elt = elt if it else nxt
def n_elts(elt, n):
return [n, elt] if n > 1 else elt
return compr(x[0], 1, x[1:]) if isinstance(x, list) else x
あるいはこんなカンジとかね。
def compress(x):
def n_elts(elt, n):
return [n, elt] if n > 1 else elt
if isinstance(x, list):
elt, n, lst, acc = x[0], 1, x[1:], []
while True:
if lst == []:
return acc + [n_elts(elt, n)]
else:
nxt = lst[0]
it = nxt == elt
acc += [] if it else [n_elts(elt, n)]
lst = lst[1:]
n = n + 1 if it else 1
elt = elt if it else nxt
else:
return x
なお、Python版ではRacket版でnextと名付けられてる変数名がnxtとなっている。これはPythonではnextが予約語だから、だ。
もちろんローカル環境でnextを使っても、大域的には影響はないが、IDLEなんかでの統合開発環境では、予約語や基本的な組み込み関数名の色を変えて知らせてくれるので、危険な「予約語のシャドウイング」は敢えて避けるようにするクセを付けた方がいいだろう。
さて、このランレングス圧縮のコードさえあれば、与題なんざすぐ解けるわけだ。あとはフィルタリングすればいいだけ、だからな。
> (define *a* '(0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0))
> (map (lambda (x)
(if (list? x)
(car x)
x)) (filter (lambda (x)
(or (and (number? x) (= x 1))
(and (list? x) (= (cadr x) 1))))
(compress *a*)))
'(3 2 5 1)
>
Pythonだったらこんなカンジだ。
>>> a = [0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0]>>> [i[0] if isinstance(i, list) else i for i in filter(lambda x: isinstance(x, int) and x == 1 or isinstance(x, list) and x[1] == 1, compress(a))]
[3, 2, 5, 1]
>>>
ランレングス圧縮のコードを転用すれば、このように題意はすぐ解ける(※1)。
とランレングス圧縮を紹介しておいて、だ。
ただ、長ぇよな(笑)。
ポール・グレアムのコードは基礎的なランレングス圧縮を丁寧に説明してるコードではあるんだけど、本の最初の方に出てきてるだけあって、コード自体が圧縮されてるわけじゃあない。
理論的な話はさておいて、ここからはランレングス圧縮から離れて、この与題に最適化した考え方でもっと短いコードを書いていこうと思う。
このテの、ちとリストで扱いづらい問題の場合、意外と便利なのは文字列だ。文字列操作の為の関数が豊富だった場合、文字列へと変換すれば意外とアッサリ解けたりする。
Racketなんかでは次のように書いてみる。
> (require (only-in srfi/13 string-concatenate string-tokenize) (only-in srfi/14 char-set))
> (define *a* '(0 1 1 1 0 0 0 0 1 1 0 1 1 1 1 1 0 1 0))
> (map string-length (string-tokenize (string-concatenate (map number->string *a*)) (char-set #\1)))
'(3 2 5 1)
>
string-tokenizeは第2引数に与えた文字セット以外を「区切り文字」として認識する。従って、例えば "0111000011011111010" と言う文字列を与えられ、文字セットを#\1とした場合、 #\1と言う文字以外を全部区切り文字と認識して与えられた文字列を分割する。
> (string-tokenize "0111000011011111010" (char-set #\1))
'("111" "11" "11111" "1")
>
実はこの時点でこの問題はほぼ解けた、と言って良い。あと、必要なのは、各文字列の長さが何なのか、と言う事だが、これはmapで簡単に調べる事が出来る。
これで終了、だ。あとは最初のリストを文字列に変換出来れば良い、って事だ。
これらを連続させれば最初に見せたワンライナーになるわけ、だ。
Pythonも同様に、リストを文字列に変換すれば上手くワンライナーで処理する事が出来る。
>>> a = [0,1,1,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0]
>>> [len(i) for i in "".join(map(str, a)).split("0") if i != ""]
[3, 2, 5, 1]
>>>
これもRacketと発想は同じで、まずは与えられたリストを文字列へと変換する。
>>> "".join(map(str, a))
'0111000011011111010'
>>>
"0" を区切り文字として文字列を分割する。
>>> "".join(map(str, a)).split("0")
['', '111', '', '', '', '11', '11111', '1', '']
>>>
分割された各文字列の長さを調べる。
>>> [len(i) for i in "".join(map(str, a)).split("0")]
[0, 3, 0, 0, 0, 2, 5, 1, 0]
>>>
ただし、空文字列があるんで、そいつをフィルタリングすればいい、って事だ。
>>> [len(i) for i in "".join(map(str, a)).split("0") if i != ""]
[3, 2, 5, 1]
とまぁ、ワンライナーで処理が可能だ。
※1: 実はPythonのitertools.groupbyは、事実上、このポール・グレアムのランレングス圧縮コードと同じ事をやっている。
それが理由で、全体的にグルーピングするには、一旦引数となるリストをソートしないとならないわけだ(ソートすれば、全ての値が昇順なり降順なり揃うんで、連続的に拾ってグルーピングが出来る)。
従って、
>>> from itertools import groupby>>> a = [0,1,1,1,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0]>>> [len(list(i[1])) for i in groupby(a) if i[0] == 1]
[3, 2, 5, 1]
>>>
と書いても良い。
