What is the time/space complexity of split/strip/open (in-built python functions)?
Does anyone know where i can look up on the time/space complexity of these functions?
-
2I do not know where you can find that information, but couldn't you just time the functions yourself and then plot the results on a graph and see if it is linear/parabolic/etc..?Reedinationer– Reedinationer2019-03-12 03:34:00 +00:00Commented Mar 12, 2019 at 3:34
-
2wiki.python.org/moin/TimeComplexityRocky Li– Rocky Li2019-03-12 04:00:47 +00:00Commented Mar 12, 2019 at 4:00
-
1@RockyLi has the exact answer to the question, don't bother with timing or anything like that unless you need an empirical result instead of a formal statement.Grismar– Grismar2019-03-12 04:25:02 +00:00Commented Mar 12, 2019 at 4:25
Add a comment
|
1 Answer
The exact answer will depend on what properties are fed into the function. The easiest way to find out would probably be to examine the source code for those functions. The python source code can be found here.
Lets take a look at the source for split. The code runs different loops depending on the properties. This is the loop for splitting by whitespace.
while (maxcount-- > 0) {
while (i < str_len && STRINGLIB_ISSPACE(str[i]))
i++;
if (i == str_len) break;
j = i; i++;
while (i < str_len && !STRINGLIB_ISSPACE(str[i]))
i++;
In this code, the function will look at each character in the string (unless the maxcount is reached). The inner most loops will run n times for a string of size n. Time complexity is O(n)
The source for strip steps through each character in the string.
i = 0;
if (striptype != RIGHTSTRIP) {
while (i < len) {
Py_UCS4 ch = PyUnicode_READ(kind, data, i);
if (!BLOOM(sepmask, ch))
break;
if (PyUnicode_FindChar(sepobj, ch, 0, seplen, 1) < 0)
break;
i++;
}
}
j = len;
if (striptype != LEFTSTRIP) {
j--;
while (j >= i) {
Py_UCS4 ch = PyUnicode_READ(kind, data, j);
if (!BLOOM(sepmask, ch))
break;
if (PyUnicode_FindChar(sepobj, ch, 0, seplen, 1) < 0)
break;
j--;
}
j++;
}
This gives strip a time complexity of O(n).
The Source for open() shows no loops. This is what we would expect. There is nothing to loop through.
1 Comment
noobprogrammer
Thanks a lot! Really helped me clarify the time complexity of those in built functions!