python之Python 的 strip() 的运行时间是多少

Python 的 strip() 的运行时间是多少？

既然 remove 对于单个 char 是 O(n)，那么对于 string strip 是 O(n^2) 吗？

请您参考如下方法:

它也是 O(N) 而已。引用与去除空格的普通 strip 相对应的代码，from the version 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) 

但另一方面，the strip which removes the set of characters , 稍微复杂但相当相似。

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 是要剥离的实际字符串的长度。