Самый быстрый алгоритм для выполнения N * M итераций в Python

Question

Я не человек алгоритма, так что простите за наивность вопроса.

У меня есть список A, содержащий элементы 100K элементов. У меня есть другой список B, содержащий 100K элементов. Допустим, a является элементом из списка A, b является элементом из списка B. Я хочу выяснить те (a, b) комбинации, сумма которых меньше 100.

Один очевидный способ сделать это заключается в следующем:

results = []
for a in A:
    for b in B:
        if (a+b) < 100:
            results.append((a,b))     

, но временная сложность этого подхода составляет O (n * m) = 100K * 100K, что довольно много. Существует ли какой-нибудь быстрый алгоритм, способный более эффективно вычислить желаемый результат - с точки зрения памяти и времени. Если да, можно ли это реализовать на python?

Answer 1

Нет, вы не можете стать лучше, чем это в худшем случае. Рассмотрим патологический случай, когда каждая комбинация A и B должна быть добавлена ​​в список:

A = list(range(0, -n, -1))
B = list(range(0, -m, -1))

Поскольку каждая пара должна быть добавлена, вы выполняете O(m * n) операций.

Если вам нужно только посчитать количество комбинаций, это может быть другая история.

Answer 2

Ваш критерий - это a + b < 100, который можно определить как диапазон. В этом случае я определил его как wanted_result_range = range(0, 100), так как ваши списки A и B содержат только положительные числа, поэтому результаты будут только положительными значениями.

Запустите следующий скрипт, и вы увидите, насколько быстрее мой подход, чем "фронтальный", который вы упомянули. Мое решение будет плохим, если будет определено более широкое значение wanted_result_range.

import timeit
# http://docs.python.org/3.3/library/timeit.html

print "\nTiming execution times\n"

version1="""
results1 = []
list_A = range(1000)
list_B = range(1000)
wanted_result_range = range(0, 100)
d1 = {} 
l3 = []
for key in list_A: 
    d1[key] = True # Value associated to key is not important and can be any value 
for wanted_result in wanted_result_range:
    for key2 in list_B: 
        if ((wanted_result-key2) in d1): 
            results1.append((key2,wanted_result-key2))
"""
print("Version 1 - Hash table (dictionary) approach")
print(timeit.repeat(version1, number=10, repeat=4))
print('END Version 1\n')

version2="""
results2 = []
list_A = range(1000)
list_B = range(1000)
for a in list_A:
    for b in list_B:
        if (a+b) < 100:
            results2.append((a,b))
"""
print("Version 2 - Frontal approach")
print(timeit.repeat(version2, number=10, repeat=4))
print('END Version 2\n')

Answer 3

Сортировка обоих списков (O(n log n) и O(m log m), возможно, меньше, если значения ограничены).

Затем вы можете просто найти для каждого a в A наибольшее b в B, такое что (a+b) < 100. Каждый меньший b также будет удовлетворять этому условию.

Нахождение наибольшего значения b для некоторых значений a можно выполнить с помощью бинарного поиска, чтобы найти нижнюю границу в B. И, начав с наибольшего значения a, уменьшив его, вы можете сохранить список b s, соответствующий предыдущему a, поскольку сумма будет меньше.