如何在大整数列表中快速找到2个列表元素的第一个多个？

Question

我有一个大约10万个排序甚至整数的列表,范围是10 ^ 12到10 ^ 14.我的目标是找到x列表中的第一个整数,这也是列表x*2的成员.由于我的列表相当长,速度非常重要.

我的第一个想法是迭代列表并检查每个元素乘以2是否也在列表中,但是在实现这一点时很明显这对我的目的来说太慢了.

我的下一个想法是将列表中的每个元素分解为使用SymPy的主要分解factorint,然后搜索我的分解列表以进行相同的分解,除了额外的2.这显然没有更快,但我觉得必须有一种使用素数分解的方法,如果不是其他的话.

Answer 1

您可以使用两个迭代器迭代列表:一个指向当前元素,一个指向第一个大于或等于它的double.这将是O(N).

这是一个想法的草稿:

l = [1, 3, 5, 7, 10, 12, 15]

# ...
j = 0
for i in range(0, len(l)):
    while l[j] < 2*l[i]:
        j += 1
        if j == len(l):
            return -1
    if l[j] == 2*l[i]:
        return i

编辑:在另一个答案的评论之后,一些表演测试显示,通过消除乘法,调用len和减少列表中项目检索的数量,这个版本将更快(在我的测试中为3次):

j = 0
s = len(l)
for i in range(0, s):
    l_i = l[i]
    l_i2 = l_i<<1
    while l[j] < l_i2:
        j += 1
        if j == s:
            return -1
    if l[j] == l_i2:
        return i