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

发布时间：2020-12-20 13:00:35 所属栏目：Python 来源：网络整理

导读：我正在制作一个脚本,它接受公司的元素并将它们与人的元素配对.目标是优化配对,使得所有配对值的总和最大化(每个配对的值被预先计算并存储在字典ctrPairs中). 他们都以1：1的比例配对,每个公司只有一个人,每个人只属于一家公司,公司数量等于人数.我使用自上而

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

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

解决方法

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

你在这里要解决的问题被称为assignment problem：给出两个n元素列表和n×n值(每对的值),如何分配它们以使总“值”最大化(或等效),最小化).有几种算法,例如Hungarian algorithm(Python implementation),或者您可以使用更通用的最小成本流算法来解决它,或者甚至将其转换为线性程序并使用LP求解器.其中大多数的运行时间为O(n3).

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!