1

私の仕事では、RLE (ランレングス エンコーディング) パターンがよく出てくるようです。

その本質は、「ブレーク」が表示されるか、入力の最後に到達するたびに、最後の「ブレーク」以降に発生した要素の削減を出力していることです。

(実際の RLE では、「ブレーク」はこの文字が最後の文字と一致しないことですが、現実の世界では通常もう少し複雑ですが、それでも現在の要素と最後の要素の関数です。)

last_val != None: rle.append((last_val, count))ループと終了の両方で発生する重複した条件とアクションを削除したい。

問題は次のとおりです。

  1. それらを関数呼び出しに置き換えると、コードが少なくなるのではなく、多くなります。
  2. 命令型のスタイルに保つ (たとえば、Haskell では、問題は蒸発するだけです)。

必須の Python コードは次のとおりです。

#!/usr/bin/env python

data = "abbbccac"

if __name__ == '__main__':
  rle = []
  last_val = None
  count = 0;

  for val in data:
    if val != last_val and last_val != None:
      rle.append((last_val, count))
      count = 1
    else:
      count += 1
    last_val = val
  if last_val != None:
    rle.append((last_val, count))

  print rle

PS関数型言語で自明に解決可能：

#!/usr/bin/env runhaskell
import Data.List (group)

dat = "abbbccac"

rle :: Eq a => [a] -> [(a, Int)]
rle arr = map (\g -> (head g, length g)) $ group arr

main :: IO ()
main = print $ rle dat
4

5 に答える 5

3

Pythonの「バッテリーが含まれています」を使用して自明に解決可能：

>>> data = "abbbccac"
>>> from itertools import groupby
>>> ilen = lambda gen : sum(1 for x in gen)
>>> print [(ch, ilen(ich)) for ch,ich in groupby(data)]
[('a', 1), ('b', 3), ('c', 2), ('a', 1), ('c', 1)]

groupby2 タプルの反復子を返します。1 つ目は次のグループを表す値で、2 つ目はグループ内の項目を反復処理するために使用できる反復子です。グループの長さだけが必要ですが、長さを直接取得することはできないilenため、反復子の長さを計算する単純なラムダ関数を追加しました。

于 2012-07-06T08:43:57.840 に答える
2

これは、より命令的な形式です。リスト要素のいずれにも一致しない使い捨てのセンチネルを追加またはチェーンすることで、重複したコードを排除できます。

from itertools import chain

def rle(seq):
    ret = []
    sentinel = object()
    enum = enumerate(chain(seq,[sentinel]))
    start,last = next(enum)
    for i,c in enum:
        if c != last:
            ret.append((last,i-start))
            start,last = i,c
    return ret

これは、入力 seq が空の場合でも適切に処理し、入力は文字列だけでなく、任意のシーケンス、イテレータ、またはジェネレータにすることができます。

于 2012-07-06T11:07:56.383 に答える
2

私がそれを正しく理解していれば簡単です...

from itertools import groupby

data = "abbbccac"

print [(k, len(list(g))) for k,g in groupby(data)]

うわー-ポールの非常によく似た機能を私のものと比較すると、非常に驚​​くべき結果が得られました。リストの読み込みが 10 ～ 100 倍高速であることがわかりました。さらに驚くべきことは、ブロックが大きくなるにつれて、リストの実装の利点が大きくなることです。

これが、私が ♥ Python を使用する理由だと思います。これにより、簡潔な表現がうまく機能します。たとえそれが魔法のように思えることもあります。

自分でデータを確認してください。

from itertools import groupby
from timeit import Timer

data = "abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac" 

def rle_walk(gen):
    ilen = lambda gen : sum(1 for x in gen)
    return [(ch, ilen(ich)) for ch,ich in groupby(data)]

def rle_list(data):
    return [(k, len(list(g))) for k,g in groupby(data)]

# randomy data
t = Timer('rle_walk("abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac")', "from __main__ import rle_walk; gc.enable()")
print t.timeit(1000)

t = Timer('rle_list("abbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccacabbbccac")', "from __main__ import rle_list; gc.enable()")
print t.timeit(1000)

# chunky blocks
t = Timer('rle_walk("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc")', "from __main__ import rle_walk; gc.enable()")
print t.timeit(1000)

t = Timer('rle_list("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbccccccccccccccccccccccccccccccccccccccccccccc")', "from __main__ import rle_list; gc.enable()")
print t.timeit(1000)

（小さいほど良い）の結果が得られます：

1.42423391342    # lambda and walk - small blocks
0.145968914032   # make list - small blocks
1.41816806793    # lambda and walk - large blocks
0.0165541172028  # make list - large blocks
于 2012-07-06T08:48:34.407 に答える
1

enumerate見た値の数を追跡し、last_val と last_index (または (last_val, last_index) をタプルとして) を保存するために使用する場合は、少なくとも else 句を取り除くことができます。例えば

last_index = 0
last_val = None

for index, val in enumerate(data):
    if val != last_val and last_val is not None:
        rle.append((last_val, index - last_index + 1))
        last_val = val
        last_index = index
    last_val = val
if last_val is not None:
    rle.append((last_val, index - last_index + 1))

任意の時点で列挙を開始することもでき、カウントアップします (したがって、で初期化できますenumerate(data, last_index)。カウントを 1 から開始したいようです。そのため、この+ 1部分を追加しました。

列挙は、イテレータから生成された要素の数をカウントするだけで、型は関係ありません。

于 2012-07-06T08:34:51.223 に答える
0

私はgroupbyソリューションを好みますが、命令型ソリューションを作成する最も便利な方法は、多くの場合、ジェネレーターとして使用することです。

data = "abbbccac"

def rle(xs):
    def g():
        last = object()
        n = 0
        for x in xs:
            if x != last:
                yield last,n
                last = x
                n = 0
            n += 1
    return list(g())[1:]

print rle(data)
于 2012-07-07T02:59:25.827 に答える