Suchen Sie das n-te Vorkommen von Teilzeichenfolgen in einer Zeichenfolge

Dies scheint ziemlich trivial zu sein, aber ich bin neu bei Python und möchte es auf die pythonischste Art und Weise tun.

Ich möchte den Index finden, der dem n-ten Vorkommen eines Teilstrings innerhalb eines Strings entspricht.

Es muss etwas geben, das dem entspricht, was ich tun möchte, nämlich

mystring.find("substring", 2nd)

Wie können Sie dies in Python erreichen?

Marks iterativer Ansatz wäre der übliche Weg, denke ich.

Hier ist eine Alternative mit String-Aufteilung, die häufig nützlich sein kann, um verwandte Prozesse zu finden:

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)

Und hier ist ein kurzer (und etwas schmutziger, da Sie eine Spreu auswählen müssen, die nicht zur Nadel passt) Einzeiler:

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

Hier ist eine pythonischere Version der einfachen iterativen Lösung:

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

Beispiel:

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

Wenn Sie die n - te finden wollen überlappende Vorkommen needle, können Sie erhöhen , indem 1stattlen(needle) , wie folgt aus :

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

Beispiel:

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

Dies ist einfacher zu lesen als Marks Version und erfordert weder den zusätzlichen Speicher der Teilungsversion noch das Importieren eines Moduls für reguläre Ausdrücke. Im Gegensatz zu den verschiedenen Ansätzen werden auch einige Regeln im Zen of Pythonre eingehalten:

1. Einfach ist besser als komplex.
2. Wohnung ist besser als verschachtelt.
3. Lesbarkeit zählt.

Dies findet das zweite Vorkommen von Teilzeichenfolgen in Zeichenfolgen.

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

Bearbeiten: Ich habe nicht viel über die Leistung nachgedacht, aber eine schnelle Rekursion kann helfen, das n-te Vorkommen zu finden:

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)

Da Regex nicht immer die beste Lösung ist, würde ich hier wahrscheinlich eine verwenden:

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

Ich biete einige Benchmarking-Ergebnisse an, in denen die wichtigsten bisher vorgestellten Ansätze verglichen werden, nämlich @ bobince's findnth()(basierend auf str.split()) mit @ tgamblin's oder @Mark Byers find_nth()(basierend auf str.find()). Ich werde auch mit einer C-Erweiterung ( _find_nth.so) vergleichen, um zu sehen, wie schnell wir gehen können. Hier ist 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

Natürlich ist die Leistung am wichtigsten, wenn die Zeichenfolge groß ist. Nehmen wir also an, wir möchten die 1000001. erste Zeile ('\ n') in einer 1,3-GB-Datei namens 'bigfile' finden. Um Speicherplatz zu sparen, möchten wir an einer mmap.mmapObjektdarstellung der Datei arbeiten:

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)

Es gibt bereits das erste Problem mit findnth(), da mmap.mmapObjekte nicht unterstützen split(). Wir müssen also tatsächlich die gesamte Datei in den Speicher kopieren:

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

Autsch! Zum Glück spasst immer noch in die 4 GB Speicher meines Macbook Air. Lassen Sie uns also einen Benchmark erstellen findnth():

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

Offensichtlich eine schreckliche Leistung. Mal sehen, wie der darauf basierende Ansatz str.find()funktioniert:

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

Viel besser! findnth()Das Problem ist natürlich, dass es gezwungen ist, die Zeichenfolge während zu kopieren. Dies split()ist bereits das zweite Mal, dass wir die 1,3 GB Daten danach kopieren s = mm[:]. Hier kommt der zweite Vorteil von find_nth(): Wir können es mmdirekt verwenden, so dass keine Kopien der Datei erforderlich sind:

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

Es scheint eine kleine Leistungseinbuße Betriebs auf sein mmgegenüber s, aber dies zeigt , dass find_nth()uns eine Antwort in 1,2 s im Vergleich zu bekommen findnth‚s insgesamt 47 s.

Ich fand keine Fälle, in denen der str.find()basierte Ansatz signifikant schlechter war als derstr.split() basierte Ansatz, daher würde ich an dieser Stelle argumentieren, dass die Antwort von @ tgamblin oder @ Mark Byers anstelle der von @ bobince akzeptiert werden sollte.

In meinen Tests war die find_nth()obige Version die schnellste reine Python-Lösung, die ich finden konnte (sehr ähnlich der Version von @Mark Byers). Mal sehen, wie viel besser wir mit einem C-Erweiterungsmodul arbeiten können. Hier ist _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);
}

Hier ist die setup.pyDatei:

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

Installieren Sie wie gewohnt mit python setup.py install. Der C-Code spielt hier eine Rolle, da er sich darauf beschränkt, einzelne Zeichen zu finden. Mal sehen, wie schnell dies geht:

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

Klar noch ein bisschen schneller. Interessanterweise gibt es auf C-Ebene keinen Unterschied zwischen In-Memory- und Mmapped-Fällen. Es ist auch interessant zu sehen, dass das _find_nth2(), was auf string.hder memchr()Bibliotheksfunktion basiert , gegen die unkomplizierte Implementierung in verliert _find_nth(): Die zusätzlichen "Optimierungen" in memchr()sind anscheinend nach hinten los ...

