代码之家 › 专栏 › 技术社区 › F-22 Destroyer

优化Python代码快4秒

performance python

F-22 Destroyer · 技术社区 · 11 月前

我写了一些代码来解决一个在线问题, Here .

mustConstraint = set()
notConstraint = set()
violated = 0
satisfied = 0 

for i in range(0, int(input(''))):
    constraint = input('')
    mustConstraint.add(frozenset(constraint.split()))

for i in range(0, int(input(''))):
    constraint = input('')
    notConstraint.add(frozenset(constraint.split()))

for i in range(0, int(input(''))):
    group = input('')
    group = set(group.split())

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

violated += len(mustConstraint) - satisfied

print(violated)

总结一下问题,第一行输入包含一个正整数X,其中X=>0.以下X行输入将包含两个单词,用空格分隔。这两个字必须属于同一组。下一行输入将包含另一个正整数Y;接下来的Y行输入将包含两个单词,用空格隔开。这两个词不能属于同一组。下一行输入将包含一个正整数G,其中G>=1.接下来的G行输入将由三个不同的单词组成,用单个空格隔开。这三个词被放在同一组。

输出一个介于0和X+Y之间的整数,这是违反的约束数。

我强烈建议您访问问题网站 here ,因为通过提供的示例案例及其解释,问题更容易理解。

不幸的是,由于最后一批有大约300000个输入,我的嵌套for循环太慢了,无法满足4秒的时间限制——有人能帮我优化我的代码吗?

大部分延迟来自此块:

for i in range(0, int(input(''))):
    group = input('')
    group = set(group.split())

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

嵌套的for循环每次执行100000^2次迭代,从该代码块(2*100000^2)总共迭代200亿次

如果有人能找到一种减少迭代次数的方法,那将产生巨大的影响。

2 回复 | 直到 11 月前

Stina Andersson 11 月前

您可以更有效地利用集合操作,特别是子集检查,可以使用issubset()进行改进。

您还可以通过一次读取所有输入并对其进行处理来避免冗余的输入调用。

这样地:

```
notConstraint = set()
mustConstraint = set()
violated = 0
satisfied = 0 

import sys
input = sys.stdin.read
data = input().splitlines()

# Read constraints
index = 0
for i in range(int(data[index])):
    index += 1
    constraint = data[index]
    mustConstraint.add(frozenset(constraint.split()))

index += 1
for i in range(int(data[index])):
    index += 1
    constraint = data[index]
    notConstraint.add(frozenset(constraint.split()))

# Process groups
index += 1
for i in range(int(data[index])):
    index += 1
    group = set(data[index].split())

    for x in mustConstraint:
        if x.issubset(group):
            satisfied += 1
        
    for y in notConstraint:
        if y.issubset(group):
            violated += 1

violated += len(mustConstraint) - satisfied

print(violated)
```

使用sys.stdin.read一次读取所有输入,并将其拆分为行以加快处理速度。并使用issubset()进行更有效的子集检查。

这减少了迭代次数,并显著提高了性能。

您可以在以下网址找到有关复杂常见操作的更多帮助 Big-O Cheat Sheet . 而且 Python's Time Complexity 很好地解释了Python内置数据类型的性能特征。

祝你好运

no comment Pratyush Goutam 11 月前

两种解决方案,都很容易通过所有测试。

解决方案1:最小变化

将你的大内环替换为该组三对上的小环,即改变

    for x in mustConstraint:
        if x & group == x:
            satisfied +=1
        
    for y in notConstraint:
        if y & group == y:
            violated += 1

对此:

    a, b, c = group
    for pair in {a, b}, {a, c}, {b, c}:
        if pair in mustConstraint:
            satisfied += 1
        if pair in notConstraint:
            violated += 1

解决方案2:只需两组操作

所有三个部分都指定了一组配对。有助于将其转化为函数。然后查找/统计违规行为:

必须是但不是的配对。
一定不是,而是。

from itertools import combinations

def pairs():
    return {
        frozenset(pair)
        for _ in range(int(input()))
        for pair in combinations(input().split(), 2)
    }

must = pairs()
must_not = pairs()
are = pairs()

print(len(must - are) + len(must_not & are))