python - 2 elenchi e ricerca del prodotto massimo da 2 elenchi

Question

Ho due elenchi composti da numeri (numeri interi); entrambi hanno 2 milioni di elementi unici.

Voglio trovare il numero uno dalla lista 1 e B dalla lista 2, che -

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

ecco cosa mi si avvicinò con:

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 

qualche suggerimento? modifica: il mio metodo è troppo lento. Ci vorrebbe più di un giorno.

Answer 1

Ecco una soluzione in tempo lineare (dopo la cernita):

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) 

In poche parole:

• partenza dal più alto e quello più basso da ogni lista
• mentre il loro prodotto è inferiore al target, far avanzare lo sma ll-voce
• una volta che il prodotto diventa più grande di quanto il vostro obiettivo, far avanzare il big-voce fino a quando va sotto di nuovo

In questo modo, avrete la garanzia di passare attraverso ogni lista solo una volta. Restituirà False se non riesce a trovare qualcosa di abbastanza piccolo, altrimenti restituirà il prodotto e la coppia che lo ha prodotto.

Esempio di output:

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

Questo potrebbe essere più veloce.

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) 

Nota che ordina gli elenchi sul posto; questo è più veloce, ma può o non può essere appropriato nel tuo scenario.

Answer 3

Grazie per i consigli e le idee di tutti. Alla fine ho trovato una soluzione utile. Mr inspectorG4dget ha fatto luce su questo.

Utilizza il modulo bisect dalla libreria standard di python.

modifica: il modulo bisect esegue la ricerca binaria per trovare la posizione di inserimento di un valore in una lista ordinata. quindi riduce il numero di confronti, a differenza della mia precedente soluzione.

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