Temukan kemunculan substring ke-n dalam sebuah string

Sepertinya ini cukup sepele, tetapi saya baru di Python dan ingin melakukannya dengan cara yang paling Pythonic.

Saya ingin mencari indeks yang sesuai dengan kejadian n'th dari substring dalam sebuah string.

Pasti ada sesuatu yang setara dengan apa yang AKU INGIN lakukan yaitu

mystring.find("substring", 2nd)

Bagaimana Anda bisa mencapai ini dengan Python?

Pendekatan berulang Mark akan menjadi cara yang biasa, saya pikir.

Berikut adalah alternatif dengan pemisahan string, yang sering kali berguna untuk menemukan proses terkait:

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)

Dan inilah cara cepat (dan agak kotor, karena Anda harus memilih sekam yang tidak bisa cocok dengan jarum) satu baris:

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

Berikut adalah versi yang lebih Pythonic dari solusi iteratif langsung:

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

Contoh:

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

Jika Anda ingin menemukan kejadian tumpang tindih ke-n needle, Anda dapat menambahnya 1alih-alih len(needle), seperti ini:

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

Contoh:

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

Ini lebih mudah dibaca daripada versi Mark, dan tidak memerlukan memori tambahan dari versi pemisahan atau pengimporan modul ekspresi reguler. Itu juga mematuhi beberapa aturan di Zen of python , tidak seperti berbagai rependekatan:

1. Sederhana lebih baik daripada kompleks.
2. Datar lebih baik dari pada bersarang.
3. Keterbacaan itu penting.

Ini akan menemukan kemunculan kedua substring dalam string.

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

Sunting: Saya belum terlalu memikirkan kinerjanya, tetapi rekursi cepat dapat membantu menemukan kejadian ke-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)

Memahami bahwa regex tidak selalu merupakan solusi terbaik, saya mungkin akan menggunakannya di sini:

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

Saya menawarkan beberapa hasil pembandingan yang membandingkan pendekatan paling menonjol yang disajikan sejauh ini, yaitu @ bobince findnth()(berdasarkan str.split()) vs. @ tgamblin atau @Mark Byers ' find_nth()(berdasarkan str.find()). Saya juga akan membandingkan dengan ekstensi C ( _find_nth.so) untuk melihat seberapa cepat kita bisa pergi. Ini dia 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

Tentu saja, kinerja paling penting jika stringnya besar, jadi misalkan kita ingin mencari baris baru ke-1000001 ('\ n') dalam file 1,3 GB yang disebut 'bigfile'. Untuk menghemat memori, kami ingin mengerjakan mmap.mmaprepresentasi objek dari file:

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)

Sudah ada masalah pertama dengan findnth(), karena mmap.mmapobjek tidak mendukung split(). Jadi kami sebenarnya harus menyalin seluruh file ke dalam memori:

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

Aduh! Untungnya smasih muat di memori 4 GB Macbook Air saya, jadi mari benchmark findnth():

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

Performa yang jelas mengerikan. Mari kita lihat bagaimana pendekatan berdasarkan str.find()itu:

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

Jauh lebih baik! Jelas, findnth()masalahnya adalah bahwa string dipaksa untuk menyalin selama split(), yang sudah kedua kalinya kami menyalin 1,3 GB data setelahnya s = mm[:]. Inilah keuntungan kedua dari find_nth(): Kita dapat menggunakannya secara mmlangsung, sehingga tidak ada salinan file yang diperlukan:

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

Tampaknya ada hukuman kinerja kecil yang beroperasi pada mmvs. s, tetapi ini menggambarkan bahwa find_nth()dapat memberi kita jawaban dalam 1,2 d dibandingkan dengan findnthtotal 47 d.

Saya tidak menemukan kasus di mana str.find()pendekatan berbasis secara signifikan lebih buruk daripada str.split()pendekatan berbasis, jadi pada titik ini, saya berpendapat bahwa jawaban @ tgamblin atau @Mark Byers harus diterima daripada @ bobince.

Dalam pengujian saya, versi di find_nth()atas adalah solusi Python murni tercepat yang dapat saya buat (sangat mirip dengan versi @Mark Byers). Mari kita lihat seberapa baik yang bisa kita lakukan dengan modul ekstensi C. Ini dia _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);
}

Ini setup.pyfilenya:

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

