Какова продолжительность работы полосы Python ()?

Question

Какова продолжительность работы полосы Python ()?

Поскольку remove - это O(n) для одного символа, является ли полоса O(n^2) для строки?

Answer 1

Это также только O(N). Цитирование кода, соответствующего равнине strip которая убирает пробелы, с версии 2.7.9

Py_LOCAL_INLINE(PyObject *)
do_strip(PyStringObject *self, int striptype)
{
    char *s = PyString_AS_STRING(self);
    Py_ssize_t len = PyString_GET_SIZE(self), i, j;

    i = 0;
    if (striptype != RIGHTSTRIP) {
        while (i < len && isspace(Py_CHARMASK(s[i]))) {
            i++;
        }
    }

    j = len;
    if (striptype != LEFTSTRIP) {
        do {
            j--;
        } while (j >= i && isspace(Py_CHARMASK(s[j])));
        j++;
    }

    if (i == 0 && j == len && PyString_CheckExact(self)) {
        Py_INCREF(self);
        return (PyObject*)self;
    }
    else
        return PyString_FromStringAndSize(s+i, j-i);
}

Сначала он начинается слева и увеличивает переменную i до тех пор, пока не найдет непробельный символ, а затем начнется справа и уменьшится j пока он не найдет непробельный символ. И, наконец, строка между i а также j возвращается с этим

PyString_FromStringAndSize(s+i, j-i)

Но с другой стороны, strip который удаляет набор символов, немного сложен, но довольно похож.

Py_LOCAL_INLINE(PyObject *)
do_xstrip(PyStringObject *self, int striptype, PyObject *sepobj)
{
    char *s = PyString_AS_STRING(self);
    Py_ssize_t len = PyString_GET_SIZE(self);
    char *sep = PyString_AS_STRING(sepobj);
    Py_ssize_t seplen = PyString_GET_SIZE(sepobj);
    Py_ssize_t i, j;

    i = 0;
    if (striptype != RIGHTSTRIP) {
        while (i < len && memchr(sep, Py_CHARMASK(s[i]), seplen)) {
            i++;
        }
    }

    j = len;
    if (striptype != LEFTSTRIP) {
        do {
            j--;
        } while (j >= i && memchr(sep, Py_CHARMASK(s[j]), seplen));
        j++;
    }

    if (i == 0 && j == len && PyString_CheckExact(self)) {
        Py_INCREF(self);
        return (PyObject*)self;
    }
    else
        return PyString_FromStringAndSize(s+i, j-i);
}

Он такой же, как предыдущий, но имеет memchr(sep, Py_CHARMASK(s[j]), seplen) проверяй каждый раз. Таким образом, временная сложность этого становится O(N * M), где M длина фактической строки символов, которые будут удалены.