문자열에서 n 번째 하위 문자열 찾기
이것은 매우 사소한 것처럼 보이지만 저는 Python을 처음 접했고 가장 Pythonic 방식으로하고 싶습니다.
문자열에서 n 번째 발생하는 부분 문자열을 찾고 싶습니다.
내가하고 싶은 것과 동등한 것이 있어야합니다.
mystring.find("substring", 2nd)
파이썬에서 어떻게 이것을 달성 할 수 있습니까?
Mark의 반복적 인 접근 방식은 일반적인 방법이라고 생각합니다.
다음은 관련 프로세스를 찾는 데 유용 할 수있는 문자열 분할의 대안입니다.
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')
다음은 간단한 반복 솔루션의 Python 버전입니다.
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증가 할 수 있습니다 .1len(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의 버전보다 읽기 쉽고 분할 버전이나 정규 표현식 모듈 가져 오기의 추가 메모리가 필요하지 않습니다. 또한 다양한 접근 방식 과 달리 Zen of python 의 몇 가지 규칙을 준수합니다 re.
- 단순한 것이 복잡한 것보다 낫습니다.
- 플랫이 중첩보다 낫습니다.
- 가독성이 중요합니다.
문자열에서 두 번째 하위 문자열을 찾습니다.
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)
정규식이 항상 최선의 해결책은 아니라는 것을 이해하고 여기에서 사용할 것입니다.
>>> 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
지금까지 제시된 가장 눈에 띄는 접근 방식, 즉 @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 라이브러리 함수에 대한 사례가있을 수 있으므로 개선 할 여지가 여전히 많이 있습니다.
색인 매개 변수를 사용하는 찾기 함수를 사용하여 다음과 같이 할 수 있습니다.
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하게 만드는지 모르겠습니다.
가장 간단한 방법?
text = "This is a test from a test ok"
firstTest = text.find('test')
print text.find('test', firstTest + 1)
a 또는 a를 검색 할 때 작동해야하는 또 다른 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
Here is another approach using re.finditer.
The difference is that this only looks into the haystack as far as necessary
from re import finditer
from itertools import dropwhile
needle='an'
haystack='bananabanana'
n=2
next(dropwhile(lambda x: x[0]<n, enumerate(re.finditer(needle,haystack))))[1].start()
>>> 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
This will give you an array of the starting indices for matches to yourstring:
import re
indices = [s.start() for s in re.finditer(':', yourstring)]
Then your nth entry would be:
n = 2
nth_entry = indices[n-1]
Of course you have to be careful with the index bounds. You can get the number of instances of yourstring like this:
num_instances = len(indices)
Building on modle13's answer, but without the re module dependency.
def iter_find(haystack, needle):
return [i for i in range(0, len(haystack)) if haystack[i:].startswith(needle)]
I kinda wish this was a builtin string method.
>>> iter_find("http://stackoverflow.com/questions/1883980/", '/')
[5, 6, 24, 34, 42]
# 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
The replace one liner is great but only works because XX and bar have the same lentgh
A good and general def would be:
def findN(s,sub,N,replaceString="XXX"):
return s.replace(sub,replaceString,N-1).find(sub) - (len(replaceString)-len(sub))*(N-1)
Providing another "tricky" solution, which use split and join.
In your example, we can use
len("substring".join([s for s in ori.split("substring")[:2]]))
This is the answer you really want:
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
Solution without using loops and recursion.
Use the required pattern in compile method and enter the desired occurrence in variable 'n' and the last statement will print the starting index of the nth occurrence of the pattern in the given string. Here the result of finditer i.e. iterator is being converted to list and directly accessing the nth index.
import re
n=2
sampleString="this is history"
pattern=re.compile("is")
matches=pattern.finditer(sampleString)
print(list(matches)[n].span()[0])
Here is my solution for finding nth occurrance of b in string a:
from functools import reduce
def findNth(a, b, n):
return reduce(lambda x, y: -1 if y > x + 1 else a.find(b, x + 1), range(n), -1)
It is pure Python and iterative. For 0 or n that is too large, it returns -1. It is one-liner and can be used directly. Here is an example:
>>> reduce(lambda x, y: -1 if y > x + 1 else 'bibarbobaobaotang'.find('b', x + 1), range(4), -1)
7
How about:
c = os.getcwd().split('\\')
print '\\'.join(c[0:-2])
참고URL : https://stackoverflow.com/questions/1883980/find-the-nth-occurrence-of-substring-in-a-string
'developer tip' 카테고리의 다른 글
| AltGr 키가 작동하지 않습니다. 대신 Ctrl + AltGr [닫힘]을 사용해야합니다. (0) | 2020.08.13 |
|---|---|
| Cygwin에서 파일 열기 (0) | 2020.08.13 |
| 개조를 사용하여 GSON으로 중첩 된 JSON 개체 가져 오기 (0) | 2020.08.13 |
| 언제 Theme.AppCompat와 ThemeOverlay.AppCompat를 사용해야합니까? (0) | 2020.08.13 |
| asp.net mvc를 사용하여 하이픈으로 연결된 HTML 속성 (0) | 2020.08.13 |