3

companiesから要素を取得し、それらを の要素とペアにするスクリプトに取り組んでいますpeople。目標は、すべてのペア値の合計が最大になるようにペアリングを最適化することです (個々のペアリングの値は事前に計算され、ディクショナリに格納されますctrPairs)。

1対1でペアを組み、1社に1人、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 の値 (各ペアの値) の 2 つのリストが与えられた場合、合計の「値」が最大になるようにそれらを割り当てる方法 (または同様に、最小化されます)。これには、ハンガリー語アルゴリズム( Python 実装)など、いくつかのアルゴリズムがあります。または、より一般的な最小コスト フロー アルゴリズムを使用して解くことも、線形プログラムとしてキャストして LP ソルバーを使用することもできます。これらのほとんどの実行時間は O(n 3 ) です。

上記のアルゴリズムが行うことは、それらをペアリングする可能なすべての方法を試すことです。(メモ化は、サブセットのペアの答えを再計算するのを避けるのに役立つだけですが、サブセットのすべてのペアを見ていることになります。) このアプローチは、少なくとも Ω(n 2 2 2n ) です。n=16 の場合、n 3は 4096、n 2 2 2nは 1099511627776 です。もちろん、各アルゴリズムには一定の要素がありますが、違いがわかりますか? :-) (問題のアプローチは、単純な O(n!) よりも優れていますが、これははるかに悪いものです。) O(n^3) アルゴリズムの 1 つを使用すると、アップに間に合うように実行されるはずです。 n=15 までではなく、n=10000 程度まで。

Knuth が言ったように、「時期尚早の最適化は諸悪の根源」ですが、最適化の遅延/期限切れも同様です。実装する前にまず適切なアルゴリズムを慎重に検討する必要があります。悪いアルゴリズムを選択してから、どの部分が遅いのか疑問に思うのではありません。:-) Python で適切なアルゴリズムを実装するのが下手でも、すべての「遅い?」を修正するよりも桁違いに高速です。上記のコードの一部 (たとえば、C で書き直す)。

于 2009-06-11T16:55:18.650 に答える
1

ここに 2 つの問題があります。

  1. 効率:remainingPeople会社ごとに同じサブリストを再作成しています。remainingPeopleすべてをremainingCompanies一度に作成してから、すべての組み合わせを実行する方がよいでしょう。

  2. メモ化: リストの代わりにタプルを使用してdict、メモ化のキーとして使用しています。ただし、タプル ID は順序に依存します。IOW:これにはs とs を(1,2) != (2,1) 使用することをお勧めします:setfrozensetfrozenset((1,2)) == frozenset((2,1))

于 2009-06-11T16:59:58.340 に答える
0

タプルのコピーをリストとして取得したい場合は、 mylist = list(mytuple) を実行できます

于 2009-06-11T16:54:22.457 に答える
0

この行：

残りの会社 = 会社[1:len(会社)]

次の行に置き換えることができます。

remainingCompanies = companies[1:]

非常にわずかな速度の増加。それが私が見る唯一の改善です。

于 2009-06-11T16:39:58.170 に答える