python - 2 lists, and finding maximum product from 2 lists

Question

I have two lists made of numbers(integers); both have 2 million unique elements.

I want to find number a from list 1 and b from list 2, that -

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

here's what I came up with:

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

有什么建议？编辑:我的方法太慢了.这将需要一天以上.

Answer 1

这是一个线性时间解决方案（排序后）：

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)

简单的说：

• 从每个列表中最高和最低的开始
• 当他们的产品低于目标时，推进小项目
• 一旦产品变得大于你的目标，就推进大项目，直到它再次低于你的目标

这样，您就可以保证每个列表只浏览一次。False如果找不到足够小的东西，它将返回，否则它将返回产品和生产它的对。

示例输出：

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)