Consider a python line:
str[::-1]
I see it's very fast, and way more faster than some O(n) solution and also memory saving. What algorithm does Python use in this case?
Add a comment
|
2 Answers
Hmm, have you tried any quick-and-dirty tests? Here is a first-pass:
In [1]: import time
In [2]: def reverse_list_time(my_list):
...: start = time.time()
...: reversed = my_list[::-1]
...: stop = time.time()
...: return stop - start
...:
In [3]: reverse_list_time(list(range(1000)))
Out[3]: 1.33514404296875e-05
In [4]: testing_lists = (list(range(n)) for n in range(1000,100000,500))
In [5]: testing_lists
Out[5]: <generator object <genexpr> at 0x7f7786bd97d8>
In [6]: results = list(map(reverse_list_time,testing_lists))
And here are my results
That looks roughly O(n) to me.
If that doesn't convince you, here is the implementation. It looks like a pretty straight forward O(n) solution to me. This is the meat of it: else {
result = PyList_New(slicelength);
if (!result) return NULL;
src = self->ob_item;
dest = ((PyListObject *)result)->ob_item;
for (cur = start, i = 0; i < slicelength;
cur += step, i++) {
it = src[cur];
Py_INCREF(it);
dest[i] = it;
}
return result;
answered Jul 3, 2016 at 4:35
juanpa.arrivillaga
97.7k14 gold badges141 silver badges190 bronze badges
Comments
You can use Python's dis.dis module to disassemble str[::-1]:
>>> import dis
>>> def reverse_(str_):
... return str_[::-1]
...
>>> dis.dis(reverse_)
6 0 LOAD_FAST 0 (str_)
3 LOAD_CONST 0 (None)
6 LOAD_CONST 0 (None)
9 LOAD_CONST 1 (-1)
12 BUILD_SLICE 3
15 BINARY_SUBSCR
16 RETURN_VALUE
You can see what each instruction means in the documentation. For LOAD_FAST the docs say:
Pushes a reference to the local
co_varnames[var_num]onto the stack.
co_varnames is a structure that is always present with a code object. In this case, it is str_:
>>> reverse_.__code__.co_varnames
('str_',)
The next instruction, LOAD_CONST, is described like this:
Pushes
co_consts[consti]onto the stack.
The value that was pushed onto the stack is None (dis is helpful and looked it up for you). The next two instructions are LOAD_CONST instructions that push the values None and -1 onto the stack.
The next instruction, BUILD_SLICE, is described as:
Pushes a slice object on the stack. argc must be 2 or 3. If it is 2,
slice(TOS1, TOS)is pushed; if it is 3,slice(TOS2, TOS1, TOS)is pushed. See theslice()built-in function for more information.
TOS2, TOS1, TOS represent the values on the stack None, None, -1, which are pushed to the slice() object from the stack (the object becomes slice(None, None, -1)).
BINARY_SUBSCR is described as:
Implements
TOS = TOS1[TOS].
This means that Python computes str_[sli] where sli is the slice() object pushed to the stack in the previous instruction. It's the equivalent of
>>> str_[slice(None, None, -1)]
Finally, RETURN_VALUE:
Returns with TOS to the caller of the function.
The last instruction returns the result of the previous step, which is the reversed str_.
Summary
I see it's very fast, and way more faster than some O(n) solution and also memory saving.
In fact, reversing a list by slicing involves more memory overhead than some other reversal methods in Python. Long story short (and without going down a long rabbit hole), the greater memory overhead occurs because the slicing operation returns a whole list.
One alternative method might be: generating an iterator using reversed(), which is usually more performant for memory and time (although, generating a list from this iterator is time-consuming).
What algorithm does Python use in this case?
To make a long story short: Python loads the variable str, builds a slice(None, None, -1) object, implements str[slice(None, None, -1)] (source code), and returns the reversed str.
