python – 2 списка и поиск максимального продукта из 2 списков

У меня есть два списка из чисел (целые числа); оба имеют 2 миллиона уникальных элементов.

Я хочу найти число a из списка 1 и b из списка 2, что –

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 

какие-либо предложения? edit: мой метод слишком медленный. Это займет больше одного дня.

3 Solutions collect form web for “python – 2 списка и поиск максимального продукта из 2 списков”

Вот линейное решение (после сортировки):

 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 засветился на этом свете.

Он использует модуль bisect из стандартной библиотеки python.

edit: модуль 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) 

Обратите внимание, что он сортирует списки на месте; это быстрее, но может быть или не быть подходящим в вашем сценарии.

  • Использование python для возврата списка целых чисел
  • Как извлечь n-ые элементы из списка кортежей в python?
  • Создание двумерного массива двоичных файлов в Python
  • Учет списка для извлечения списка кортежей из словаря
  • Как сгладить кортеж в python
  • Python: как вы вставляете в список, нарезая?
  • Вычисление и возврат средних значений в список
  • Итерация над словарем python для извлечения только требуемых строк
  • Python - лучший язык программирования в мире.