python字符串查找第二个 - python返回字符位置




在字符串中查找第n次出现的子字符串 (12)

这似乎应该是非常微不足道的,但我是Python的新手,并希望做到最Python的方式。

我想在字符串中找到第n个子字符串的出现位置。

这应该与我想要做的事情相同

mystring.find("substring", 2nd)

你如何在Python中实现这一点?


下面是一个更直接的迭代解决方案的Pythonic版本:

def find_nth(haystack, needle, n):
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+len(needle))
        n -= 1
    return start

例:

>>> find_nth("foofoofoofoo", "foofoo", 2)
6

如果你想找到needle的第n个重叠事件,你可以增加1而不是len(needle) ,如下所示:

def find_nth_overlapping(haystack, needle, n):
    start = haystack.find(needle)
    while start >= 0 and n > 1:
        start = haystack.find(needle, start+1)
        n -= 1
    return start

例:

>>> find_nth_overlapping("foofoofoofoo", "foofoo", 2)
3

这比Mark的版本更易于阅读,并且不需要额外的分割版本或导入正则表达式模块的内存。 它也遵守python禅中的一些规则,而不像其他的方法:

  1. 简单胜于复杂。
  2. Flat比嵌套更好。
  3. 可读性计数。

了解这个正则表达式并不总是最好的解决方案,我可能会在这里使用一个:

>>> import re
>>> s = "ababdfegtduab"
>>> [m.start() for m in re.finditer(r"ab",s)]
[0, 2, 11]
>>> [m.start() for m in re.finditer(r"ab",s)][2] #index 2 is third occurrence 
11

怎么样:

c = os.getcwd().split('\\')
print '\\'.join(c[0:-2])

我可能会这样做,使用带有索引参数的find函数:

def find_nth(s, x, n):
    i = -1
    for _ in range(n):
        i = s.find(x, i + len(x))
        if i == -1:
            break
    return i

print find_nth('bananabanana', 'an', 3)

我想这不是特别的Pythonic,但很简单。 你可以使用递归来代替它:

def find_nth(s, x, n, i = 0):
    i = s.find(x, i)
    if n == 1 or i == -1:
        return i 
    else:
        return find_nth(s, x, n - 1, i + len(x))

print find_nth('bananabanana', 'an', 3)

这是解决这个问题的一种功能性方式,但我不知道这是否会使它变得更加Pythonic。


我提供了一些基准比较结果,比较迄今为止提出的最显着的方法,即@ bobince的findnth() (基于str.split() )与@ tgamblin's或@Mark Byers的find_nth() (基于str.find() )。 我也会比较一下C扩展( _find_nth.so )来看看我们可以走多快。 这里是find_nth.py

def findnth(haystack, needle, n):
    parts= haystack.split(needle, n+1)
    if len(parts)<=n+1:
        return -1
    return len(haystack)-len(parts[-1])-len(needle)

def find_nth(s, x, n=0, overlap=False):
    l = 1 if overlap else len(x)
    i = -l
    for c in xrange(n + 1):
        i = s.find(x, i + l)
        if i < 0:
            break
    return i

当然,如果字符串很大,性能最重要,所以假设我们想要在名为'bigfile'的1.3 GB文件中找到1000001行新行('\ n')。 为了节省内存,我们希望处理文件的mmap.mmap对象表示形式:

In [1]: import _find_nth, find_nth, mmap

In [2]: f = open('bigfile', 'r')

In [3]: mm = mmap.mmap(f.fileno(), 0, access=mmap.ACCESS_READ)

findnth()已经存在第一个问题,因为mmap.mmap对象不支持split() 。 所以我们实际上必须将整个文件复制到内存中:

In [4]: %time s = mm[:]
CPU times: user 813 ms, sys: 3.25 s, total: 4.06 s
Wall time: 17.7 s

哎哟! 幸运的s仍然适用于我的Macbook Air的4 GB内存,所以让我们以findnth()基准:

In [5]: %timeit find_nth.findnth(s, '\n', 1000000)
1 loops, best of 3: 29.9 s per loop

