python -2列表，并从2个列表中查找最大乘积

Question

我有两个由数字(整数)组成的列表；两个列表都有两百万个唯一的元素。

我想从列表1中找出数字a，从列表2中找出b，即-

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

这是我想出来的：

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)

简单地说：

从每个列表中最高和最低的项目开始，当他们的产品低于目标时，前进small-item

• once
• 产品变得比你的目标更大，前进大项目，直到它再次低于目标

这样，您就可以保证每个列表只浏览一次。如果找不到足够小的东西，它将返回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)

Answer 2

感谢大家的建议和想法。我终于想出了一个有用的解决方案。inspectorG4dget先生在这个问题上大放异彩。

它使用python标准库中的bisect模块。

编辑:二等分模块执行二进制搜索，以便在排序列表中找到值的插入位置。因此，它减少了比较的次数，这与我之前的解决方案不同。

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

Answer 3

这可能会更快。

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)

请注意，它会就地对列表进行排序；这会更快，但在您的场景中可能适合也可能不适合。