Bottom line of this wall of text:
The quoted code (above) is a catastrophically slow implementation of
reverse. I don't have a good suggestion for the exercise, but see my one-line suggestions further down for how one should reverse a string. Ignore the fact that they are shorter, they are far faster for large strings.
If the length of
text is one million (could be a book, right?), then on average
rev would contain half a million characters each iteration of that loop.
Strings are immutable. So adding a character means creating a copy of the old string, with the new character added. A million characters to add, with an average of half a million characters to copy each time, you do the math. And what if it's far longer than a million? The number of operations required is in the order of
len(text) * len(text) (Should be in the order of
len(text), the number of characters, since it shouldn't matter how long the string is, it should still take the same amount of time per character to reverse it.)
These four lines would take far longer to execute than what's reasonable (reasonable is less than a second)
text = 'a' * 1000000 # A string of one million a's
result = ''
for char in text:
result = char + result
For the purpose of the exercise, I suppose it's okay, especially considering that the alternative using only what's taught in the course is quite ugly:
rev = 
for i in range(len(text)-1, -1, -1):
I don't expect many to come up with that, some of that might not even precede this exercise. The reason for not iterating "forwards" through
text is that inserting in the front of a list involves moving all the already existing elements to make room in the first location of the list (the front). One could use a data structure other than list, one that supports both iteration and fast insertion at the front (for example a linked list) but that's even more complicated, and not an improvement regardless.
In "real" code, one would do one of:
# built-in function `reversed`
# list slicing (works on strings too)
But of course they aren't much sport for the exercise.
There's no nice way to implement it ourselves in Python, because there's no need for it, it'd just be re-inventing the wheel, and a worse wheel at that (can't beat built-in functions in speed, they are written in C (not Python) by somebody who actually thought things through)
To make this even more complicated, the following would actually be fast, despite what I just said:
text = 'a' * 1000000
result = ''
for char in text:
result += char
The difference is that this just copies, without reversing. Strings are immutable and you shouldn't think of them as anything else. So "appending" is slow, as just explained. But in this case, Python, or to be more specific, CPython (There are several Python implementations, CPython is the most widely used one, but not the only one!) will exploit that there is only a single reference to the string,
result. This means that in this case there won't be any side-effects of actually changing the string, despite that strings are supposed to be immutable. This probably also only works for adding at the end of the string, so this performance hack doesn't help much/at all for the quoted function.
Other implementations may not have this performance hack, and actually do as promised, which is to make a huge amount of copies. (My local installs of Jython and PyPy do not appear to have this performance hack)
So while this "appending" "works", I can't recommend it. It is saying to make copies, one shouldn't rely on that Python does something different from what you told it, instead one should write what it's supposed to do.