2列表，并从2个列表中查找最大产品

我有两个由数字组成的列表（整数）; 都有200万个独特的元素。

我想查找列表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

有什么建议么？ 编辑：我的方法太慢了。 这将需要超过一天的时间。

---

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

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)

---

感谢大家的建议和想法。 我终于想出了有用的解决方案。 检查员G4dget先生点亮了这张照片。

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

编辑：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

---

这可能会更快。

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)

请注意，它就地对列表进行排序; 这是更快，但可能会或可能不适合您的情况。

链接地址: http://www.djcxy.com/p/66261.html

上一篇: 2 lists, and finding maximum product from 2 lists

下一篇: Youtube API: no way to get liked videos from user's activity feed