최적화 파이썬 알고리즘

, 나는 모든 조합 가능한 가장 빠른 시간에 x, y, zx in a, y in b and z in c 및 1/x + 1/y + 1/z < 1을 얻고 싶은 최적화 파이썬 알고리즘

a, b, c = [10,9,8], [9,8,7], [13,5,1]

을 examplewise. 나는

for x, y, z in product(a, b, c): 
    if predicative(x,y,z): 
     yield (x, y, z)

는 물론, 이것이 내가 모든 것을 확인하고있어 고려 너무 시간이 오래 걸립니다, 몇 가지 다른 접근을 시도하고 있었고, 목록 a, b, c 이미 분류되어 있습니다. sum에서 product(a,b,c)을 정렬하려고 시도했지만, 모든 제품을 사용하기 때문에 속도가 느립니다. a, b and c이 정렬 된 나의 초기 계획은 하나가 실패하자마자 루프에서 빠져 나올 수 있습니다. 어떤 아이디어?

감사합니다. 합니다 (auxillary 목록에서) 가장 높은 1/z에 대한 이진 검색을 사용 - 조금을 가속화 할 수

출처

2015-01-18 Martol1ni

['itertools.takewhile'] (https://docs.python.org/2/library/itertools.html#itertools.takewhile)로 생각하십니까? 순수한 파이썬과 동등한 구현은 현재 접근법에 두 줄을 더한 것입니다 ('else : break'). – jonrsharpe

'takewhile will'은 직선적으로 진행되므로 정직하게 작동한다고 생각하지 않습니다. '제품'이 분류되는 방식으로, 나는 쉽게 조합을 놓칠 수있다. 내가 틀렸다면 나를 바로 잡아주세요. – Martol1ni

@ Martol1ni 데이터가 이미 정렬되었으므로 [this] (http://ideone.com/dCMAF3)가 내가 얻을 수있는 최상의 것입니다. – thefourtheye

간단한 해결책이 목록에 c 각 z에 대한 1/z를 저장하기 위해, 그리고 a,b에서 x,y의 각 쌍에 대한 것 따라서 1/x + 1/y + 1/z < 1 - 3 번째 목록에서 많은 검색을 효과적으로 다듬어 속도를 높일 수 있습니다.
이렇게하면 시간 복잡도가 O(log(n)*n^2 + Y)으로 줄어 듭니다. 여기서 Y은 출력 크기입니다 (생성 된 삼중 항의 수).

그러나 출력 크기 자체가 O(n^3) (모든 요소가 3.333 이상인 3 개의 목록을 고려하십시오.)이므로 n^3 세 쌍을 생성해야하므로 최악의 경우는 느려지지 않습니다.

그러나 카운트 만 원하는 경우 접근 방법은 O(n^2*logn)에서 쉽게 찾을 수 있습니다.

출처

2015-01-18 12:59:35 amit

그것은 매우 흥미 롭습니다. 나는 내가 무엇을 하든지'O (n^3) '로 끝낼 것입니다. – Martol1ni

답변

관련 문제