By Midos


2019-03-11 10:01:06 8 Comments

This code will take as output any string (long, empty, with spaces...) and will return its reverse. Can I improve this algorithm so that it can be faster?

Right now its complexity is \$O(n)\$.

def reverse(stri):
    output = ''
    length = len(stri)
    while length > 0:
        output += stri[-1]
        stri, length = (stri[0:length - 1], length - 1)
    return output

2 comments

@Graipher 2019-03-11 10:11:41

Yes, this can be faster. Adding strings using + is usually a bad idea in Python, since strings are immutable. This means that whenever you add two strings, a new string needs to be allocated with the size of the resulting strings and then both string contents need to be copied there. Even worse is doing so in a loop, because this has to happen ever time. Instead you usually want to build a list of strings and ''.join them at the end (where you pay this cost only once).

But here you can just use the fact that strings can be sliced and you can specify a negative step:

def reverse_g(s):
    return s[::-1]

Here is a timing comparison for random strings of length from one up to 1M characters, where reverse is your function and reverse_g is this one using slicing. Note the double-log scale, for the largest string your function is almost a hundred thousand times slower.

enter image description here


The reverse_s function uses the reversed built-in, as suggested in the (now deleted, so 10k+ reputation) answer by @sleblanc and assumes you actually need the reversed string and not just an iterator over it:

def reverse_s(s):
    return ''.join(reversed(s))

The reverse_b function uses the C implementation, compiled with -O3, provided in the answer by @Broman, with a wrapper to create the string buffers and extract the output:

from ctypes import *

revlib = cdll.LoadLibrary("rev.so")
_reverse_b = revlib.reverse
_reverse_b.argtypes = [c_char_p, c_char_p, c_size_t]

def reverse_b(s):
    stri = create_string_buffer(s.encode('utf-8'))
    stro = create_string_buffer(b'\000' * (len(s)+1))
    _reverse_b(stro, stri, len(s) - 1)
    return stro.value.decode()

In the no interface version, just the call to _reverse_b is timed.

@gerrit 2019-03-11 13:23:23

How did you measure the uncertainty bars, is the drop in processing time with increasing string length near length 10 for reverse_g significant and if so why?

@Graipher 2019-03-11 13:55:15

@gerrit: The uncertainty bars come from the fact that each timing measurement is performed three times, so the value is the mean and the uncertainty the uncertainty of the mean (i.e. standard deviation / sqrt(n)). So I would doubt that the drop is significant. Sometimes you get large increases due to some other activity on the machine, so that is what could have happened in the first case.

@sleblanc 2019-03-12 02:17:56

Data is code and code is data. Ponder why you might want to reverse the string, and consider instead to use an iterator that simply reads the string backwards. This is essentially what this answer is, while the actual implementation the iterator is buried inside CPython's internals. Nice answer

@Schism 2019-03-12 03:42:52

Adding strings using + is usually a bad idea in Python, since strings are immutable. Immutability (and the use of Python) isn't what matters here; in nearly every case, string addition requires iterating over at least one of the strings. A pre-allocated, mutable C-string concatenation still requires linear time to copy the contents of the second string into the tail of the first.

@Ismael Miguel 2019-03-12 09:59:50

Which function is reverse_g()? You have reverse() and reverse_s() on your code, and the question just has reverse() as well.

@Graipher 2019-03-12 10:14:58

@IsmaelMiguel: As mentioned in the text reverse_g is the function with the slicing, i.e. the one in the answer. Renamed it so it is the correct name now, though.

@Deduplicator 2019-03-12 16:15:59

Having time/input on the left axis (and adjusting its scaling if needed) might be even better.

@Graipher 2019-03-12 16:26:08

@Deduplicator: That might show off the differences better, but I am usually also interested in the overall running time of an algorithm. It is also less generally useful (because I do need these timing plots quite often and the inputs are quite diverse). In this case it looks interesting, though: i.stack.imgur.com/RlEym.png (ignore the ylabel, it should be "Time / len(s)", I did not change it)

@corsiKa 2019-03-12 18:48:52

Keep in mind that graph is LOGARITHMIC when trying to see exactly how much faster the orange line is than the blue (or even green, which is already substantially improved.)

@Graipher 2019-03-12 19:35:06

@corsiKa Thanks for reminding me to check the wording again. In an earlier version the plot only went to 10^5, where the ratio was about a thousand, but at 10^6 this grows to about a hundred thousand.

@Broman 2019-03-12 20:28:12

@Graipher I posted an answer below. If you have the time and energy, you could update the benchmark graph with that.

@Graipher 2019-03-12 20:29:01

@Broman I'll see if I manage to include it tomorrow.

@Broman 2019-03-12 06:43:07

In terms of pure complexity, the answer is simple: No, it is not possible to reverse a string faster than O(n). That is the theoretical limit when you look at the pure algorithm.

However, your code does not achieve that because the operations in the loop are not O(1). For instance, output += stri[-1] does not do what you think it does. Python is a very high level language that does a lot of strange things under the hood compared to languages such as C. Strings are immutable in Python, which means that each time this line is executed, a completely new string is created.

