할당 최적화 작업을 쉽게 해결하는 방법

StackOverflow https://stackoverflow.com/questions/982127

문제

저는 요소를 가져오는 스크립트를 작성 중입니다. 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
도움이 되었습니까?

해결책

학습 이론의 사용에 대해 궁금해하는 모든 사람들에게 이 질문은 좋은 예입니다.올바른 질문은 '파이썬에서 목록과 튜플 사이를 빠르게 이동하는 방법'에 관한 것이 아닙니다. 느린 이유는 더 깊은 데 있습니다.

여기서 해결하려는 것은 할당 문제:각각 n개의 요소로 구성된 두 개의 목록과 n×n 값(각 쌍의 값)이 주어지면 전체 "값"이 최대화(또는 동등하게 최소화)되도록 이를 할당하는 방법.이를 위한 여러 가지 알고리즘이 있습니다. 헝가리어 알고리즘 (파이썬 구현) 또는 보다 일반적인 최소 비용 흐름 알고리즘을 사용하여 문제를 풀거나 선형 프로그램으로 캐스팅하고 LP 솔버를 사용할 수도 있습니다.이들 중 대부분은 O(n)의 실행 시간을 갖습니다.3).

위의 알고리즘은 가능한 모든 페어링 방법을 시도하는 것입니다.(메모는 하위 집합 쌍에 대한 답을 다시 계산하는 것을 피하는 데에만 도움이 되지만 여전히 모든 하위 집합 쌍을 보고 있습니다.) 이 접근 방식은 최소한 Ω(n222n).n=16인 경우, n3 4096이고 n입니다222n 1099511627776입니다.물론 각 알고리즘에는 일정한 요소가 있지만 차이점이 보이시나요?:-) (질문의 접근 방식은 순진한 O(n!)보다 여전히 낫습니다. 이는 훨씬 더 나쁠 것입니다.) O(n^3) 알고리즘 중 하나를 사용하면 최대 시간에 맞춰 실행될 것으로 예측합니다. 최대 n=15가 아닌 n=10000 정도로 변경됩니다.

Knuth가 말했듯이 "성급한 최적화는 모든 악의 근원입니다". 그러나 지연/기한이 지난 최적화도 마찬가지입니다.구현하기 전에 먼저 적절한 알고리즘을 주의 깊게 고려해야 합니다. 나쁜 알고리즘을 선택한 다음 어떤 부분이 느린지 궁금해해서는 안 됩니다.:-) Python에서 좋은 알고리즘을 잘못 구현하더라도 모든 "느린"을 고치는 것보다 훨씬 빠른 순서가 될 것입니다. 위의 코드의 일부 (예 : C로 다시 쓰기).

다른 팁

여기에는 두 가지 문제가 있습니다.

  1. 효율성 : 당신은 같은 것을 재현하고 있습니다 remainingPeople 각 회사의 하위 목록. 모든 것을 만드는 것이 좋습니다 remainingPeople 그리고 모든 remainingCompanies 한 번 그리고 모든 조합을 수행하십시오.

  2. Memoization : 목록 대신 튜플을 사용하여 사용합니다. dict 메모 화를위한 열쇠; 그러나 튜플 아이덴티티는 순서에 민감합니다. iow : (1,2) != (2,1) 당신은 더 잘 사용합니다 set모래 frozenset이것을위한 s : frozenset((1,2)) == frozenset((2,1))

이 라인 :

나머지 회사 = 회사 [1 : Len (회사)

이 줄로 교체 할 수 있습니다.

remainingCompanies = companies[1:]

매우 약간의 속도 증가. 그것이 내가 보는 유일한 개선입니다.

목록으로 튜플 사본을 받으려면 mylist = list (mytuple)를 할 수 있습니다.

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top