英文:
Is there a way to speed up python while loop without numpy or pypy or cython
问题
我正在尝试解决USACO问题Censoring（Bronze），这是2015年2月比赛的第1个问题。我的解决方案对一些测试案例有效，但对其余的测试案例超时。如何加快代码速度？我尝试使用Numba，但Numba在USACO IDE中不起作用。https://ide.usaco.guide/NXQs8hkV3sWOtNYsvyj
http://www.usaco.org/index.php?page=viewproblem2&cpid=526
这是问题链接。
这是我的代码：
input = open('censor.in', 'r').read().split('\n')
s = input[0]
c = input[1]
l = len(c)
while True:
try:
i = s.index(c)
s = s[:i] + s[i + l:]
except:
break
output = open('censor.out', 'w')
output.write(s)
output.close()
它在测试案例7-15上超时。
我期望它以O(n)时间复杂度运行，因为有一个while循环，应该有效，但它没有。问题出在哪里？
英文:
I'm trying to solve the USACO problem Censoring(Bronze), which was the 1st problem for the 2015 February contest. My solution works for some test cases, but then times out for the rest. How do I speed up the code? I tried to use Numba, but Numba doesn't work in USACO IDE. https://ide.usaco.guide/NXQs8hkV3sWOtNYsvyj
http://www.usaco.org/index.php?page=viewproblem2&cpid=526
This is the problem link.
This is my code:
input = open('censor.in', 'r').read().split('\n')
s = input[0]
c = input[1]
l = len(c)
while True:
try:
i = s.index(c)
s = s[:i] + s[i + l:]
except:
break
output = open('censor.out', 'w')
output.write(s)
output.close()
It timed out for test cases 7-15.
I expected it to run with O(n) time complexity because of the while loop, which should work, but it didn't. What's wrong?
答案1
得分: 0
这不是对Python代码本身的修复，但你可以尝试关闭电脑上的其他应用程序，特别是浏览器，因为它们占用了大量的内存。Microsoft Edge在后台运行，所以你需要打开任务管理器（Ctrl + Shift + Esc）然后结束掉Edge。
英文:
This isn't a fix to the python code itself, but you can try closing other apps on your computer, particularly browsers as they take up alot of ram. Microsoft edge runs in the background, so you have to open up task manager (ctrl + shift + esc) and kill edge
答案2
得分: 0
你的代码不是O(n)，有两个原因。为了看清楚原因，让我们考虑我认为的最坏情况：输入是500,000个a，后面跟着499,999个b。然后你被要求删除ab。
问题＃1：你从字符串的开头开始搜索下一个ab的出现。每次搜索都会是O(n)，因为你直到字符串的中间才找到ab。如果你之前的搜索返回位置i，那么在压缩字符串之后，你知道不需要回退到i - len(search_string) + 1之前。你在前一轮已经在i - len(search_string)找到了一个结果。
问题＃2：字符串的拼接是O(n)。你一直在删除字符串的中间部分，然后重新将前半部分和后半部分拼接在一起。同样，你最终会得到一个O(n^2)的算法。我不能立即想到一个简单的方法来修复这个问题。一个更复杂的解决方案可能是将字符串放入一个deque中，但这会使代码的搜索部分变得更加复杂。
无论如何，你的代码不是O(n)。你有一个while循环，但在每个while循环内部，你做了比你意识到的更多的工作。
英文:
Your code is not O(n) for two reasons. To see why, let's consider what I think is the worst case: The input is 500,000 as followed by 499,999 bs. And you're asked to delete ab.
Problem #1. You are starting your search for the next occurrence of ab from the beginning of the string. Each of your searches is going to be O(n), since you don't find ab until the middle of the string. If your previous search returned position i, you know that after collapsing the string, you don't need to go back further than i - len(search_string) + 1. You would have found a result at i - len(search_string) on the previous round.
Problem #2. String concatenation is O(n). You are repeatedly chopping out the middle of the string and putting the front and back together again. Again, you'll end up with an O(n^2) algorithm. I can't come up immediately with a simple way to fix this. A more complicated solution would be to put the string into a deque, but that complicates the search part of the code.
In any case, your code is not O(n). You have a single while loop, but you're doing more work than you realize inside each while loop.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论