Laufzeit von python ist, wenn substring in string

Was ist die große O der folgenden if statement?

if "pl" in "apple":
   ...

Was ist das Allgemeine big O wie python bestimmt, ob die Zeichenfolge "pl" gefunden wird, in der Zeichenfolge "Apfel"

oder andere Teilzeichenfolge in der Zeichenfolge zu suchen.

Ist dies der effizienteste Weg, um zu testen, ob ein Teilstring in einem string? Hat es den gleichen Algorithmus verwenden wie .find()?

  • Was meinst du mit "wie lang ist die Laufzeit"? Wenn Sie sich Fragen, was ist schneller, man kann timeit.
  • Ich aktualisierte die Frage etwas. Sorry für unklar zu sein
  • Verwandte: Python - Kosten der find () - Funktion
InformationsquelleAutor Liondancer | 2016-02-05
  1. 8

    In python 3.4.2 es sieht aus wie Sie sind auf die gleiche Funktion, aber es kann den Unterschied im timing trotzdem. Zum Beispiel s.find erste ist erforderlich, um die lookup - find - Methode der string-und wie.

    Der verwendete Algorithmus ist eine Mischung zwischen Boyer-Mehr und Horspool.

    InformationsquelleAutor skyking
  2. 23

    Die Zeit-Komplexität ist O(N) - im Durchschnitt O(NM) schlimmsten Fall (N ist dabei die Länge des längeren Strings, M, die kürzere Zeichenfolge, die Sie suchen).

    Den gleichen Algorithmus verwendet wird, für str.index(), str.find(), str.__contains__() (die in Betreiber) und str.replace(); es ist eine Vereinfachung der Boyer-Moore mit Ideen, die aus der Boyer–Moore–Horspool und Sonntag algorithmen.

    Sehen die original stringlib Diskussion posten, sowie die fastsearch.h Quellcode; der Basis-Algorithmus hat sich nicht verändert, seit Einführung in Python 2.5 (abgesehen von einige low-level-Optimierungen und-Ecke-Fall behebt).

    Der post enthält ein Python-code-Gliederung des Algorithmus:

    def find(s, p):
    # find first occurrence of p in s
    n = len(s)
    m = len(p)
    skip = delta1(p)[p[m-1]]
    i = 0
    while i <= n-m:
        if s[i+m-1] == p[m-1]: # (boyer-moore)
            # potential match
            if s[i:i+m-1] == p[:m-1]:
                return i
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + skip # (horspool)
        else:
            # skip
            if s[i+m] not in p:
                i = i + m + 1 # (sunday)
            else:
                i = i + 1
    return -1 # not found

    sowie Geschwindigkeit Vergleiche.

    InformationsquelleAutor Martijn Pieters
  3. 4

    Können Sie timeit und testen Sie es selbst:

    maroun@DQHCPY1:~$ python -m timeit 's = "apple";s.find("pl")'
10000000 loops, best of 3: 0.125 usec per loop
maroun@DQHCPY1:~$ python -m timeit 's = "apple";"pl" in s'
10000000 loops, best of 3: 0.0371 usec per loop

    Mit in ist tatsächlich schneller (0.0371 usec verglichen werden, auf 0,125 usec).

    Für die tatsächliche Umsetzung, Sie können sich an der code selbst.

    • In Bezug auf seine Zeit-Komplexität, fand ich eine sehr gute Erklärung der here.
    InformationsquelleAutor Maroun
  4. 2

    Ich denke, der beste Weg, um herauszufinden, ist der Blick auf die Quelle. Diese sieht aus wie Sie es umsetzen würden __contains__:

    static int
bytes_contains(PyObject *self, PyObject *arg)
{
    Py_ssize_t ival = PyNumber_AsSsize_t(arg, PyExc_ValueError);
    if (ival == -1 && PyErr_Occurred()) {
        Py_buffer varg;
        Py_ssize_t pos;
        PyErr_Clear();
        if (PyObject_GetBuffer(arg, &varg, PyBUF_SIMPLE) != 0)
            return -1;
        pos = stringlib_find(PyBytes_AS_STRING(self), Py_SIZE(self),
                             varg.buf, varg.len, 0);
        PyBuffer_Release(&varg);
        return pos >= 0;
    }
    if (ival < 0 || ival >= 256) {
        PyErr_SetString(PyExc_ValueError, "byte must be in range(0, 256)");
        return -1;
    }

    return memchr(PyBytes_AS_STRING(self), (int) ival, Py_SIZE(self)) != NULL;
}

    in Bezug auf stringlib_find(), die verwendet fastsearch().

    InformationsquelleAutor Vlad
Schreibe einen Kommentar