AIO城堡骑兵-我的代码太慢了，有什么方法可以缩短这个吗？
因此，我目前正在筹备一项竞赛(澳大利亚信息学奥林匹克运动会)，在训练枢纽中，在2018年AIO2018中级课程中有一个名为城堡骑兵的问题。我完成了它：
input = open("cavalryin.txt").read()
output = open("cavalryout.txt", "w")
squad = input.split()
total = squad[0]
squad.remove(squad[0])
squad_sizes = squad.copy()
squad_sizes = list(set(squad))
yn = []
for i in range(len(squad_sizes)):
n = squad.count(squad_sizes[i])
if int(squad_sizes[i]) == 1 and int(n) == int(total):
yn.append(1)
elif int(n) == int(squad_sizes[i]):
yn.append(1)
elif int(n) != int(squad_sizes[i]):
yn.append(2)
ynn = list(set(yn))
if len(ynn) == 1 and int(ynn[0]) == 1:
output.write("YES")
else:
output.write("NO")
output.close()我提交了这段代码，但没有通过，因为它太慢了，只有1.952秒。时间限制是1.000秒。我不知道怎样才能把它缩短，因为在我看来它看起来很好。请记住，我还在学习，我只是个业余爱好者。我只是在今年才开始编写代码，所以如果答案很明显，很抱歉浪费了你的时间。
谢谢你帮我！
回答 3
Stack Overflow用户
发布于 2019-08-18 05:38:16
一个性能问题是在同一个实体上一次又一次地调用int()，或者对已经是int的事物进行调用。
if int(squad_sizes[i]) == 1 and int(n) == int(total):
elif int(n) == int(squad_sizes[i]):
elif int(n) != int(squad_sizes[i]):
if len(ynn) == 1 and int(ynn[0]) == 1:但真正的问题是你的代码不起作用。让它更快也改变不了这一点。考虑到投入：
4
2
2
2
2您的代码将输出"NO" (缺少换行符)，尽管它是一个有效的配置。这是由于您在代码的早期使用set()来缩小团队大小。您已经丢弃了重要的信息，并且只对数据的一部分进行了测试。作为比较，下面是我认为正确处理输入的完整重写：
with open("cavalryin.txt") as input_file:
string = input_file.read()
total, *squad_sizes = map(int, string.split())
success = True
while squad_sizes:
squad_size = squad_sizes.pop()
for _ in range(1, squad_size):
try:
squad_sizes.remove(squad_size) # eliminate n - 1 others like me
except ValueError:
success = False
break
else: # no break
continue
break
with open("cavalryout.txt", "w") as output_file:
print("YES" if success else "NO", file=output_file)注意，我在早期将所有输入转换为int，这样就不必再考虑这个问题了。我不知道这是否符合AIO的时间限制。
Stack Overflow用户
发布于 2019-08-18 05:28:24
我可以在其中看到一些可能效率低下的东西，但优化代码的最佳方法是分析它:使用分析器和示例数据运行它。
你可以很容易地浪费时间，试图加快那些不需要它的部分，而不会产生很大的影响。阅读标准库中的cProfile模块，了解如何这样做并解释输出。分析教程可能太长，无法在这里复制。
我的建议，没有分析，
squad.remove(squad[0])删除大列表的开始很慢，因为列表的其余部分必须在其向下移动时被复制。(删除列表的末尾更快，因为列表通常由过度分配的数组(比元素多)支持，这样.append()就可以快速运行，因此它只需要减少长度，并且可以保持相同的数组。
最好将其设置为一个虚拟值，并在将其转换为一个集合时将其移除(集合由哈希表支持，因此删除速度很快)。
dummy = object()
squad[0] = dummy # len() didn't change. No shifting required.
...
squad_sizes = set(squad)
squad_sizes.remove(dummy) # Fast lookup by hash code.因为我们知道这些都是字符串，所以您可以只使用None而不是虚拟对象，但是即使您的列表可能包含None，上述技术也能工作。
squad_sizes = squad.copy()这一行不是必需的，它只是做额外的工作。set()已经做了一个浅拷贝。
n = squad.count(squad_sizes[i])这条线可能是真正的瓶颈。它实际上是一个循环内部的一个循环，所以它基本上必须扫描每个外循环的整个列表。考虑将collections.Counter用于此任务。在循环之外生成一次计数表，然后查找每个字符串的数字。
如果这样做，还可以避免完全生成集合。只需将Counter对象的键用于您的集合。
另一点与性能无关。当您不需要索引时使用像[i]这样的索引是非质子化的。for循环可以从迭代中获取元素，并在一个步骤中将它们赋值给变量：
from collections import Counter
...
count_table = Counter(squad)
for squad_size, n in count_table.items():
...Stack Overflow用户
发布于 2019-08-18 13:02:49
您可以在字典中收集每个骑士的首选数字的所有出现情况。然后测试具有给定优先数的骑士数是否可被该数整除。
with open('cavalryin.txt', 'r') as f:
lines = f.readlines()
# convert to int
list_int = [int(a) for a in lines]
#initialise counting dictionary: key: preferred number, item: empty list to collect all knights with preferred number.
collect_dict = {a:[] for a in range(1,1+max(list_int[1:]))}
print(collect_dict)
# loop though list, ignoring first entry.
for a in list_int[1:]:
collect_dict[a].append(a)
# initialise output
out='YES'
for key, item in collect_dict.items():
# check number of items with preference for number is divisilbe
# by that number
if item: # if list has entries:
if (len(item) % key) > 0:
out='NO'
break
with open('cavalryout.txt', 'w') as f:
f.write(out)https://stackoverflow.com/questions/57541726
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号