如何提高追加然后检查列表中后续元素的效率

Question

我正在尝试解决： http://orac.amt。 edu.au/cgi-bin/train/problem.pl?problemid=980&set=aio17int

该算法超出了较大文件的时间限制。我对 python 相当陌生，无法在网上找到更有效的解决方案来检查元素是否在列表中，然后进行相应的附加。请帮助提高速度而不使用任何导入。谢谢。

输入文件：

8 5
2 7
1 8
8 4
7 5
8 6

re = 1
bl = 1
red = [1]
blue = [2]
input_file = open("tagin.txt","r")
n, m = map(int, input_file.readline().split())
for i in range(m):
    a, b = map(int, input_file.readline().split())
    if a in red:
        red.append(b)
        re+=1
    elif a in blue:
        blue.append(b)
        bl+=1

output_file = open("tagout.txt", "w")
output_file.write(str(re) + " " + str(bl))
output_file.close()

输出文件：

4 3

另请告知堆栈溢出是否是提出此问题的错误平台，如果是，我应该使用什么？

Answer 1

您可以改进的一些地方：

• 使用集合而不是列表来收集团队成员。这将提高 in 运算符的效率。

• 无需跟踪团队的规模，因为您可以使用 len 函数获取该信息

• 仅收集一个团队的成员。我们可以从 m 得出另一个团队的规模，它代表有多少人被标记。如果我们添加 2，我们还会考虑已标记的前两个。从中减去一个团队的规模，就可以得到另一个团队的规模。

代码：

input_file = open("tagin.txt","r")
n, m = map(int, input_file.readline().split())
red = {1}  # A set, only for the red team
for i in range(m):
    a, b = map(int, input_file.readline().split())
    if a in red:  # Better efficiency as red is now a set
        red.add(b)

output_file = open("tagout.txt", "w")
# Size of blue team can be deduced from what we already know:
output_file.write(str(len(red)) + " " + str(m + 2 - len(red)))
output_file.close()

Answer 2

如果我正确理解问题，那么这应该实现目标：

with open('tagin.txt') as tagin:
    _, M = map(int, next(tagin).split())
    red = {1}
    blue = {2}
    for _ in range(M):
        a, b = map(int, next(tagin).split())
        (red if a in red else blue).add(b)
    print(len(red), len(blue))

输出：

4 3