如何tractably解决的优化分配任务

Question

我工作的一个脚本，需要的元素 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

Answer 1

所有那些不知道对使用的学习理论，这个问题是一个很好的例子。正确的问题不是一个"快速的方式反弹之间的清单和元组在蟒蛇"—之所以缓慢，是更深层次的东西.

什么你试图解决这里是被称为 分配问题:鉴于两个列表中的n元素中的每一个和n×n值(价值的每一对)、如何分配他们，因此总的"价值"最大化的(或者最小化)。有几个算法用于这一点，例如 匈牙利算法 (蟒蛇执行情况)，或者你可以解决它使用更多的一般分成本的流动算法，或甚至把它作为一个线性程序，并使用一个LP求解。大多数的这些会有一个运行时间O(n³).

什么你的算法上不是尽量每个可能的办法配对。(该memoisation仅有助于避免重新计算答案，对子集，但你仍然在寻找，在所有对子集。) 这种做法是至少Ω(n²2²ⁿ).N=16,n³ 是4096和n²2²ⁿ 是1099511627776.有恒定的因素在各个算法的过程，但是看到差别？:-)(该方法的问题仍然是更好的比的幼稚O(n!), 这将会更糟糕。) 使用一个O(n^3)的算法，我预计，它应该运行在时间长达n=10000个左右，而不是仅仅达n=15。

"早产的优化是所有罪恶的根源"，因为Knuth所述，但所以被延迟/过期优化：你应该先认真考虑一个适当的算法实施之前，不挑一个坏的然后不知道哪些部分是缓慢的。:-)即使是不好实施一个良好的算法在Python将订单的幅度快于修复所有的"慢？"零部件的编码以上(例如，通过改写在C)。

Answer 2

我在这里看到两个问题：

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

2. 记忆：您使用元组而不是列表来将它们用作 dict 记忆键；但元组身份是顺序敏感的。IOW： (1,2) != (2,1) 你最好使用 set沙 frozenset为此： frozenset((1,2)) == frozenset((2,1))

Answer 3

此行：

remainingCompanies =公司[1：LEN（公司）]

可与这条线被替换为：

remainingCompanies = companies[1:]

有关非常轻微的速度增加。这是我看到的唯一的改善。

Answer 4

如果你想获得一个元组的副本，你可以做一个列表 MYLIST =列表（mytuple）