问题描述
我很想知道我的麻省理工学院在线edx课堂练习问题的显然代码与提供的答案代码。 来自课程的问题分配如下：
成功的代码：
curSlice ='z'
for b in range（len（s ））：如果s [e-1] （b + 1，len（s））：
如果len（s [ b：e + 1]）> len（aas）：
aas = s [b：e + 1]
else：
break
print（'命令是：'+ str（aas））
逻辑是增加一个开始的字符串并测试每增加一个字母，增加数值，如果大于当前分片，则存储该分片，直到测试失败，并且开始字母增加1。
麻省理工学院的守则：
如果s [i]> [code> curString = s [0]
longest = s [0]
; = curString [-1]：
curString + = s [i]
if len（curString）> len（最长）：
最长= curString
else：
curString = s [i]
print'按字母顺序排列的最长字符串是：'，最长
哪个代码更高效？他们两人的长度差不多，但是我有两个圈。这是否使得它不是最优化的？谢谢
作为一个粗略的规则，添加更多循环会减慢速度。但这只是一个粗略的规则。看起来不像循环的东西在实际执行中可能会循环，从而导致速度变慢。例如，像 curString + = s [i] 这些天真的代码实际上可能非常慢。这是因为，假设curString是一个Python字符串，你不能再给它添加一个字母。 Python最终要做的是创建一个比旧的长1个字符的新字符串，然后将所有旧字符复制到新字符串中，然后附加一个新字符，然后将这个新字符串分配给 curString 。这两个实现都不是非常有效的，因为它们都是这样做的（使用范围而不是xrange，复制字符串切片等）。但是，假设字符串相对较短，这也不太可能成立。
无论如何，这两个实现都可以被固定，以便每个操作表演很有效率。在这种情况下，它会回到循环，它们的实现确实比你的更快。为了明白为什么，考虑像wxyabcd字符串。当考虑前三个字符（w，x和y）时，两种算法都做了几乎相同的事情。但是要考虑接下来发生的事在你的代码中你会遇到a，注意这不是按字母顺序排列，所以你结束了你的内部循环。你的外部循环将有b = 1，你会考虑所有以x开始的字符串。但是，这些永远不会给你一个更长的字符串，即以w开头的字符串，所以这是浪费精力。在继续检查以a开头的字符串之前，最后检查x，xy和y，而MIT代码将跳转到以a开头的字符串。更具体地说，这里是你的代码将考虑的一组字符串：
$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $
x
xy
y
a
ab
abc
abcd
b
bc
bcd
c
cd
d
以下是MIT代码将考虑的内容
pre $ $ $ $
$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $
正如您所看到的，他们的代码的工作量少得多。一种看待它的方法是，他们只查看字符串中任何给定的字符一次，而多次查看一些字符。
I was wondering about my apparently code for an MIT online edx class practice problem vs the provided answer code.
The assignment in question from the class was as follows:
My successful code:
curSlice='z'
for b in range(len(s)):
for e in range(b+1,len(s)):
if s[e-1]<=s[e]:
if len(s[b:e+1])>len(aas):
aas=s[b:e+1]
else:
break
print('Longest substring in alphabetical order is: '+str(aas))
The logic is to increment a beginning string letter and test every subsequent letter for increasing value then store the slice if bigger than the current slice, until the test fails and and the beginning letter increments one. At which point the process starts over.
MIT's Code:
curString = s[0]
longest = s[0]
for i in range(1, len(s)):
if s[i] >= curString[-1]:
curString += s[i]
if len(curString) > len(longest):
longest = curString
else:
curString = s[i]
print 'Longest substring in alphabetical order is:', longest
which code is more efficient? They both are about the same length, but mine has two loops. Does that make it not as optimized? Thanks
As a rough rule, adding more loops slows things down. But that's just a rough rule. Things that don't look like loops can, in actual implementation, be loops and thus slow things down. For example, innocent looking code like curString += s[i] can actually be quite slow. That's because, assuming curString is a Python string, you can't just add one more letter to it; what Python ends up doing is creating a new string that's 1 character longer than the old one, then copying all the old characters into the new string, then appending the one new character, and then assigning this new string to curString. Neither implementation is terribly efficient as they both do things like this (using range instead of xrange, copying slices of strings, etc.). However, assuming the strings are relatively short this is also unlikely to matter.
In any event, both implementations, your and theirs, could be fixed to so that each operation they perform is efficient. In that case, it does come back to the loops and their implementation is indeed faster than yours. To see why, consider a string like "wxyabcd". When considering the first three characters (the "w", "x", and "y"), both algorithms do pretty much the same thing. But consider what happens next. In your code you'll encounter the "a", note that this isn't in alphabetical order, so you end you inner loop. Your outer loop will have b = 1, and you'll consider the all strings that start with "x". However, these won't ever give you a longer string that the one that started with "w", so this is wasted effort. Still you'll end up checking "x", "xy", and "y" before moving on to check the strings that start with "a", while the MIT code will jump right to the strings that start with "a". To be more concrete, here's the set of strings your code will consider:
w
wx
wxy
x
xy
y
a
ab
abc
abcd
b
bc
bcd
c
cd
d
And here's what the MIT code will consider
w
wx
wxy
a
ab
abc
abcd
As you can see, their code does a lot less work. One way to look at it is that they "look at" any given character in the string only once while you will look at some characters multiple times.
这篇关于最长的子串计算复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！