通过列表旋转找到最小绝对差和的最快算法
Fastest Algorithm to Find the Minimum Sum of Absolute Differences through List Rotation
通过从左到右旋转 2 个列表，在给定 的情况下，找到两个列表中每个对应项之间差异的绝对值的最小可能总和相同长度。
旋转样本：
List [0, 1, 2, 3, 4, 5] rotated to the left = [1, 2, 3, 4, 5, 0]
List [0, 1, 2, 3, 4, 5] rotated to the right= [5, 0, 1, 2, 3, 4]
绝对差之和：
List 1 = [1, 2, 3, 4]
List 2 = [5, 6, 7, 8]
Sum of Abs. Diff. = |1-5| + |2-6| + |3-7| + |4-8| = 16
再一次，对于任意长度的列表和整数值，任务是通过简单地旋转到一个或两个列表的 left/right 来寻找最小可能的总和。
我对旋转和获取最小绝对差和没有问题。我只想知道更聪明的方法，因为我的算法会检查每一种可能的组合，这很慢。
这是我的暴力破解方法：
list1 = [45, 21, 64, 33, 49]
list2 = [90, 12, 77, 52, 28]
choices = [] # Put all possible sums into a list to find the minimum value.
for j in range(len(list1)): # List1 does a full rotation
total = 0
for k in range(len(list1)):
total += abs(list1[k] - list2[k])
list1.append(list1.pop(0))
choices.append(total)
print(min(choices))
什么是更聪明的方法？我也希望能有更短的代码和时间复杂度。
我设法通过应用生成器使其更快。感谢@kuriboh 的想法！但是由于我在生成器实现方面仍然是新手，所以只想知道这是否是实现它以减少我的时间复杂度的最佳方式，尤其是对于我的循环。 我们还能比这个配置走得更快吗？
list1 = [45, 21, 64, 33, 49]
list2 = [90, 12, 77, 52, 28]
choices = []
l = len(list1)
for j in range(l):
total = sum([abs(int(list1[k])-int(list2[k])) for k in range(l)])
list1.append(list1.pop(0))
choices.append(total)
print(min(choices))
由于 Python 将负索引视为从右端开始计数，您可以对 list1 的绝对值求和减去（list2 偏移 k），其中 0 ≤ k < len (list1) 作为
sum(abs(list1[i] - list2[i - k]) for i in range(len(list1)))
如果您想要所有这些值中的最小值
length = len(list1)
min(sum(abs(list1[i] - list2[i - k]) for i in range(length))
for k in range(length))
此代码仍然是 O(n^2)，但进行的推入和弹出操作要少得多。
我真的想不出有什么方法可以让算法比 O(n^2) 更快。
我还没有破解完整的问题，但在输入值都是0或1（或任何两个不同的值，或[=15=中的任何一个）的特殊情况下] 不同的值，但我们需要另一个想法才能更进一步），我们可以通过应用快速卷积得到一个 O(n log n) 时间算法。
我们的想法是计算所有绝对差的和作为 List1 * reverse(1 - List2) + (1 - List1) * reverse(List2) 其中 1 - List 表示执行该操作 point-wise 和 * 表示循环卷积（可计算在使用一对 FFT 的时间 O(n log n)）。这里循环卷积的定义是
n-1
__
\
(f * g)(i) = /_ f(j) g((i - j) mod n).
j=0
用List1代替f，用reverse(1 - List2)代替g，我们得到
n-1
__
\
(List1 * reverse(1 - List2))(i) = /_ List1(j) (1 - List2((n-1-(i-j)) mod n))
j=0
n-1
__
\
= /_ List1(j) (1 - List2((j-(i+1)) mod n)).
j=0
当且仅当 List1(j) = 1 和 List2((j-(i+1)) mod n) = 0 时，乘积 List1(j) (1 - List2((j-(i+1)) mod n)) 为 1，否则为 0。因此，卷积的 i 值计算 List1 具有 1 偏移量的位置数 i+1 循环到 List2 具有 [=] 的左侧13=]。其他卷积计数0s对应1s。鉴于我们的输入限制，这是绝对差的总和。
代码：
import numpy
def convolve_circularly(a1, a2):
return numpy.round(numpy.abs(numpy.fft.ifft(numpy.fft.fft(a1) * numpy.fft.fft(a2))))
def min_sum_abs_diff(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)[::-1]
return numpy.min(convolve_circularly(a1, 1 - a2) + convolve_circularly(1 - a1, a2))
def slow_min_sum_abs_diff(a1, a2):
return min(
sum(abs(a1[i] - a2[i - k]) for i in range(len(a1))) for k in range(len(a2))
)
def main():
n = 100
for r in range(100000):
a1 = numpy.random.randint(2, size=n)
a2 = numpy.random.randint(2, size=n)
r = min_sum_abs_diff(a1, a2)
slow_r = slow_min_sum_abs_diff(a1, a2)
if r != slow_r:
print(a1, a2, r, slow_r)
break
if __name__ == "__main__":
main()
您的原始答案和 Frank 接受的答案的优化组合：
min(list1.append(list1.pop(0)) or
sum(abs(x - y) for x, y in zip(list1, list2))
for _ in list1)
像那样旋转有点脏，但是嘿，你要求的是“最快”:-)
列表长度为 1000 的基准测试：
original Frank_Yellin superb_rain
127 ms 164 ms 125 ms
140 ms 170 ms 117 ms
134 ms 166 ms 116 ms
124 ms 161 ms 126 ms
135 ms 164 ms 126 ms
基准代码：
from timeit import repeat
from random import shuffle
def original(list1, list2):
choices = [] # Put all possible sums into a list to find the minimum value.
for j in range(len(list1)): # List1 does a full rotation
total = 0
for k in range(len(list1)):
total += abs(list1[k] - list2[k])
list1.append(list1.pop(0))
choices.append(total)
return min(choices)
def Frank_Yellin(list1, list2):
length = len(list1)
return min(sum(abs(list1[i] - list2[i - k]) for i in range(length))
for k in range(length))
def superb_rain(list1, list2):
return min(list1.append(list1.pop(0)) or
sum(abs(x - y) for x, y in zip(list1, list2))
for _ in list1)
funcs = [
(10, original),
(10, Frank_Yellin),
(10, superb_rain),
]
list1 = list(range(1000))
list2 = list1.copy()
shuffle(list2)
for _, f in funcs:
print(f(list1, list2))
for _, f in funcs:
print(f.__name__.center(15), end='')
print()
for _ in range(5):
for number, f in funcs:
t = min(repeat(lambda: f(list1, list2), number=number)) / number
print('%8d ms ' % (t * 1e3), end='')
print()
的基准测试和我的两个 NumPy 解决方案。
500 个随机整数 0 或 1:
189.62414 ms slow_min_sum_abs_diff # Like Frank's
49.75403 ms less_slow_min_sum_abs_diff # My NumPy
10.13092 ms lesser_slow_min_sum_abs_diff # My Numpy
0.85030 ms min_sum_abs_diff # David's
0.27434 ms array_conversion # for comparison
1000 个随机整数 0 或 1:
857.02381 ms slow_min_sum_abs_diff
100.26820 ms less_slow_min_sum_abs_diff
28.55692 ms lesser_slow_min_sum_abs_diff
1.67077 ms min_sum_abs_diff
0.49301 ms array_conversion
1000 个从 -106 到 106 的随机整数（没有大卫的，因为它不是为此而制作的，会产生错误的结果):
829.18451 ms slow_min_sum_abs_diff
89.97418 ms less_slow_min_sum_abs_diff
22.69516 ms lesser_slow_min_sum_abs_diff
我不明白 David 的解决方案，但他自己的验证很有说服力，我自己做了更多，将每个更快的解决方案与 next-slower 的解决方案进行了比较（这实际上就是我编写 NumPy 解决方案的原因，所以我可以用更大的输入来测试大卫的）：
passed: less_slow_min_sum_abs_diff (220 tests with n=100)
passed: lesser_slow_min_sum_abs_diff (89 tests with n=300)
passed: min_sum_abs_diff (146 tests with n=1000)
passed: min_sum_abs_diff (5 tests with n=10000)
在 repl.it 的 Python 3.8.2 64 位上完成的基准测试。
代码：
import numpy
from timeit import repeat, default_timer as timer
def array_conversion(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)
def convolve_circularly(a1, a2):
return numpy.round(numpy.abs(numpy.fft.ifft(numpy.fft.fft(a1) * numpy.fft.fft(a2))))
def min_sum_abs_diff(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)[::-1]
return numpy.min(convolve_circularly(a1, 1 - a2) + convolve_circularly(1 - a1, a2))
def slow_min_sum_abs_diff(a1, a2):
return min(
sum(abs(a1[i] - a2[i - k]) for i in range(len(a1))) for k in range(len(a2))
)
def less_slow_min_sum_abs_diff(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)
return min(
numpy.abs(a1 - numpy.roll(a2, k)).sum()
for k in range(len(a2))
)
def lesser_slow_min_sum_abs_diff(a1, a2):
n = len(a2)
a1 = numpy.array(a1)
a2 = numpy.concatenate((a2, a2))
return min(
numpy.abs(a1 - a2[k:k+n]).sum()
for k in range(n)
)
def random_arrays(n):
a1 = numpy.random.randint(2, size=n).tolist()
a2 = numpy.random.randint(2, size=n).tolist()
return a1, a2
def verify(candidate, reference, n, timelimit=1):
t0 = timer()
count = 0
while timer() - t0 < timelimit:
a1_orig, a2_orig = random_arrays(n)
a1, a2 = a1_orig.copy(), a2_orig.copy()
expect = reference(a1, a2)
assert a1 == a1_orig and a2 == a2_orig
result = candidate(a1, a2)
assert a1 == a1_orig and a2 == a2_orig
if result != expect:
print('wrong:')
print(' expected', expect, 'by', reference.__name__)
print(' got', result, 'by', candidate.__name__)
print(' a1:', a1)
print(' a2:', a2)
break
count += 1
else:
print('passed:', candidate.__name__, f'({count} tests with {n=})')
def main():
if 1:
verify(less_slow_min_sum_abs_diff, slow_min_sum_abs_diff, 100)
verify(lesser_slow_min_sum_abs_diff, less_slow_min_sum_abs_diff, 300)
verify(min_sum_abs_diff, lesser_slow_min_sum_abs_diff, 1000)
verify(min_sum_abs_diff, lesser_slow_min_sum_abs_diff, 10000)
print()
funcs = [
(10, slow_min_sum_abs_diff),
(100, less_slow_min_sum_abs_diff),
(100, lesser_slow_min_sum_abs_diff),
(1000, min_sum_abs_diff),
(1000, array_conversion),
]
a1, a2 = random_arrays(1000)
for _ in range(3):
for number, func in funcs:
t = min(repeat(lambda: func(a1, a2), number=number)) / number
print('%11.5f ms ' % (t * 1e3), func.__name__)
print()
if __name__ == "__main__":
main()
print('done')
通过从左到右旋转 2 个列表，在给定 的情况下，找到两个列表中每个对应项之间差异的绝对值的最小可能总和相同长度。
旋转样本：
List [0, 1, 2, 3, 4, 5] rotated to the left = [1, 2, 3, 4, 5, 0]
List [0, 1, 2, 3, 4, 5] rotated to the right= [5, 0, 1, 2, 3, 4]
绝对差之和：
List 1 = [1, 2, 3, 4]
List 2 = [5, 6, 7, 8]
Sum of Abs. Diff. = |1-5| + |2-6| + |3-7| + |4-8| = 16
再一次，对于任意长度的列表和整数值，任务是通过简单地旋转到一个或两个列表的 left/right 来寻找最小可能的总和。
我对旋转和获取最小绝对差和没有问题。我只想知道更聪明的方法，因为我的算法会检查每一种可能的组合，这很慢。
这是我的暴力破解方法：
list1 = [45, 21, 64, 33, 49]
list2 = [90, 12, 77, 52, 28]
choices = [] # Put all possible sums into a list to find the minimum value.
for j in range(len(list1)): # List1 does a full rotation
total = 0
for k in range(len(list1)):
total += abs(list1[k] - list2[k])
list1.append(list1.pop(0))
choices.append(total)
print(min(choices))
什么是更聪明的方法？我也希望能有更短的代码和时间复杂度。
我设法通过应用生成器使其更快。感谢@kuriboh 的想法！但是由于我在生成器实现方面仍然是新手，所以只想知道这是否是实现它以减少我的时间复杂度的最佳方式，尤其是对于我的循环。 我们还能比这个配置走得更快吗？
list1 = [45, 21, 64, 33, 49]
list2 = [90, 12, 77, 52, 28]
choices = []
l = len(list1)
for j in range(l):
total = sum([abs(int(list1[k])-int(list2[k])) for k in range(l)])
list1.append(list1.pop(0))
choices.append(total)
print(min(choices))
由于 Python 将负索引视为从右端开始计数，您可以对 list1 的绝对值求和减去（list2 偏移 k），其中 0 ≤ k < len (list1) 作为
sum(abs(list1[i] - list2[i - k]) for i in range(len(list1)))
如果您想要所有这些值中的最小值
length = len(list1)
min(sum(abs(list1[i] - list2[i - k]) for i in range(length))
for k in range(length))
此代码仍然是 O(n^2)，但进行的推入和弹出操作要少得多。
我真的想不出有什么方法可以让算法比 O(n^2) 更快。
我还没有破解完整的问题，但在输入值都是0或1（或任何两个不同的值，或[=15=中的任何一个）的特殊情况下] 不同的值，但我们需要另一个想法才能更进一步），我们可以通过应用快速卷积得到一个 O(n log n) 时间算法。
我们的想法是计算所有绝对差的和作为 List1 * reverse(1 - List2) + (1 - List1) * reverse(List2) 其中 1 - List 表示执行该操作 point-wise 和 * 表示循环卷积（可计算在使用一对 FFT 的时间 O(n log n)）。这里循环卷积的定义是
n-1
__
\
(f * g)(i) = /_ f(j) g((i - j) mod n).
j=0
用List1代替f，用reverse(1 - List2)代替g，我们得到
n-1
__
\
(List1 * reverse(1 - List2))(i) = /_ List1(j) (1 - List2((n-1-(i-j)) mod n))
j=0
n-1
__
\
= /_ List1(j) (1 - List2((j-(i+1)) mod n)).
j=0
当且仅当 List1(j) = 1 和 List2((j-(i+1)) mod n) = 0 时，乘积 List1(j) (1 - List2((j-(i+1)) mod n)) 为 1，否则为 0。因此，卷积的 i 值计算 List1 具有 1 偏移量的位置数 i+1 循环到 List2 具有 [=] 的左侧13=]。其他卷积计数0s对应1s。鉴于我们的输入限制，这是绝对差的总和。
代码：
import numpy
def convolve_circularly(a1, a2):
return numpy.round(numpy.abs(numpy.fft.ifft(numpy.fft.fft(a1) * numpy.fft.fft(a2))))
def min_sum_abs_diff(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)[::-1]
return numpy.min(convolve_circularly(a1, 1 - a2) + convolve_circularly(1 - a1, a2))
def slow_min_sum_abs_diff(a1, a2):
return min(
sum(abs(a1[i] - a2[i - k]) for i in range(len(a1))) for k in range(len(a2))
)
def main():
n = 100
for r in range(100000):
a1 = numpy.random.randint(2, size=n)
a2 = numpy.random.randint(2, size=n)
r = min_sum_abs_diff(a1, a2)
slow_r = slow_min_sum_abs_diff(a1, a2)
if r != slow_r:
print(a1, a2, r, slow_r)
break
if __name__ == "__main__":
main()
您的原始答案和 Frank 接受的答案的优化组合：
min(list1.append(list1.pop(0)) or
sum(abs(x - y) for x, y in zip(list1, list2))
for _ in list1)
像那样旋转有点脏，但是嘿，你要求的是“最快”:-)
列表长度为 1000 的基准测试：
original Frank_Yellin superb_rain
127 ms 164 ms 125 ms
140 ms 170 ms 117 ms
134 ms 166 ms 116 ms
124 ms 161 ms 126 ms
135 ms 164 ms 126 ms
基准代码：
from timeit import repeat
from random import shuffle
def original(list1, list2):
choices = [] # Put all possible sums into a list to find the minimum value.
for j in range(len(list1)): # List1 does a full rotation
total = 0
for k in range(len(list1)):
total += abs(list1[k] - list2[k])
list1.append(list1.pop(0))
choices.append(total)
return min(choices)
def Frank_Yellin(list1, list2):
length = len(list1)
return min(sum(abs(list1[i] - list2[i - k]) for i in range(length))
for k in range(length))
def superb_rain(list1, list2):
return min(list1.append(list1.pop(0)) or
sum(abs(x - y) for x, y in zip(list1, list2))
for _ in list1)
funcs = [
(10, original),
(10, Frank_Yellin),
(10, superb_rain),
]
list1 = list(range(1000))
list2 = list1.copy()
shuffle(list2)
for _, f in funcs:
print(f(list1, list2))
for _, f in funcs:
print(f.__name__.center(15), end='')
print()
for _ in range(5):
for number, f in funcs:
t = min(repeat(lambda: f(list1, list2), number=number)) / number
print('%8d ms ' % (t * 1e3), end='')
print()
500 个随机整数 0 或 1:
189.62414 ms slow_min_sum_abs_diff # Like Frank's
49.75403 ms less_slow_min_sum_abs_diff # My NumPy
10.13092 ms lesser_slow_min_sum_abs_diff # My Numpy
0.85030 ms min_sum_abs_diff # David's
0.27434 ms array_conversion # for comparison
1000 个随机整数 0 或 1:
857.02381 ms slow_min_sum_abs_diff
100.26820 ms less_slow_min_sum_abs_diff
28.55692 ms lesser_slow_min_sum_abs_diff
1.67077 ms min_sum_abs_diff
0.49301 ms array_conversion
1000 个从 -106 到 106 的随机整数（没有大卫的，因为它不是为此而制作的，会产生错误的结果):
829.18451 ms slow_min_sum_abs_diff
89.97418 ms less_slow_min_sum_abs_diff
22.69516 ms lesser_slow_min_sum_abs_diff
我不明白 David 的解决方案，但他自己的验证很有说服力，我自己做了更多，将每个更快的解决方案与 next-slower 的解决方案进行了比较（这实际上就是我编写 NumPy 解决方案的原因，所以我可以用更大的输入来测试大卫的）：
passed: less_slow_min_sum_abs_diff (220 tests with n=100)
passed: lesser_slow_min_sum_abs_diff (89 tests with n=300)
passed: min_sum_abs_diff (146 tests with n=1000)
passed: min_sum_abs_diff (5 tests with n=10000)
在 repl.it 的 Python 3.8.2 64 位上完成的基准测试。
代码：
import numpy
from timeit import repeat, default_timer as timer
def array_conversion(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)
def convolve_circularly(a1, a2):
return numpy.round(numpy.abs(numpy.fft.ifft(numpy.fft.fft(a1) * numpy.fft.fft(a2))))
def min_sum_abs_diff(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)[::-1]
return numpy.min(convolve_circularly(a1, 1 - a2) + convolve_circularly(1 - a1, a2))
def slow_min_sum_abs_diff(a1, a2):
return min(
sum(abs(a1[i] - a2[i - k]) for i in range(len(a1))) for k in range(len(a2))
)
def less_slow_min_sum_abs_diff(a1, a2):
a1 = numpy.array(a1)
a2 = numpy.array(a2)
return min(
numpy.abs(a1 - numpy.roll(a2, k)).sum()
for k in range(len(a2))
)
def lesser_slow_min_sum_abs_diff(a1, a2):
n = len(a2)
a1 = numpy.array(a1)
a2 = numpy.concatenate((a2, a2))
return min(
numpy.abs(a1 - a2[k:k+n]).sum()
for k in range(n)
)
def random_arrays(n):
a1 = numpy.random.randint(2, size=n).tolist()
a2 = numpy.random.randint(2, size=n).tolist()
return a1, a2
def verify(candidate, reference, n, timelimit=1):
t0 = timer()
count = 0
while timer() - t0 < timelimit:
a1_orig, a2_orig = random_arrays(n)
a1, a2 = a1_orig.copy(), a2_orig.copy()
expect = reference(a1, a2)
assert a1 == a1_orig and a2 == a2_orig
result = candidate(a1, a2)
assert a1 == a1_orig and a2 == a2_orig
if result != expect:
print('wrong:')
print(' expected', expect, 'by', reference.__name__)
print(' got', result, 'by', candidate.__name__)
print(' a1:', a1)
print(' a2:', a2)
break
count += 1
else:
print('passed:', candidate.__name__, f'({count} tests with {n=})')
def main():
if 1:
verify(less_slow_min_sum_abs_diff, slow_min_sum_abs_diff, 100)
verify(lesser_slow_min_sum_abs_diff, less_slow_min_sum_abs_diff, 300)
verify(min_sum_abs_diff, lesser_slow_min_sum_abs_diff, 1000)
verify(min_sum_abs_diff, lesser_slow_min_sum_abs_diff, 10000)
print()
funcs = [
(10, slow_min_sum_abs_diff),
(100, less_slow_min_sum_abs_diff),
(100, lesser_slow_min_sum_abs_diff),
(1000, min_sum_abs_diff),
(1000, array_conversion),
]
a1, a2 = random_arrays(1000)
for _ in range(3):
for number, func in funcs:
t = min(repeat(lambda: func(a1, a2), number=number)) / number
print('%11.5f ms ' % (t * 1e3), func.__name__)
print()
if __name__ == "__main__":
main()
print('done')