[python] 문자열에서 n 번째 부분 문자열 찾기

지금까지 제시된 가장 눈에 띄는 접근 방식, 즉 @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.3GB 파일에서 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.mmapsplit()

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의 4GB 메모리에 맞으므로 벤치 마크를 해보겠습니다 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.3GB의 데이터를 복사 한 것은 이미 두 번째 인 동안 문자열을 복사해야한다는 것입니다 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에서 작동하는 약간의 성능 저하가있는 것으로 보이지만 이는 의 총 47 초에 find_nth()비해 1.2 초 안에 답을 얻을 수 있음을 보여줍니다 findnth.

str.find()기반 접근 방식이 기반 접근 방식보다 훨씬 더 나쁜 경우를 발견하지 못 str.split()했으므로이 시점에서 @bobince 대신 @tgamblin 또는 @Mark Byers의 답변을 수락해야한다고 주장합니다.

내 테스트에서 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.hmemchr()_find_nth()memchr()

결론적으로 findnth()(기반 str.split()) 의 구현은 ( a) 필요한 복사로 인해 더 큰 문자열에 대해 끔찍하게 수행되고 (b) mmap.mmap객체에서 전혀 작동하지 않기 때문에 정말 나쁜 생각 입니다. find_nth()(기반 str.find()) 의 구현은 모든 상황에서 선호되어야합니다 (따라서이 질문에 대한 대답이 허용됨).

C 확장은 순수한 Python 코드보다 거의 4 배 더 빠르게 실행되어 전용 Python 라이브러리 함수에 대한 사례가있을 수 있으므로 개선의 여지가 여전히 많이 있습니다.

답변

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

firstTest = text.find('test')

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

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)

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)