显然是一个可怕的表现。 让我们看看基于str.find()的方法如何:

In [6]: %timeit find_nth.find_nth(s, '\n', 1000000)
1 loops, best of 3: 774 ms per loop

好多了! 显然, findnth()的问题在于它在split()期间被迫复制字符串,这已经是我们第二次在s = mm[:]之后复制了1.3 GB的数据。 这里有find_nth()的第二个优点:我们可以直接在mm上使用它,这样就需要文件的拷贝:

In [7]: %timeit find_nth.find_nth(mm, '\n', 1000000)
1 loops, best of 3: 1.21 s per loop

mms似乎有一个小的性能损失,但这说明find_nth()可以在1.2秒内得到答案,而findnth的总计为47秒。

我发现没有什么情况下,基于str.find()的方法明显比基于str.find()的方法差,因此在这一点上,我会争辩说@ tgamblin或@Mark Byers的答案应该被接受而不是@ bobince的。

在我的测试中,上面的find_nth()版本是我能想出的最快的纯Python解决方案(非常类似于@Mark Byers的版本)。 让我们看看我们可以用C扩展模块做得更好。 这里是_find_nthmodule.c

#include <Python.h>
#include <string.h>

off_t _find_nth(const char *buf, size_t l, char c, int n) {
    off_t i;
    for (i = 0; i < l; ++i) {
        if (buf[i] == c && n-- == 0) {
            return i;
        }
    }
    return -1;
}

off_t _find_nth2(const char *buf, size_t l, char c, int n) {
    const char *b = buf - 1;
    do {
        b = memchr(b + 1, c, l);
        if (!b) return -1;
    } while (n--);
    return b - buf;
}

/* mmap_object is private in mmapmodule.c - replicate beginning here */
typedef struct {
    PyObject_HEAD
    char *data;
    size_t size;
} mmap_object;

typedef struct {
    const char *s;
    size_t l;
    char c;
    int n;
} params;

int parse_args(PyObject *args, params *P) {
    PyObject *obj;
    const char *x;

    if (!PyArg_ParseTuple(args, "Osi", &obj, &x, &P->n)) {
        return 1;
    }
    PyTypeObject *type = Py_TYPE(obj);

    if (type == &PyString_Type) {
        P->s = PyString_AS_STRING(obj);
        P->l = PyString_GET_SIZE(obj);
    } else if (!strcmp(type->tp_name, "mmap.mmap")) {
        mmap_object *m_obj = (mmap_object*) obj;
        P->s = m_obj->data;
        P->l = m_obj->size;
    } else {
        PyErr_SetString(PyExc_TypeError, "Cannot obtain char * from argument 0");
        return 1;
    }
    P->c = x[0];
    return 0;
}

static PyObject* py_find_nth(PyObject *self, PyObject *args) {
    params P;
    if (!parse_args(args, &P)) {
        return Py_BuildValue("i", _find_nth(P.s, P.l, P.c, P.n));
    } else {
        return NULL;    
    }
}

static PyObject* py_find_nth2(PyObject *self, PyObject *args) {
    params P;
    if (!parse_args(args, &P)) {
        return Py_BuildValue("i", _find_nth2(P.s, P.l, P.c, P.n));
    } else {
        return NULL;    
    }
}

static PyMethodDef methods[] = {
    {"find_nth", py_find_nth, METH_VARARGS, ""},
    {"find_nth2", py_find_nth2, METH_VARARGS, ""},
    {0}
};

PyMODINIT_FUNC init_find_nth(void) {
    Py_InitModule("_find_nth", methods);
}

这是setup.py文件:

from distutils.core import setup, Extension
module = Extension('_find_nth', sources=['_find_nthmodule.c'])
setup(ext_modules=[module])

像往常一样python setup.py install 。 由于C代码仅限于查找单个字符,因此在这里可以发挥其优势,但让我们看看它有多快:

In [8]: %timeit _find_nth.find_nth(mm, '\n', 1000000)
1 loops, best of 3: 218 ms per loop

In [9]: %timeit _find_nth.find_nth(s, '\n', 1000000)
1 loops, best of 3: 216 ms per loop