Zusammenfassend ist die Implementierung in findnth()(basierend auf str.split()) wirklich eine schlechte Idee, da (a) sie aufgrund des erforderlichen Kopierens für größere Zeichenfolgen eine schreckliche Leistung erbringt und (b) überhaupt nicht für mmap.mmapObjekte funktioniert . Die Implementierung in find_nth()(basierend auf str.find()) sollte unter allen Umständen bevorzugt werden (und daher die akzeptierte Antwort auf diese Frage sein).

Es gibt noch viel Raum für Verbesserungen, da die C-Erweiterung fast um den Faktor 4 schneller lief als der reine Python-Code, was darauf hinweist, dass möglicherweise eine dedizierte Python-Bibliotheksfunktion vorliegt.

Einfachster Weg?

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

firstTest = text.find('test')

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

Ich würde wahrscheinlich so etwas mit der Suchfunktion machen, die einen Indexparameter akzeptiert:

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)

Es ist nicht besonders pythonisch, aber es ist einfach. Sie können dies stattdessen mit Rekursion tun:

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)

Es ist ein funktionaler Weg, um es zu lösen, aber ich weiß nicht, ob es dadurch pythonischer wird.

Dadurch erhalten Sie eine Reihe von Startindizes für Übereinstimmungen mit yourstring:

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

Dann wäre Ihr n-ter Eintrag:

n = 2
nth_entry = indices[n-1]

Natürlich muss man mit den Indexgrenzen vorsichtig sein. Sie können die Anzahl der Instanzen yourstringwie folgt ermitteln:

num_instances = len(indices)

Hier ist ein anderer Ansatz mit re.finditer.
Der Unterschied besteht darin, dass dies nur so weit wie nötig in den Heuhaufen schaut

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

Hier ist eine weitere re+ itertoolsVersion, die bei der Suche nach a stroder a funktionieren sollte RegexpObject. Ich werde frei zugeben, dass dies wahrscheinlich überarbeitet ist, aber aus irgendeinem Grund hat es mich unterhalten.

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

Aufbauend auf der Antwort von modle13 , jedoch ohne die Modulabhängigkeitre .

def iter_find(haystack, needle):
    return [i for i in range(0, len(haystack)) if haystack[i:].startswith(needle)]

Ich wünschte, dies wäre eine eingebaute String-Methode.

>>> iter_find("http://stackoverflow.com/questions/1883980/", '/')
[5, 6, 24, 34, 42]

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

Bereitstellung einer weiteren "kniffligen" Lösung, die splitund verwendetjoin .

In Ihrem Beispiel können wir verwenden

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

# 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

Lösung ohne Schleifen und Rekursion.

Verwenden Sie das erforderliche Muster in der Kompilierungsmethode und geben Sie das gewünschte Vorkommen in die Variable 'n' ein. Die letzte Anweisung gibt den Startindex des n-ten Vorkommens des Musters in der angegebenen Zeichenfolge aus. Hier wird das Ergebnis des Finditer, dh des Iterators, in eine Liste konvertiert und greift direkt auf den n-ten Index zu.

import re
n=2
sampleString="this is history"
pattern=re.compile("is")
matches=pattern.finditer(sampleString)
print(list(matches)[n].span()[0])

Der Ersatz-Liner ist großartig, funktioniert aber nur, weil XX und Bar die gleiche Länge haben

Ein guter und allgemeiner Def wäre:

def findN(s,sub,N,replaceString="XXX"):
    return s.replace(sub,replaceString,N-1).find(sub) - (len(replaceString)-len(sub))*(N-1)

Dies ist die Antwort, die Sie wirklich wollen:

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

Hier ist meine Lösung, um das nVorkommen von bin string zu finden 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)

Es ist reines Python und iterativ. Für 0 oder nzu groß wird -1 zurückgegeben. Es ist einzeilig und kann direkt verwendet werden. Hier ist ein Beispiel:

>>> reduce(lambda x, y: -1 if y > x + 1 else 'bibarbobaobaotang'.find('b', x + 1), range(4), -1)
7

Für den Sonderfall, in dem Sie nach dem n-ten Vorkommen eines Zeichens suchen (dh Teilzeichenfolge der Länge 1), erstellt die folgende Funktion eine Liste aller Vorkommenspositionen des angegebenen Zeichens:

def find_char_nth(string, char, n):
    """Find the n'th occurence of a character within a string."""
    return [i for i, c in enumerate(string) if c == char][n-1]

Wenn es weniger als nVorkommen des angegebenen Zeichens gibt, gibt es IndexError: list index out of range.

Dies wird aus der Antwort von @ Zv_oDD abgeleitet und für den Fall eines einzelnen Zeichens vereinfacht.

Def:

def get_first_N_words(mytext, mylen = 3):
    mylist = list(mytext.split())
    if len(mylist)>=mylen: return ' '.join(mylist[:mylen])

Benutzen:

get_first_N_words('  One Two Three Four ' , 3)

Ausgabe:

'One Two Three'

Wie wäre es mit:

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