在字符串中查找第n个子字符串

Question

这似乎应该是非常简单的,但我是Python的新手,并希望以最Pythonic的方式做到这一点.

我想在字符串中找到第n个子字符串.

必须有一些与我想做的事情相同的东西

mystring.find("substring", 2nd)

你怎么能用Python实现这个目标？

Answer 1

这是一个更直接的迭代解决方案的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

如果你想找到第n个重叠的出现needle,你可以增加,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的版本更容易阅读,并且它不需要分割版本的额外内存或导入正则表达式模块.它还遵循蟒蛇禅的一些规则,不同于各种re方法:

1. 简单比复杂更好.
2. Flat优于嵌套.
3. 可读性很重要.

Answer 2

我认为马克的迭代方法是常用的方法.

这是字符串拆分的替代方法,通常可用于查找相关的进程:

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)

这是一个快速(有点脏,因为你必须选择一些与针不匹配的箔条)单线:

'foo bar bar bar'.replace('bar', 'XXX', 1).find('bar')

Answer 3

这将在字符串中找到第二次出现的子字符串.

def find_2nd(string, substring):
   return string.find(substring, string.find(substring) + 1)

编辑:我没有考虑性能,但快速递归可以帮助找到第n次出现:

def find_nth(string, substring, n):
   if (n == 1):
       return string.find(substring)
   else:
       return string.find(substring, find_nth(string, substring, n - 1) + 1)

Answer 4

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

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

Answer 5

我提供了一些基准测试结果,比较了迄今为止最突出的方法,即@ bobince findnth()(基于str.split())与@ tgamblin或@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文件中找到1000001st换行符('\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(),这已经是我们第二次复制1.3 GB的数据了s = mm[:].第二个优点是find_nth():我们可以mm直接使用它,这样就需要零拷贝的文件:

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

似乎有一个小的性能损失的操作mm与s,但是这说明了find_nth()可以让我们在1.2秒的回答相比,findnth"总第47号.

我没有发现任何情况下str.find()基础方法明显比str.split()基础方法差,所以在这一点上,我认为应该接受@ 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

显然还是要快一点.有趣的是,内存和mmapped案例之间的C级别没有差异.这也是有趣的是_find_nth2(),这是基于string.h的memchr()库函数,失去反对在简单的实现_find_nth():附加的'优化’中memchr()显然事与愿违......

总而言之,findnth()(基于str.split())的实现确实是一个坏主意,因为(a)由于所需的复制,它对较大的字符串执行非常繁琐,(b)它根本不适用于mmap.mmap对象.在所有情况下find_nth()(基于str.find())的实施应该是首选(因此是该问题的可接受答案).

还有相当大的改进空间,因为C扩展比纯Python代码快了近4倍,这表明可能存在专用Python库函数的情况.

Answer 6

我可能会做这样的事情,使用带有索引参数的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.

Answer 7

这将为您提供匹配的起始索引数组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)

Answer 8

最简单的方法？

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

firstTest = text.find('test')

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