If you really need the speed, you could consider writing a C function and call it from Python. Here is an example:

rev.c:

#include <stddef.h>
void reverse(char * stro, char * stri, size_t length) {
    for(size_t i=0; i<length; i++) stro[i]=stri[length-1-i];
    stro[length]='\0';
}

Compile the above function with this command:

gcc -o rev.so -shared -fPIC rev.c

And here is a python script using that function.

rev.py:

from ctypes import *

revlib = cdll.LoadLibrary("rev.so");
reverse = revlib.reverse
reverse.argtypes = [c_char_p, c_char_p, c_size_t]

hello = "HelloWorld"
stri = create_string_buffer(hello)
stro = create_string_buffer(b'\000' * (len(hello)+1))

reverse(stro, stri, len(stri)-1)

print(repr(stri.value))
print(repr(stro.value))

Please note that I'm by no means an expert on this. I tested this with string of length 10⁸, and I tried the method from Graipher, calling the C function from Python and calling the C function from C. I used -O3 optimization. When I did not use any optimization it was slower to call the C function from Python. Also note that I did NOT include the time it took to create the buffers.

stri[::-1] :                  0.98s
calling reverse from python : 0.59s
calling reverse from c:       0.06s

It's not a huge improvement, but it is an improvement. But the pure C program was WAY faster. The main function I used was this one:

int __attribute__((optimize("0"))) // Disable optimization for main
main(int argc, char ** argv) {     // so that reverse is not inlined

    const size_t size = 1e9;
    char * str = malloc(size+1);

    static const char alphanum[] =
        "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
    // Take data from outside the program to fool the optimizer        
    alphanum[atoi(argv[1])]='7';

    // Load string with random data to fool the optimizer        
    srand(time(NULL));
    for (size_t i = 0; i < size; ++i) {
        str[i] = alphanum[rand() % (sizeof(alphanum) - 1)];
    }

    char *o = malloc(size+1);
    reverse(o, str, strlen(str));

    // Do something with the data to fool the optimizer        
    for(size_t i=0; i<size; i++) 
        if(str[i] != o[size-i-1]) {
            printf("Error\n");
            exit(1);
        }
}

Then, to get the runtime I ran:

gcc -O3 -pg rev.c; ./a.out; gprof a.out gmon.out | head -n8

@PascalVKooten 2019-03-12 15:04:45

Thus, this answer is simply wrong as it doesn't address the issue with the presented code

@Broman 2019-03-12 20:27:10

@PascalVKooten Fixed

@Graipher 2019-03-13 08:47:04

Added the timings to the plot. To be a fair competition I included the time of the wrapper function (since if you want to use the function in Python you want it to accept normal strings and return a normal string). I also had to modify the creation of the input buffer to include an encoding, otherwise it was giving me TypeErrors. I compiled the runtime with -O3.

@Broman 2019-03-13 09:05:04

@Graipher I was unsure if I should include the buffer creation or not. One can think of many circumstances where you continue to work on the same buffer and perform more operations. Maybe the most fair thing to do would be to do one with and one without.

@Graipher 2019-03-13 09:07:24

@Broman: To be honest, part of including it was so that getting and plotting the timings is easier, since all functions have the same interface, which let's me use a function for that. But I'll see what I can do.

@Broman 2019-03-13 09:11:13

@Graipher Well, of course it's completely up to you. I'm just discussing it. Don't feel that you have to do it. But if you do it, it would be interesting to see what happens if you stretch to 10⁸ elements. Don't go to 10⁹ unless you have endless amount of memory. I could not go above 10⁸ before it started to swap.

@Broman 2019-03-13 09:19:18

And btw, I really understand if you don't want to try OP:s code on 10⁸ :)

@Graipher 2019-03-13 09:30:53

@Broman: :D Yeah. Anyway, already at about 10^4, the pure C code, with just the calling of the C function included in the timing, is faster than letting Python call it's C function implementation of s[::-1] (plot updated). Python seems to be doing some interesting stuff for shortish strings, though, since there it beats your implementation by a factor of five or so.

Related Questions

Sponsored Content

1 Answered Questions

[SOLVED] String reversing x times

1 Answered Questions

[SOLVED] Reversing the vowels in a String

2 Answered Questions

[SOLVED] URLify a string using Python

2 Answered Questions

[SOLVED] Find smallest subset prefixes

2 Answered Questions

2 Answered Questions

[SOLVED] Finding longest common prefix

3 Answered Questions

[SOLVED] Finding the fastest common prefix of 2 strings in Python

1 Answered Questions

[SOLVED] Method to replace all spaces in a String with '%20'

  • 2016-03-05 10:02:37
  • fsociety
  • 3097 View
  • 3 Score
  • 1 Answer
  • Tags:   java strings

1 Answered Questions

3 Answered Questions

[SOLVED] Reversing every word in a string

Sponsored Content