Trouver la nième occurrence d'une sous-chaîne dans une chaîne de caractères.

Question

Cela semble devoir être assez trivial, mais je suis nouveau en Python et je veux le faire de la manière la plus pythonique possible.

Je veux trouver l'index correspondant à la nième occurrence d'une sous-chaîne dans une chaîne de caractères.

Il doit bien y avoir quelque chose d'équivalent à ce que je VEUX faire, c'est-à-dire

mystring.find("substring", 2nd)

Comment réaliser cela en Python ?

Answer 1

Voici une version plus pythique de la solution itérative directe :

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

Exemple :

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

Si vous voulez trouver le nième chevauchement l'apparition de needle vous pouvez l'incrémenter par 1 au lieu de len(needle) comme ceci :

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

Exemple :

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

Cette version est plus facile à lire que celle de Mark, et elle ne nécessite pas la mémoire supplémentaire de la version de fractionnement ou l'importation du module d'expression régulière. Elle adhère également à quelques règles de la norme Zen de python contrairement aux différents re approches :

1. La simplicité est préférable à la complexité.
2. Le plat est meilleur que l'imbriqué.
3. La lisibilité compte.

Answer 2

L'approche itérative de Mark serait la méthode habituelle, je pense.

Voici une alternative avec le fractionnement des chaînes de caractères, qui peut souvent être utile pour les processus de recherche :

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)

Et voici une phrase rapide (et un peu sale, dans la mesure où vous devez choisir des paillettes qui ne peuvent pas correspondre à l'aiguille) :

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

Answer 3

Cela permettra de trouver la deuxième occurrence de la sous-chaîne dans la chaîne.

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

Edit : Je n'ai pas beaucoup pensé aux performances, mais une récursion rapide peut aider à trouver la nième occurrence :

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

Sachant que les expressions rationnelles ne sont pas toujours la meilleure solution, j'en utiliserais probablement une ici :

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

Je vous propose quelques résultats d'analyse comparative des approches les plus importantes présentées jusqu'à présent, à savoir la méthode de @bobince findnth() (sur la base de str.split() ) contre ceux de @tgamblin ou @Mark Byers find_nth() (sur la base de str.find() ). Je vais également comparer avec une extension C ( _find_nth.so ) pour voir à quelle vitesse on peut aller. Voici 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

Bien sûr, les performances sont plus importantes si la chaîne de caractères est grande. Supposons que nous voulions trouver le 1000001e saut de ligne ('). \n ) dans un fichier de 1,3 Go appelé 'bigfile'. Pour économiser de la mémoire, nous souhaitons travailler sur un fichier mmap.mmap représentation objet du fichier :

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)

Il y a déjà un premier problème avec findnth() puisque mmap.mmap les objets ne supportent pas split() . Nous devons donc copier tout le fichier en mémoire :

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

Aïe ! Heureusement, s tient toujours dans les 4 Go de mémoire de mon Macbook Air. findnth() :

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

C'est clairement une performance terrible. Voyons comment l'approche basée sur str.find() fait :

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

Beaucoup mieux ! Clairement, findnth() Le problème de l'utilisateur est qu'il est obligé de copier la chaîne de caractères pendant que split() c'est déjà la deuxième fois que nous copions les 1,3 Go de données après s = mm[:] . C'est là qu'intervient le deuxième avantage de find_nth() : On peut l'utiliser sur mm directement, de sorte que zéro copies du fichier sont nécessaires :

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

Il semble qu'il y ait une petite pénalité de performance en fonctionnant sur mm vs. s mais cela illustre le fait que find_nth() peut nous obtenir une réponse en 1,2 s par rapport à findnth Le total de 47 s de l'UE.

Je n'ai trouvé aucun cas où le str.find() était nettement moins bonne que l'approche str.split() Donc, à ce stade, je dirais que la réponse de @tgamblin ou de @Mark Byers devrait être acceptée au lieu de celle de @bobince.

Dans mes tests, la version de find_nth() Ce qui précède était la solution Python pure la plus rapide que j'ai pu trouver (très similaire à la version de @Mark Byers). Voyons à quel point nous pouvons faire mieux avec un module d'extension C. Voici _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);
}

Voici le setup.py fichier :

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

Installer comme d'habitude avec python setup.py install . Le code C est ici avantagé puisqu'il est limité à la recherche de caractères uniques, mais voyons à quel point cela est rapide :

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

Clairement un peu plus rapide encore. Il est intéressant de noter qu'il n'y a pas de différence au niveau C entre les cas en mémoire et en mappe. Il est également intéressant de voir que _find_nth2() qui est basé sur string.h 's memchr() perd face à la mise en œuvre simple de la fonction de la bibliothèque. _find_nth() : Les "optimisations" supplémentaires dans memchr() sont apparemment en train de se retourner contre eux...

En conclusion, la mise en œuvre dans findnth() (sur la base de str.split() ) est vraiment une mauvaise idée, car (a) elle est très peu performante pour les grandes chaînes de caractères en raison de la copie nécessaire, et (b) elle ne fonctionne pas sur mmap.mmap objets du tout. L'implémentation dans find_nth() (sur la base de str.find() ) devrait être préféré en toutes circonstances (et donc être la réponse acceptée à cette question).

Il y a encore beaucoup de place pour l'amélioration, puisque l'extension C s'est exécutée presque un facteur 4 plus rapidement que le code Python pur, indiquant qu'il pourrait y avoir un cas pour une fonction de bibliothèque Python dédiée.