查找字符串中特定字符的范围

我在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中实现相同的算法会击败正则表达式:) –

查找字符串中特定字符的范围

回答

相关问题