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
O(n**2)
because it creates at least n strings with length between1
andn
. \$\endgroup\$ReverseString
class, which only accesses the data when needed. \$\endgroup\$