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

list, python

Solution

Here's a linear-time solution (after sorting):

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)

Simply put:

- start from the highest and lowest from each list

- while their product is less than the target, advance the small-item

- once the product becomes bigger than your goal, advance the big-item until it goes below again

This way, you're guaranteed to go through each list only once. It'll return `False` if it couldn't find anything small enough, otherwise it'll return the product and the pair that produced it.

Sample output:

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)

Problem

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 ``` any suggestions? edit : my method is too slow. It would take more than one day.

Original source