Geek Answers Handbook

Python - 2 lists and finding the maximum product from 2 lists

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

I want to find the number a from list 1 and b from list 2, which is -

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

Here is 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 takes more than one day.

+7
source share
3 answers

Here's a time-linear 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 with the highest and lowest of each list
  • while their product is smaller than the target, promote a small item
  • Once the product is larger than your goal, advance the large item until it drops below.

Thus, you can go through each list only once. He will return False if he cannot find anything small enough, otherwise he will return the product and the pair that created it.

Output Example:

 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)
+3
source

Thanks for the tips and ideas. Finally, I came up with a useful solution. Mr. Inspector G4dget lit up in this world.

It uses the bisect module from the python standard library.

edit: The bisect module performs a binary search to find the insertion position of a value in a sorted list. therefore, it reduces the number of comparisons, unlike my previous solution.

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
+1
source

It could be faster.

 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)

Note that it sorts the lists in place; it is faster, but may or may not be suitable in your scenario.

0
source

More articles:


All Articles