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 при сохранении порядка и удалении самого старого элемента
  • Циркулярная ссылка с списками python
  • Определите дубликаты в списке списков и суммируйте их последние позиции
  • Найти все последовательные подпоследовательности длины n в последовательности
  • Сравнение двух списков для поиска большего списка
  • Convert For Loop to List Consrehension: тестирование, если элементы из списка 2 являются частичным совпадением для элементов в списке 1
  • Python: понимание разницы между добавлением и расширением
  • Python - изменения счетных знаков
  • Сравнение значений в двух списках в Python
  • Python - групповые дубликаты в списке списков по индексу
  •  
    Interesting Posts for Van-Lav

    Почему объект pylint указывает на имена имен одиночных символов?

    Могут ли параллельные обходы выполняться в MATLAB так же, как в Python?

    Создание / включение Boost.Python в VS2013

    PyQt: Получение данных главного окна из диалогового окна?

    Передача списка при сохранении оригинала

    Вложенная петля Python с генераторами не работает (в некоторых случаях)?

    Сигнал PyQt с аргументами произвольного типа / эквивалент PyQt_PyObject для сигналов нового стиля

    Python ascii utf unicode

    Получить str-ревью с двойными кавычками Python

    Ошибка при вызове баз метакласса: аргумент функции () должен быть кодом, а не str

    Разница между `yield from foo ()` и `for x в foo (): yield x`

    Получить информацию о часовом поясе системы в Python?

    SymPy / SciPy: решение системы обыкновенных дифференциальных уравнений с различными переменными

    Замена импорта Python отличается между 3.4.6 и 3.5.2

    Как сохранить секрет ключа разработчика в сценарии Python, который размещен на GitHub

    Python - лучший язык программирования в мире.