python - 如何优化这些嵌套循环？

Question

谁能优化这个代码块吗？它正在工作，但运行速度非常慢。

maxsat = 0
possiblevotes = []
for i in range(1,int(numcats)+1):
    for j in range(1,int(numdogs)+1):
        possiblevotes.append('C' + str(i) + ' ' + 'D' + str(j))
        possiblevotes.append('D' + str(j) + ' ' + 'C' + str(i))
for m in possiblevotes:
    count = 0
    for n in votes:
        if m == n:
            count += 1
        elif m.split()[0] == n.split()[0]:
            count += 1
    if count > maxsat:
        maxsat = count

Answer 1

不需要生成所有可能的投票。您可以测试实际投票，而无需生成 possiblevotes 列表，因为您可以轻松计算现有投票是否可行。

您也只真正计算“留下”票。您寻找匹配的“stay go”投票并不重要，因为任何 m == n 为 true 的“stay go”投票，m.split()[0] == n.split()[0] 也是 true。所以你不妨放弃第一个计数，只看第二个。

现在您只需找到保留投票的最大计数。使用collections.Counter()使计数变得更容易:

import collections

vote_counts = collections.Counter(v.split()[0] for v in votes)

maxsat = vote_counts.most_common(1)[0][1]  # retrieve the most popular count

这计算出的数字与您的代码计算的数字相同，但现在我们只需循环投票一次，并且只计算“留下”票。

将此与您的循环进行对比，您首先循环 numcats * numdogs 次，然后循环 numcats * numdogs * 2 * len(votes) 次。 3 * numcats * numdogs 的因子更大。

如果您必须先验证投票，您可以使用:

from itertools import ifilter

numcats = int(numcats)
numdogs = int(numdogs)

def validvote(vote):
    stay, go = vote.split()
    cat, dog = sorted((stay, go))
    if (cat[0], dog[0]) != ('C', 'D'):
        return False
    if not (1 >= int(cat[1:]) >= numcats):
        return False
    if not (1 >= int(dog[1:]) >= numdogs):
        return False
    return True

vote_counts = collections.Counter(v.split()[0] for v in ifilter(validvote, votes))

您还可以开始使用go投票:

stay_votes = collections.Counter()
go_votes = collections.Counter()

for vote in ifilter(validvote, votes):
    stay, go = vote.split()
    stay_votes[stay] += 1
    go_votes[go] += 1

现在您可以简单地从保留票数中减去赞成票(任何跌至 0 的票数都会被删除):

total_votes = stay_votes - go_votes

# Display top 10
for creature, tally in total_votes.most_common(10):
    print('{}: {:>#5d}'.format(creature, tally))

当然，您也可以一次性计算:

total_votes = collections.Counter()

for vote in ifilter(validvote, votes):
    stay, go = vote.split()
    total_votes[stay] += 1
    total_votes[go] -= 1

但是将投票结果分开保存对于以后的分析可能会很有趣。