Python - 2 Listen, und Suche nach maximal Produkt aus 2 Listen

Question

Ich habe zwei Listen aus Zahlen (Integer); Beide haben 2 Millionen einzigartige Elemente.

I Nummer ein finden möchten aus der Liste 1 und b aus der Liste 2, dass -

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

hier ist, was ich kam mit:

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 

irgendwelche Vorschläge? edit: meine Methode ist zu langsam. Es würde mehr als einen Tag dauern.

Answer 1

Hier ist eine lineare Zeitlösung (nach dem Sortieren):

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) 

Einfach gesagt:

• Start aus dem höchsten und dem niedrigsten aus jeder Liste
• Während ihr Produkt weniger als das Ziel ist, fördern Sie den SMA ll-Artikel
• , sobald das Produkt wird größer als Ihr Ziel, den großen Punkt vorrücken, bis er unten wieder

Auf diese Weise geht, sind Sie garantiert nur einmal durch jede Liste gehen. Es wird False zurückgegeben, wenn es nichts klein genug finden konnte, sonst wird es das Produkt und das Paar, das es produziert, zurückgeben.

Beispielausgabe:

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

Dies könnte schneller sein.

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) 

Beachten Sie, dass es die Listen an Ort und Stelle sortiert; Dies ist schneller, aber möglicherweise in Ihrem Szenario nicht angemessen.

Answer 3

Vielen Dank für Ihre Hinweise und Ideen. Endlich habe ich eine brauchbare Lösung gefunden. Mr. InspectorG4dget beleuchtete dieses Licht.

Es verwendet bisect Modul aus Python-Standard-Bibliothek.

edit: halbiert Modul führt binäre Suche durch, um die Einfügeposition eines Wertes in einer sortierten Liste zu finden. Daher reduziert es die Anzahl der Vergleiche im Gegensatz zu meiner vorherigen Lösung.

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