In [10]: %timeit _find_nth.find_nth2(mm, '\n', 1000000)
1 loops, best of 3: 307 ms per loop

In [11]: %timeit _find_nth.find_nth2(s, '\n', 1000000)
1 loops, best of 3: 304 ms per loop

显然还有点快。 有趣的是,内存映射和mmap映射之间的C级没有区别。 同样有趣的是,基于string.hmemchr()库函数的_find_nth()_find_nth()中的简单实现失败了: memchr()中额外的“优化”显然是不起作用的。 ..

总之, findnth()的实现(基于str.split() )实际上是一个糟糕的主意,因为(a)由于需要的复制,它对于较大的字符串表现得非常糟糕,并且(b)它无法工作mmap.mmap对象。 find_nth()的实现(基于str.find() )应该在所有情况下都是首选的(因此可以被接受为这个问题的答案)。

还有相当多的改进空间,因为C扩展的速度几乎比纯Python代码快4倍,这表明可能会出现专用Python库函数的情况。


提供另一个“棘手”的解决方案,它使用splitjoin

在你的例子中,我们可以使用

len("substring".join([s for s in ori.split("substring")[:2]]))

最简单的方法?

text = "This is a test from a test ok" 

firstTest = text.find('test')

print text.find('test', firstTest + 1)

这会给你一个匹配yourstring的起始索引数组:

import re
indices = [s.start() for s in re.finditer(':', yourstring)]

那么你的第n项将是:

n = 2
nth_entry = indices[n-1]

当然你必须小心索引边界。 你可以像这样获取你的yourstring的实例数量:

num_instances = len(indices)

这是你真正想要的答案:

def Find(String,ToFind,Occurence = 1):
index = 0 
count = 0
while index <= len(String):
    try:
        if String[index:index + len(ToFind)] == ToFind:
            count += 1
        if count == Occurence:
               return index
               break
        index += 1
    except IndexError:
        return False
        break
return False

这是另一个re + itertools版本,它应该在搜索strRegexpObject 。 我会毫不犹豫地承认这可能是过度设计的,但由于某种原因它招待我。

import itertools
import re

def find_nth(haystack, needle, n = 1):
    """
    Find the starting index of the nth occurrence of ``needle`` in \
    ``haystack``.

    If ``needle`` is a ``str``, this will perform an exact substring
    match; if it is a ``RegexpObject``, this will perform a regex
    search.

    If ``needle`` doesn't appear in ``haystack``, return ``-1``. If
    ``needle`` doesn't appear in ``haystack`` ``n`` times,
    return ``-1``.

    Arguments
    ---------
    * ``needle`` the substring (or a ``RegexpObject``) to find
    * ``haystack`` is a ``str``
    * an ``int`` indicating which occurrence to find; defaults to ``1``

    >>> find_nth("foo", "o", 1)
    1
    >>> find_nth("foo", "o", 2)
    2
    >>> find_nth("foo", "o", 3)
    -1
    >>> find_nth("foo", "b")
    -1
    >>> import re
    >>> either_o = re.compile("[oO]")
    >>> find_nth("foo", either_o, 1)
    1
    >>> find_nth("FOO", either_o, 1)
    1
    """
    if (hasattr(needle, 'finditer')):
        matches = needle.finditer(haystack)
    else:
        matches = re.finditer(re.escape(needle), haystack)
    start_here = itertools.dropwhile(lambda x: x[0] < n, enumerate(matches, 1))
    try:
        return next(start_here)[1].start()
    except StopIteration:
        return -1

# return -1 if nth substr (0-indexed) d.n.e, else return index
def find_nth(s, substr, n):
    i = 0
    while n >= 0:
        n -= 1
        i = s.find(substr, i + 1)
    return i

>>> s="abcdefabcdefababcdef"
>>> j=0
>>> for n,i in enumerate(s):
...   if s[n:n+2] =="ab":
...     print n,i
...     j=j+1
...     if j==2: print "2nd occurence at index position: ",n
...
0 a
6 a
2nd occurence at index position:  6
12 a
14 a




substring