1

RLE（运行长度编码）模式似乎在我的工作中出现了很多。

其本质是，每次看到“中断”或到达输入末尾时，您输出自上次“中断”以来遇到的元素的减少。

（在实际的 RLE 中，'break' 只是这个字符与最后一个字符不匹配，但在现实世界中它通常更复杂一些，但仍然是当前和最后一个元素的函数。）

我想删除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)]

groupby返回 2 元组的迭代器。第一个是代表下一个组的值，第二个是可用于迭代组中项目的迭代器。您只需要组的长度，但不能直接获取长度，因此我添加了简单的ilenlambda 函数来计算迭代器的长度。

于 2012-07-06T08:43:57.840 回答
2

如果我理解正确的话很简单......

from itertools import groupby

data = "abbbccac"

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

哇 - 将 Paul 的功能与我的非常相似的功能进行比较，得到了非常令人惊讶的结果。事实证明，加载列表的速度要快 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 回答
2

这是一个更重要的形式。您可以通过添加或链接到永远不会匹配任何列表元素的一次性标记来消除重复代码，从而强制序列结束通过您的“this-not-equal-last”代码：

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 回答
1

enumerate如果您使用 else 子句来跟踪您看到的值并将 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部分的原因。

Enumerate 只计算迭代器产生了多少元素，与类型无关。

于 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 回答