python - 2 danh sách và tìm sản phẩm tối đa từ 2 danh sách

Question

Tôi có hai danh sách được làm bằng số (số nguyên); cả hai đều có 2 triệu yếu tố độc đáo.

Tôi muốn tìm số một trong danh sách 1 và b từ danh sách 2, đó -

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

đây là những gì tôi đã đưa ra:

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 

bất cứ đề nghị? chỉnh sửa: phương pháp của tôi quá chậm. Sẽ mất hơn một ngày.

Answer 1

Dưới đây là một giải pháp tuyến tính thời gian (sau khi phân loại):

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) 

một cách đơn giản:

• bắt đầu từ mức cao nhất và thấp nhất từ ​​mỗi danh sách
• trong khi sản phẩm của họ ít hơn so với mục tiêu, chuyển tiếp sma ll mục
• khi sản phẩm trở nên lớn hơn mục tiêu của bạn, thúc đẩy sự lớn-item cho đến khi nó đi sau một lần nữa

Bằng cách này, bạn sẽ được bảo đảm để đi qua mỗi danh sách chỉ một lần. Nó sẽ trả lại False nếu nó không thể tìm thấy bất cứ điều gì đủ nhỏ, nếu không nó sẽ trả lại sản phẩm và cặp sản xuất nó.

Mẫu đầu ra:

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

Điều này có thể nhanh hơn.

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) 

Lưu ý rằng sắp xếp danh sách tại chỗ; điều này nhanh hơn, nhưng có thể hoặc không phù hợp trong kịch bản của bạn.

Answer 3

Cảm ơn lời khuyên và ý tưởng của mọi người. Cuối cùng tôi đã đưa ra giải pháp hữu ích. Ông thanh traG4dget chiếu sáng một cái này.

Nó sử dụng mô-đun bisect từ thư viện chuẩn của python.

chỉnh sửa: mô-đun nhị phân thực hiện tìm kiếm nhị phân để tìm vị trí chèn của một giá trị trong danh sách được sắp xếp. do đó nó làm giảm số lượng so sánh, không giống như giải pháp trước đây của tôi.

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