python - 查找列表中相差不超过 x 的所有数字对的最快方法

Question

我现在拥有的:

d = 0
res = 0
newlist = []
l = [4, 1, 6, 1, 1, 1]

for el in range(len(l)):
    for j in range(len(l)):
        if abs(l[el] - l[j]) <= d and el != j and el not in newlist and j not in newlist:
            newlist.append(el)
            newlist.append(j)
            res += 1

print(res)

它运行良好并返回正确的 2(1,1; 1,1) 但需要太多时间。我怎样才能让它工作得更快？谢谢。

例如如果 list = [1, 1, 1, 1] 和 d = 0 将有 2 对，因为每个数字只能使用一次。不允许使用 (a, b) 和 (b, c) 并且 (a, b) 和 (b, a) 是同一对...

Answer 1

对列表进行排序，然后遍历它。

一旦你对列表进行排序，你就可以贪心了:取最早的有效对，然后是下一个，然后是下一个......你最终会得到最大数量的有效对。

def get_pairs(lst, maxdiff):
    sl = sorted(lst) # may want to do lst.sort() if you don't mind changing lst
    count = 0
    i = 1
    N = len(sl)
    while i < N:
        # no need for abs -- we know the previous value is not bigger.
        if sl[i] - sl[i-1] <= maxdiff:
            count += 1
            i += 2 # these two values are now used
        else:
            i += 1
    return count

下面是一些对其进行基准测试的代码:

print('generating list...')
from random import randrange, seed
seed(0) # always same contents
l = []
for i in range(1000000):
    l.append(randrange(0,5000))

print('ok, measuring...')

from time import time

start = time();
print(get_pairs(l, 0))
print('took', time()-start, 'seconds')

结果(列表中有 100 万个值):

tmp$ ./test.py 
generating list...
ok, measuring...
498784
took 0.6729779243469238 seconds