查找字符串中特定字符的範圍

我在Windows 7上使用python-3.x。我有一個由數百萬字符組成的字符串。考慮例如：查找字符串中特定字符的範圍

ATCGNNNATCGATNNNNNATCGANTCG

我想要的範圍是N。在這裏，[[4,7], [13,18], [23,24]]。我不能只採取N s的立場，然後將它們轉換爲範圍，因爲它是一個巨大的數據，這種方法會太慢。這似乎是一個很容易的問題，但實際上沒有好的方法出現在我的腦海。有沒有一個快速的方法來做到這一點？

來源

2014-07-19 user3015703

不知道如何擴展到數百萬個字符的字符串，但你可以嘗試regular expressions：

>>> import re 
>>> data = "ATCGNNNATCGATNNNNNATCGANTCG" 
>>> spans = (g.span() for g in re.finditer('N+', data)) 
>>> list(spans) 
[(4, 7), (13, 18), (23, 24)]

更新：與A，C，G，T的隨機生成的字符串想這一點，和N.對於1,000,000個字符，list(spans)需要不到一秒的時間，對於10,000,000個字符，我的非全新計算機需要約10秒鐘，找到大約1,600,000個N的組。

來源

2014-07-19 12:02:08

使用'g.span（）'可能會稍微快一點。 – DSM

對於數以百萬計的人物，我不會一次消費迭代器的理解力，但除了那個偉大的方法+1 –

此外，不需要圍繞'g.span（）' –

沒有再一個解決方案：

from itertools import chain 

def find_ranges(it, elem): 
    start = None 
    for i, e in enumerate(chain(it, [None])): 
     if not start and e == elem: 
      start = i 
     elif start and e != elem: 
      yield (start, i) 
      start = None

與IPython中的魔術％timeit測量：

In [1]: import random 
In [2]: s = [random.choice("ACGTN") for i in range(1000000)] 
In [3]: %timeit list(find_ranges(s, "N")) 
10 loops, best of 3: 164 ms per loop

編輯：增加了一個後衛與鏈的末端，以使其工作時序列中的最後一項是搜索到的元素。

來源

2014-07-19 13:37:21

對於漂亮的圖形算法+1。僅用於比較：我在我的系統上測試了兩種解決方案，而正則表達式方法仍然快兩倍。似乎我的電腦真的不是最快的了...... –

謝謝。也許基於正則表達式的解決方案更快，因爲re模塊是用C實現的，而我的是純Python。我相信在C中實現相同的算法會擊敗正則表達式:) –

查找字符串中特定字符的範圍

回答

相關問題