如何轻松解决分配优化任务

Question

我正在编写一个脚本,它接收元素,companies并将它们与元素配对people.目标是优化配对,使得所有配对值的总和最大化(每个配对的值被预先计算并存储在字典中ctrPairs).

他们都以1:1的比例配对,每个公司只有一个人,每个人只属于一家公司,公司数量等于人数.我使用自上而下的方法和memoization table(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

Answer 1

对于那些对使用学习理论感到疑惑的人来说,这个问题很好.正确的问题不是"在python中列表和元组之间反弹的快速方法" - 缓慢的原因是更深层次的.

你在这里要解决的问题被称为赋值问题:给定两个n元素列表和n×n值(每对的值),如何分配它们以使总"值"最大化(或者等价地,最小化).有几种算法,例如匈牙利算法(Python实现),或者您可以使用更通用的最低成本流算法来解决它,甚至将其转换为线性程序并使用LP求解器.其中大多数的运行时间为O(n ³).

你的算法上面做的是尝试每种可能的配对方式.(记忆仅有助于避免重新计算子集对的答案,但您仍然在查看所有子集对.)此方法至少为Ω(n ² 2 ²ⁿ).对于n = 16,n ³为4096,n ² 2 ²ⁿ为1099511627776.当然,每种算法都有常数因子,但看到差异？:-)(问题中的方法仍然比天真的O(n!)更好,这会更糟糕.)使用其中一个O(n ^ 3)算法,我预测它应该及时运行起来n = 10000左右,而不是n = 15.

正如Knuth所说,"过早优化是所有邪恶的根源",但延迟/过期优化也是如此:在实施之前,你应首先仔细考虑一个合适的算法,而不是挑选一个坏算法,然后想知道它的哪些部分很慢.:-)即使在Python中实现一个好的算法,也比修复所有"慢"快几个数量级.上面代码的一部分(例如,通过在C中重写).