假設我有兩個串列list_1和list_2
list_1 = [1, 5, 10]
list_2 = [3, 4, 15]
我想得到一個包含 list_1 和 list_2 元素的元組串列，這樣元組中數字之間的差異就在某個常數 c 之下。
例如，假設 c 是 2 那么我將擁有的元組將是：
[(1, 3), (5, 3), (5, 4)]
當然，可以遍歷兩個串列并檢查 2 個元素之間的差異是否小于 c，但這具有 n^2 的復雜性，我寧愿降低這種復雜性。
uj5u.com熱心網友回復：
以下是來自評論的 Marat 想法的實作：
import bisect
def close_pairs(list1,list2,c):
#assumes that list2 is sorted
for x in list1:
i = bisect.bisect_left(list2,x-c)
j = bisect.bisect_right(list2,x c)
yield from ((x,y) for y in list2[i:j])
list_1 = [1, 5, 10]
list_2 = [3, 4, 15]
print(list(close_pairs(list_1,list_2,2)))
#prints [(1, 3), (5, 3), (5, 4)]
為了證明該策略相對于可能被認為是“天真的”方法的潛在改進，讓我們timeit。
import timeit
setup_naive = '''
import numpy
list_a = numpy.random.randint(0, 10, 500)
list_b = numpy.random.randint(0, 10, 500)
c = 2
def close_pairs(list_a, list_b, c):
yield from ((x,y) for x in list_a for y in list_b if abs(x-y) <= c)
'''
setup_john_coleman = '''
import bisect
import numpy
list_a = numpy.random.randint(0, 10, 500)
list_b = numpy.random.randint(0, 10, 500)
c = 2
def close_pairs(list_a, list_b, c):
list_a = sorted(list_a)
list_b = sorted(list_b)
for x in list_a:
i = bisect.bisect_left(list_b,x-c)
j = bisect.bisect_right(list_b,x c)
yield from ((x,y) for y in list_b[i:j])
'''
print(f"john_coleman: {timeit.timeit('list(close_pairs(list_a, list_b, c))', setup=setup_john_coleman, number=100):.2f}")
print(f"naive: {timeit.timeit('list(close_pairs(list_a, list_b, c))', setup=setup_naive, number=100):.2f}")
在我的筆記本電腦上，結果如下：
john_coleman: 1.50
naive: 11.86
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/340377.html