现在它的复杂度是\ $ 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
#1 楼
是的，这样可以更快。在Python中使用+添加字符串通常不是一个好主意，因为字符串是不可变的。这意味着每当添加两个字符串时，都需要分配一个新字符串，并使用结果字符串的大小，然后将两个字符串内容都复制到此处。更糟糕的是，这样做是循环的，因为这必须永远发生。取而代之的是，您通常要构建一个字符串列表，并在最后进行''.join（您只需支付一次费用）。指定一个负步：def reverse_g(s):
return s[::-1]
下面是一个长度比较的随机字符串的时间比较，该字符串长度从一个到1M个字符，其中
reverse是您的函数，而reverse_g是此函数，使用切片。请注意双对数刻度，对于最大的字符串，您的函数要慢将近十万倍。q43201079q函数使用内置的
reverse_s，按照@sleblanc的回答（现在已删除，因此信誉达到10k以上）中的建议，并假设您实际上需要反转的字符串，而不仅仅是在其上进行迭代的字符串：def reverse_s(s):
return ''.join(reversed(s))
reversed函数使用@Broman答案中提供的用reverse_b编译的C实现，并使用包装器创建字符串缓冲区并提取输出：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'q4312078q0' * (len(s)+1))
_reverse_b(stro, stri, len(s) - 1)
return stro.value.decode()
在无接口版本中，仅定时调用
-O3。评论
\ $ \ begingroup \ $
您如何测量不确定度条，对于reverse_g，随着字符串长度的增加，在长度10附近的处理时间减少是否显着？如果是，为什么？
\ $ \ endgroup \ $
– Gerrit
19年3月11日在13:23
\ $ \ begingroup \ $
@gerrit：不确定度条来自每次计时测量均进行三次的事实，因此该值是平均值，不确定度是平均值的不确定度（即标准偏差/ sqrt（n））。因此，我怀疑下降幅度是否很大。有时，由于计算机上的一些其他活动，您的收入会大大增加，因此在第一种情况下可能会发生这种情况。
\ $ \ endgroup \ $
–地狱
19年3月11日在13:55
\ $ \ begingroup \ $
数据就是代码，而代码就是数据。考虑为什么您可能想反转字符串，而考虑使用简单地向后读取字符串的迭代器。本质上，这就是答案，而迭代器的实际实现则埋在CPython的内部。好答案
\ $ \ endgroup \ $
– sleblanc
19年3月12日在2:17
\ $ \ begingroup \ $
在Python中，使用+添加字符串通常不是一个好主意，因为字符串是不可变的。不变性（以及Python的使用）在这里并不重要；在几乎每种情况下，添加字符串都需要迭代至少一个字符串。预分配的可变C字符串串联仍然需要线性时间才能将第二个字符串的内容复制到第一个字符串的尾部。
\ $ \ endgroup \ $
–分裂
19年3月12日在3:42
\ $ \ begingroup \ $
@IsmaelMiguel：正如文本中提到的，reverse_g是具有切片功能的函数，即答案中的那个。重命名它，所以现在它是正确的名称。
\ $ \ endgroup \ $
–地狱
19年3月12日在10:14
#2 楼
就纯粹的复杂性而言，答案很简单：不，不可能比O（n）更快地反转字符串。当您查看纯算法时，这是理论上的极限。但是，由于循环中的操作不是O（1），因此您的代码无法实现这一目标。例如，
output += stri[-1]不执行您认为的操作。 Python是一种非常高级的语言，与C之类的语言相比，它在幕后做了很多奇怪的事情。字符串在Python中是不可变的，这意味着每执行一次该行，就会创建一个全新的字符串。 > 如果确实需要速度，则可以考虑编写C函数并从Python调用它。这是一个示例：
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]='gcc -o rev.so -shared -fPIC rev.c
';
}
使用以下命令编译上述功能：
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'stri[::-1] : 0.98s
calling reverse from python : 0.59s
calling reverse from c: 0.06s
0' * (len(hello)+1))
reverse(stro, stri, len(stri)-1)
print(repr(stri.value))
print(repr(stro.value))
这是使用该功能的python脚本。
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);
}
}
请注意我绝不是这方面的专家。我使用长度为10⁸的字符串进行了测试，然后尝试了Graipher的方法，从Python调用了C函数，并从C调用了C函数。我使用了
-O3优化。当我不使用任何优化时，从Python调用C函数会比较慢。另请注意，我没有包括创建缓冲区所花费的时间。但是纯C程序的运行速度更快。我使用的主要功能是这样一个：gcc -O3 -pg rev.c; ./a.out; gprof a.out gmon.out | head -n8
然后，要获得我运行的运行时：
评论
\ $ \ begingroup \ $
将时序添加到绘图中。为了公平起见，我包括了包装函数的时间（因为如果您想在Python中使用该函数，则希望它接受普通字符串并返回普通字符串）。我还必须修改输入缓冲区的创建以包括编码，否则它会给我TypeErrors。我用-O3编译了运行时。
\ $ \ endgroup \ $
–地狱
19年3月13日在8:47
\ $ \ begingroup \ $
@Graipher我不确定是否应该创建缓冲区。在许多情况下，您可能会继续使用同一缓冲区并执行更多操作。也许最公平的事情是做一个有和没有一个。
\ $ \ endgroup \ $
–klutt
19年3月13日在9:05
\ $ \ begingroup \ $
@Broman：坦白地说，包括它的一部分是为了使计时的获取和绘制更加容易，因为所有功能都具有相同的接口，因此让我使用该功能。但我会看看我能做什么。
\ $ \ endgroup \ $
–地狱
19年3月13日在9:07
\ $ \ begingroup \ $
@Graipher好吧，这完全取决于您。我只是在讨论。不要以为您必须这样做。但是，如果您这样做了，那么看看如果拉伸到10个元素就会发生什么会很有趣。除非您有无数的内存，否则不要去10⁹。开始交换之前，我不能超过10英镑。
\ $ \ endgroup \ $
–klutt
19年3月13日在9:11
\ $ \ begingroup \ $
顺便说一句，我真的很了解您是否不想在10⁸上尝试OP：s代码：)
\ $ \ endgroup \ $
–klutt
19年3月13日在9:19
评论
我想说您的代码是O（n ** 2），因为它会创建至少n个长度在1到n之间的字符串。我认为您是对的，因为我没有考虑python中字符串的不变性，但是@Graipher的图形在我的代码中显示出类似于O（nlgn）复杂度的东西，我不知道我是有点困惑...
根据字符串的大小以及您要使用的字符串，创建一个懒惰的ReverseString类可能是一个好主意，该类仅在需要时才访问数据。
@Midos这可能是由于使用了Python实现。 AFAIK，cPython有时确实会重用两个字符串之一（即，它试图在两个字符串之一之后/之前保留足够的空间，并且只需要复制一个字符串，但不要在此引用我）。但是，这既依赖于实现，也可能依赖于可用内存，这就是为什么Python的官方样式指南建议不要依赖它。
@Graipher我现在找不到它，但是我认为文档曾经说过它在线性时间内运行是CPython实现的细节。我现在能找到的是字符串是100％不可变的。 1 2 3 4（注释6讨论了这个用例）