python - 2 listy i znajdowanie maksymalnego produktu z 2 list

Question

Mam dwie listy z liczb (liczb całkowitych); obie mają 2 miliony unikalnych elementów.

Chcę znaleźć Number z listy 1 i B z listy 2, które -

1)a*b should be maximized. 
2)a*b has to be smaller than certain limit. 

oto co wymyśliłem:

maxpq = 0 
nums = sorted(nums, reverse=True) 
nums2 = sorted(nums2, reverse=True) 
for p in nums: 
    n = p*dropwhile(lambda q: p*q>sqr, nums2).next() 
    if n>maxpq: 
     maxpq=n 
print maxpq 

wszelkie sugestie? edytuj: moja metoda jest zbyt powolna. Zajmie to więcej niż jeden dzień.

Answer 1

Oto rozwiązanie liniowy w czasie (po sortowaniu):

def maximize(a, b, lim): 
    a.sort(reverse=True) 
    b.sort() 
    found = False 
    best = 0 
    j = 0 
    for i in xrange(len(a)): 
     while j < len(b) and a[i] * b[j] < lim: 
      found = True 
      if a[i]*b[j] > best: 
       best, n1, n2 = a[i] * b[j], a[i], b[j] 
      j += 1 
    return found and (best, n1, n2) 

Upraszczając:

• rozpoczynać od najwyższego i najniższego od każdej listy
• , podczas gdy ich produkt jest mniejszy niż cel, przesuń sma ll-poz
• gdy produkt staje się większy niż cel, przesunąć big-przedmiot, aż spadnie poniżej ponownie

ten sposób masz gwarancję, aby przejść przez każdy liście tylko raz. Zwróci ona False, jeśli nie znajdzie niczego wystarczająco małego, w przeciwnym razie zwróci produkt i parę, która go wyprodukowała.

Przykładowe wyjście:

a = [2, 5, 4, 3, 6] 
b = [8, 1, 5, 4] 
maximize(a, b, 2) # False 
maximize(a, b, 3) # (2, 2, 1) 
maximize(a, b, 10) # (8, 2, 4) 
maximize(a, b, 100) # (48, 6, 8) 

Answer 2

To może być szybsze.

def doer(L1, L2, ceil): 
    max_c = ceil - 1 
    L1.sort(reverse=True) 
    L2.sort(reverse=True) 
    big_a = big_b = big_c = 0 

    for a in L1: 
     for b in L2: 
      c = a * b 
      if c == max_c: 
       return a, b 
      elif max_c > c > big_c: 
       big_a = a 
       big_b = b 
       big_c = c 

    return big_a, big_b 


print doer([1, 3, 5, 10], [8, 7, 3, 6], 60) 

Należy pamiętać, że sortuje listy w miejscu; jest to szybsze, ale może być lub może nie być odpowiednie w twoim scenariuszu.

Answer 3

Dzięki za porady i pomysły wszystkich. W końcu wymyśliłem użyteczne rozwiązanie. Pan inspektor G4dget rzucił na to światło.

Używa modułu bisect ze standardowej biblioteki Pythona.

edytuj: moduł bisect wykonuje wyszukiwanie binarne, aby znaleźć pozycję wstawienia wartości na posortowanej liście. w związku z tym zmniejsza liczbę porównań, w przeciwieństwie do mojego poprzedniego rozwiązania.

http://www.sparknotes.com/cs/searching/binarysearch/section1.rhtml

import bisect 

def bisect_find(num1, num2, limit): 
    num1.sort()  
    max_ab = 0 

    for a in num2: 
     complement = limit/float(a) 
     b = num1[bisect.bisect(num1, complement)-1] 

     if limit > a*b > max_ab: 
      max_ab=b*a 

    return max_ab