从RLE模式中删除代码重复，而不使用Haskell？

RLE（游程编码）模式似乎在我的工作中出现了很多。从RLE模式中删除代码重复，而不使用Haskell？

其实质是，您输出的是自上次'休息'以来遇到的元素的减少，每次您看到'break'或您到达输入的末尾。

（在实际RLE中，“破发”就是这种性格不匹配的最后一个字符，但在现实世界中，通常是一个稍微复杂一些，但仍然是当前和最后一个元素的功能。）

我想删除在循环和结尾都出现的重复last_val != None: rle.append((last_val, count))条件和操作。

的问题是：

在更多的代码与函数调用的结果替换它们，而不是更少。
保持它的命令式（例如，在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

P.S.在函数式语言平凡解：

#!/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

来源

2012-07-06 fadedbee

对于它的价值，在Haskell你只需要'RLE =地图（头&&&长度）。 group'。 – 2012-07-06 08:52:38

@Frerich Raabe - 谢谢，我不知道&&&操作符。无点式风格仍然比“正常”的Haskell看起来少得多。 – fadedbee 2012-07-06 10:26:55

'&&&'函数（来自'Control.Arrow'）非常流行，所以大多数Haskell程序员都会识别它。我认为它也是非常具有说服力的，我将'map（head &&& length）'看作是“将函数头部和长度映射到...上”。我喜欢'&&&'如何对应于“和”。 – 2012-07-06 11:28:33

这里是一个更迫切的形式。您可以通过添加或链接到永远不会与任何列表元素匹配的重复代码来消除重复的代码，从而强制序列结束通过您的“本次不等于最后”代码：

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

这甚至可以优雅地处理输入序列为空的情况，输入可以是任何序列，迭代器或生成器，而不仅仅是一个字符串。

来源

2012-07-06 11:07:56 PaulMcG

感谢这个答案，尽管我真的认为它是对这类问题的肯定，对于这些问题，FP（无论是哪种语言）都比命令式风格更有用。我的问题被提出来看看我是否错过了一个明确而优雅的命令式解决方案;我不认为我做过。 – fadedbee 2012-07-06 11:13:50

我认为，与哨兵链接，以便您不必复制优雅上的'ret.append'代码。 – PaulMcG 2012-07-06 20:19:52

如果使用enumerate来跟踪你有多少价值看到和商店，你至少可以摆脱else子句的last_val和last_index（或（last_val，last_index）作为元组）。例如。

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-06 08:34:51

请注意，由于'枚举（G）'等于'izip（count（），（G））'，所以可以通过使用'izip（count（1），（G））'来摆脱'+ 1'相反。（'izip'和'count'来自'itertools'模块） – 2012-07-06 09:34:18

这留下了最后一组。 – PaulMcG 2012-07-06 11:10:42

@PaulMcGuire我注意到，在我发布它之后，我认为我编辑了它，很奇怪。仍然，好眼睛！ – 2012-07-06 14:03:18

中平凡解使用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元组的迭代器。第一个是代表下一个组的值，第二个是可用于迭代组中项目的迭代器。你只需要组的长度，但不能直接取长度，所以我添加了简单的ilen lambda函数来计算迭代器的长度。

来源

2012-07-06 08:43:57 PaulMcG

不能决定我是否喜欢lambda的效率或者我的简洁性:) – 2012-07-06 08:53:02

lambda本身不会增加任何效率，但我认为它更具可读性。我对你的回答中唯一的效率是使用总和而不是列表 - 你的列表创建临时列表，我的总和表达式只是遍历项目的迭代器。如果你只是将'sum（gg in g）'代替'len（list（g））'，你会得到同样的效率。只有当你传递函数给像groupby，sort，map，filter等方法时，你才会获得效率，如果你通过一个C实现的内建像itemgetter - Python函数和lambda都不需要任何优化就可以调用。 – PaulMcG 2012-07-06 09:03:19

Erm ..这就是我的意思... lambda的使用使您能够遍历迭代器..因此，如果碰到大块的话，更高的内存效率:) – 2012-07-06 09:04:48

简单，如果我的理解是正确的...

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-06 08:48:34

'简单，如果我理解它正确'让我嗤笑。著名遗言。 :-) – 2012-07-06 08:49:59

Paul McGuire的解决方案效率更高，因为他不会将列表加载到内存中......但是如果您只有很小的运行编码数据长度，那么列表表达的简洁性可能会很好...... – 2012-07-06 08:56:27

有趣！我也尝试了一个版本，其中我像前面向您所建议的那样总结了表达式，如下所示：'def rle_walk_inline（gen）： return ch（ch，sum（1 for x in ich））for ch，in groupby （data）]'并且时间减少15-20％（通过将函数调用的开销保存到lambda）。另外，试着用一个非常长的字符串重新运行你的测试 - 把你的笨重的块测试和乘以1000的字符串。我的测试表明，使用迭代迭代器是非常一致的所有测试 - 对于一个长字符串，len（list （g））约慢1000倍。 – PaulMcG 2012-07-06 09:49:19

我喜欢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-07 02:59:25 solrize

从RLE模式中删除代码重复，而不使用Haskell？

回答

相关问题