從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？

回答

相關問題