Instal seperti biasa dengan python setup.py install. Kode C memainkan keuntungan di sini karena terbatas pada menemukan karakter tunggal, tetapi mari kita lihat seberapa cepat ini:

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

Jelas masih lebih cepat. Menariknya, tidak ada perbedaan pada level C antara in-memory dan case mmapped. Hal ini juga menarik untuk melihat bahwa _find_nth2(), yang didasarkan pada string.h's memchr()fungsi perpustakaan, kehilangan menentang pelaksanaan langsung di _find_nth(): The tambahan 'optimasi' di memchr()rupanya knalpot ...

Kesimpulannya, implementasi dalam findnth()(berdasarkan str.split()) benar-benar ide yang buruk, karena (a) ia bekerja sangat buruk untuk string yang lebih besar karena penyalinan yang diperlukan, dan (b) tidak bekerja pada mmap.mmapobjek sama sekali. Penerapan dalam find_nth()(berdasarkan str.find()) harus diutamakan dalam semua keadaan (dan karena itu menjadi jawaban yang diterima untuk pertanyaan ini).

Masih ada sedikit ruang untuk perbaikan, karena ekstensi C berjalan hampir 4 kali lipat lebih cepat daripada kode Python murni, menunjukkan bahwa mungkin ada kasus untuk fungsi pustaka Python khusus.

Cara paling sederhana?

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

firstTest = text.find('test')

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

Saya mungkin akan melakukan sesuatu seperti ini, menggunakan fungsi find yang mengambil parameter indeks:

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)

Kurasa tidak terlalu Pythonic, tapi sederhana. Anda dapat melakukannya dengan menggunakan rekursi:

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)

Ini cara fungsional untuk mengatasinya, tapi saya tidak tahu apakah itu membuatnya lebih Pythonic.

Ini akan memberi Anda larik indeks awal untuk kecocokan dengan yourstring:

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

Maka entri ke-n Anda adalah:

n = 2
nth_entry = indices[n-1]

Tentu saja Anda harus berhati-hati dengan batas indeks. Anda bisa mendapatkan jumlah contoh yourstringseperti ini:

num_instances = len(indices)

Berikut adalah pendekatan lain menggunakan re.finditer.
Perbedaannya adalah bahwa ini hanya melihat tumpukan jerami sejauh yang diperlukan

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

Berikut re+ itertoolsversi lain yang seharusnya berfungsi saat menelusuri a stratau a RegexpObject. Saya akan dengan bebas mengakui bahwa ini kemungkinan besar direkayasa, tetapi untuk beberapa alasan itu menghibur saya.

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

Membangun dari jawaban modle13 , tetapi tanpa reketergantungan modul.

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

Saya agak berharap ini adalah metode string bawaan.

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

Memberikan solusi lain yang "rumit", yang menggunakan splitdan join.

Dalam contoh Anda, kami dapat menggunakan

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

Solusi tanpa menggunakan loop dan rekursi.

Gunakan pola yang diperlukan dalam metode kompilasi dan masukkan kemunculan yang diinginkan dalam variabel 'n' dan pernyataan terakhir akan mencetak indeks awal kemunculan n pola dalam string yang diberikan. Di sini hasil finditer yaitu iterator diubah menjadi daftar dan langsung mengakses indeks ke-n.

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

Untuk kasus khusus di mana Anda mencari kemunculan n'th dari sebuah karakter (yaitu substring dengan panjang 1), fungsi berikut bekerja dengan membuat daftar dari semua posisi kemunculan karakter yang diberikan:

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]

Jika ada lebih sedikit dari nkemunculan karakter yang diberikan, itu akan memberi IndexError: list index out of range.

Ini berasal dari jawaban @ Zv_oDD dan disederhanakan untuk kasus satu karakter.

Ganti satu liner bagus tetapi hanya berfungsi karena XX dan bar memiliki lentgh yang sama

Definisi yang baik dan umum adalah:

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

Inilah jawaban yang sangat Anda inginkan:

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

Inilah solusi saya untuk menemukan nkemunculan bdalam 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)

Ini adalah Python murni dan berulang. Untuk 0 atau nyang terlalu besar, ia mengembalikan -1. Ini adalah satu baris dan dapat digunakan secara langsung. Berikut ini contohnya:

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

Def:

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

Menggunakan:

get_first_N_words('  One Two Three Four ' , 3)

Keluaran:

'One Two Three'

Bagaimana tentang:

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