3

我正在编写一个脚本，该脚本从 中获取元素companies并将它们与people. 目标是优化配对，使所有配对值的总和最大化（每个单独配对的值被预先计算并存储在字典中ctrPairs）。

他们都是1:1配对的，每个公司只有一个人，每个人只属于一个公司，公司的数量等于人数。我使用自上而下的方法和记忆表 ( memDict) 来避免重新计算已经解决的区域。

我相信我可以大大提高这里发生的事情的速度，但我不确定如何。我担心的区域标有#slow?，任何建议都将不胜感激（该脚本适用于列表 n<15 的输入，但对于 n > ~15，它变得非常慢）

def getMaxCTR(companies, people):
    if(memDict.has_key((companies,people))):
        return memDict[(companies,people)] #here's where we return the memoized version if it exists
    if(not len(companies) or not len(people)):
        return 0

    maxCTR = None
    remainingCompanies = companies[1:len(companies)] #slow?

    for p in people:
        remainingPeople = list(people) #slow?
        remainingPeople.remove(p) #slow?
        ctr = ctrPairs[(companies[0],p)] + getMaxCTR(remainingCompanies,tuple(remainingPeople)) #recurse
        if(ctr > maxCTR):
            maxCTR = ctr
    memDict[(companies,people)] = maxCTR
    return maxCTR
4

4 回答 4

20

对于所有想知道学习理论的使用的人来说，这个问题就是一个很好的例子。正确的问题不是关于“在 python 中的列表和元组之间快速跳转的方法”——缓慢的原因是更深层次的。

您在这里尝试解决的问题称为分配问题：给定两个列表，每个列表有 n 个元素和 n×n 个值（每对的值），如何分配它们以使总“值”最大化（或等效地，最小化）。有几种算法可以解决这个问题，例如匈牙利算法（Python 实现），或者您可以使用更通用的最小成本流算法来解决它，或者甚至将其转换为线性程序并使用 LP 求解器。其中大多数的运行时间为 O(n 3 )。

您上面的算法所做的是尝试每种可能的配对方式。（记忆仅有助于避免重新计算子集对的答案，但您仍在查看所有子集对。）这种方法至少为 Ω(n 2 2 2n )。对于 n=16，n 3是 4096，n 2 2 2n是 1099511627776。当然，每种算法都有常数因子，但看到区别了吗？:-) （问题中的方法仍然比简单的 O(n!) 更好，这会更糟糕。）使用其中一种 O(n^3) 算法，我预测它应该及时运行 up到 n=10000 左右，而不是最多 n=15。

正如 Knuth 所说，“过早的优化是万恶之源”，但延迟/过期优化也是如此：在实施之前，您应该首先仔细考虑一个合适的算法，而不是选择一个糟糕的算法，然后想知道它的哪些部分是慢的。:-) 即使在 Python 中糟糕地实现一个好的算法也会比修复所有“慢？”快几个数量级。上面的部分代码（例如，通过用 C 重写）。

于 2009-06-11T16:55:18.650 回答
1

我在这里看到两个问题：

  1. 效率：您正在remainingPeople为每家公司重新创建相同的子列表。最好一次创建所有remainingPeople所有remainingCompanies，然后进行所有组合。

  2. memoization：您使用元组而不是列表来将它们用作dictmemoization 的键；但元组身份是顺序敏感的。IOW：(1,2) != (2,1) 您最好为此使用sets 和frozensets ：frozenset((1,2)) == frozenset((2,1))

于 2009-06-11T16:59:58.340 回答
0

这一行：

剩余公司 = 公司[1:len(公司)]

可以用这一行代替：

remainingCompanies = companies[1:]

对于非常轻微的速度增加。这是我看到的唯一改进。

于 2009-06-11T16:39:58.170 回答
0

如果您想获取元组的副本作为列表，您可以执行 mylist = list(mytuple)

于 2009-06-11T16:54:22.457 回答