У нас есть два массива одинаковой длины,
A
иB
также для каждогоi
:0 <= a_i, b_i <= m
для некоторого1<=m<= 1000000
. Мы хотим проверить, будет ли один обмен между некоторым членомA
и некоторым членомB
сделать суммы массивов равными.
Рассмотрим следующее решение:
def fast_solution(A, B, m):
n = len(A)
sum_a = sum(A)
sum_b = sum(B)
d = sum_b - sum_a
if d % 2 == 1:
return False
d //= 2
count = counting(A, m) # returns a mapping <integer, #occurrences in A>
for i in range(n):
if 0 <= B[i] - d and B[i] - d <= m and count[B[i] - d] > 0:
return True
return False
Я был бы рад, если бы вы могли объяснить причины последнего предложения if
.
Если есть такой обмен, то разница между этими двумя значениями должна быть вдвое меньше разницы в суммах. Обмен двумя значениями означает, что сумма обоих списков изменится, один вверх, другой вниз - на ту же сумму. Эти два изменения должны дополнять разницу между суммами перед свопом, и обе суммы изменяются на одно и то же значение (+d
и -d
, или значение delta, что является разницей между двумя измененными значениями).
Во-первых, функция вычисляет d
как дельта между суммами, дельта суммы. Обратите внимание, что sum_a
может быть больше sum_b
, и в этот момент результат sum_b - sum_a
отрицателен. Это просто означает, что в B
должно быть значение, которое меньше целевого значения в A
, тогда swap уменьшит sum_a
и увеличит sum_b
чтобы сделать их равными. Если четность дельта суммы нечетная, а не четная, вы никогда не найдете дельта значения, равную половине дельта суммы, поэтому функция возвращает False
в этой точке. Конечным значением d
является значение delta, величина разницы между двумя измененными значениями. Помните, что значение delta равно половине суммы дельта.
Алгоритм подсчитывает все значения в A
, а затем проверяет все значения в B
Можно было бы поменять местами два значения между только A
и B
, если имеется значение в B
, которая отличается d
от значения в A
. Значение в A
для обмена с B
должно быть равно b_value - d
. Для отрицательного d
(sum_a > sum_b
), который сделает b_value
меньше, для положительного d
, для которого b_value
будет большим числом.
Тест if
проверяет, есть ли значение в B - d
доступное в A
, но оно сначала проверяет, находится ли b_value - d
в пределах диапазона [0-m]:
0 <= B[i] - d
если искомое число в остается положительным числом.B[i] - d <= m
тестов, если искомое число все еще не больше m
; это могло бы быть, если B[i]
был близок и d
отрицателен.count
содержит числа для чисел в A
; если count[B[i] - d] > 0
истинно, то в есть хотя бы одно такое число. Это число, которое можно поменять местами. Тест диапазона необходим, потому что counted
список содержит только числа от 0 до m (включительно), а не для отрицательных чисел или для чисел, больших, чем m
.
Функция может быть улучшена с помощью набора вместо функции подсчета. Нет необходимости знать, сколько раз число появляется в A
, только что оно существует. Это привело бы к тому, что граничные проверки устарели, потому что числа из числа ограничений просто не будут присутствовать в наборе значений A
Как только у нас есть набор значений A, мы можем проверить, не является ли это множество непересекающимся из набора значений b с применяемой delta, используя set.isdisjoint()
:
def faster_solution(A, B, m=None): # m is ignored in this version
delta = sum(A) - sum(B)
if delta % 2 == 1:
return False
delta //= 2
return not set(A).isdisjoint(b - delta for b in B)
Это возвращает значение True, если в A
есть значение, равное значению в B
минус дельта. Python будет только перебирать b - delta for b in B
цикле до тех пор, пока не будет найдено совпадение (в этот момент множества не пересекаются, а not
инверсии, которые приводят к True) или цикл исчерпан, и поэтому такое значение не является найденных в A
и множества оказываются непересекающимися.
Показанная функция counter()
имеет другую проблему: для этого требуется больше памяти, чем требуется, и она очень медленная по сравнению с объектом collections.Counter()
который имеет оптимизированный цикл для выполнения подсчета. Counter()
использует словарь (хэш-карту) для хранения счетчиков только для счетчиков, превышающих 0.
Установленное выше решение превосходит "быстрое решение":
>>> import timeit, random
>>> m = 1000000
>>> testdata = [random.randrange(m + 1) for _ in range(1000)]
>>> testinputs = (testdata[:], testdata[:])
>>> random.shuffle(testinputs[0]) # The order of A differs from B
>>> testinputs[1][-1] -= testinputs[1][-1] // 2 # now the two sums differ by an even amount, guaranteed to be in range
>>> assert testinputs[1][-1] > 0 # make sure the original random value was not 0 or 1.
>>> # note: It the *last value in B* that makes it possible to swap;
... # this is one of two worst-case scenarios (the other is even-delta-no-swap).
...
>>> assert fast_solution(*testinputs, m) # the original finds a solution
>>> assert faster_solution(*testinputs, m) # my version finds a solution
>>> timeit.timeit("f(*ab, m)", "from __main__ import fast_solution as f, testinputs as ab, m", number=1000)
2.3270092820748687
>>> timeit.timeit("f(*ab, m)", "from __main__ import faster_solution as f, testinputs as ab, m", number=1000)
0.13949943508487195
Не используя счетчик, и используя функцию набора Python, это примерно в 17 раз быстрее для входов длиной 1000!
Мораль истории: используйте лучшие инструменты, доступные на выбранном вами языке, и критически подумайте о том, что действительно необходимо для решения проблемы. Встроенные типы и операции Python часто позволяют избежать использования критических циклов в байт-коде Python, что значительно уменьшает коэффициенты постоянного времени алгоритма.
Этот цикл for в конце ищет каждый элемент массива B
Чтобы быть замененным элементом в индексе i
, он должен удовлетворять двум условиям:
B[i] - d
должно быть между 0
и m
. Вы можете представить себе 2 * d
сколько sum(B)
больше sum(A)
, поэтому, заменив B[i]
на B[i] - d
, массив A
с коэффициентом усиления d
и массивом B
потеряет его, увеличив разница на 2 * d
B[i] - d
должно существовать в A Это нехорошо для понимания, хотя переопределить d = d/2
в середине кода :)