python - 在A和B之间交换元素以获得总和相等

Question

我们有两个长度相等的数组，A和B同样，对于每个i：对于某些0 <= a_i, b_i <= m。我们要检查1<=m<= 1000000的某个项和A的某个项之间的单个交换是否会使数组的和相等。
考虑以下解决方案：

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

如果你能解释一下最后一个B条款背后的原因，我会很高兴的。
Source of the problem

Answer 1

如果有这样的交换，那么两个值之间的差额必须是总和差额的一半。交换两个值意味着两个列表的总和将发生相同的变化，一个上升，另一个下降。这两个变化必须加起来等于交换前和之间的差，并且两个和的变化值相同（+d和-d，或者值delta，这是两个交换值之间的差）。
首先，该函数将d计算为和之间的增量，即和增量注意sum_a可能大于sum_b，此时结果sum_b - sum_a为负这仅仅意味着B中必须有一个值小于A中的目标值，然后交换将减少sum_a并增加sum_b以使它们相等。如果和增量的奇偶性是奇数而不是偶数，则永远找不到值增量是和增量的一半，因此函数此时返回False。d的最终值是值delta，即两个交换值之间的差值。记住，值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是否仍在[0-m]范围内：
b_value - d测试在A中查找的数字是否仍然是正数。
0 <= B[i] - d测试所需数量是否仍不大于B[i] - d <= m；可能是m接近且B[i]为阴性。
d包含count中数字的计数；如果A为真，则a中至少有一个这样的数字。这是可以交换的数字。
需要进行范围测试，因为count[B[i] - d] > 0列表只保存从0到m（包括0到m）的数字计数，而不包含负数或大于counted的数字计数。
使用集合而不是计数函数可以改进该函数不需要知道一个数字出现在m中的多少次，只是它存在。这将使边界检查过时，因为超出界限的数字根本不会出现在A的一组值中。
一旦我们有了一组a值，我们就可以使用disjoint，通过应用delta来测试这组b值是否A：

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)

如果set.isdisjoint()中的值等于A中的值减去delta，则返回true。python只循环B循环，直到找到匹配（此时集合不是不相交的，并且b - delta for b in B将结果反转为true），或者循环已用尽，因此在not中找不到这样的值，并且集合是不相交的。
所示的A函数还有一个问题：它需要的内存比需要的内存多得多，而且与counter() object相比非常慢，后者在中实现了优化的循环来进行计数acollections.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's 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的set功能，对于长度为1000的输入来说，这样做大约快17倍！
这个故事的寓意是：用你所选择的语言使用最好的工具，批判性地思考解决问题所需要的东西。python的内置类型和操作通常可以让您避免在python字节码中运行关键循环，从而显著减少算法的恒定时间因子。