Python 的 strip() 的运行时间是多少? [英] What's the runtime of Python's strip()?
问题描述
Python 的 strip() 的运行时间是多少?
What's the runtime of Python's strip()?
因为单个字符的remove是O(n),那么字符串的strip O(n^2)是吗?
Since remove is O(n) for a single char, is strip O(n^2) for a string?
推荐答案
它也只是 O(N).引用与去除空格的纯 strip
对应的代码,来自 2.7.9 版
It is also O(N) only. Quoting the code corresponding to the plain strip
which strips the spaces, 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
之间的字符串与 this
It first starts from the left and increments the variable i
, till it finds a non-space character and then it starts from the right and decrements j
till it finds a non-space character. And finally the string between i
and j
is returned with this
PyString_FromStringAndSize(s+i, j-i)
但另一方面,strip
删除字符集,有点复杂,但非常相似.
But on the other hand, the strip
which removes the set of characters, is slightly complicated but fairly similar.
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
是要剥离的实际字符串的长度.
It is the same as the previous one, but it has the extra memchr(sep, Py_CHARMASK(s[j]), seplen)
check every time. So, the time complexity of this becomes O(N * M), where M
is the length of the actual string of characters to be stripped.
这篇关于Python 的 strip() 的运行时间是多少?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!