如何以最有效的方式迭代和检查（使用函数）两个列表中的元素并创建新列表？

Question

这是代码：它正在查找点 x,y （在具有行 1,2,3,4,...n 和列 1,2,3,4,...4 的表上，表在其中创建行/列) 其中分数 x/y 可以减少，但它周围的所有点都不能减少，如果 GCD(x,y) == 1 则不能减少。

    from math import gcd
    def numcalc (x,y):
    n1 = gcd((x-1),(y-1))
    n2 = gcd((x),(y-1))
    n3 = gcd((x+1),(y-1))
    n4 = gcd((x-1),y)
    n5 = gcd((x),y)
    n6 = gcd((x+1),y)
    n7 = gcd((x-1),(y+1))
    n8 = gcd((x),(y+1))
    n9 = gcd((x+1),(y+1))
    return n1,n2,n3,n4,n5,n6,n7,n8,n9

    n,listj = 1000,[]
    num1 = [i for i in range(2,n+1)]

    for x in num1:
        for y in num1:
            listi = numcalc(x, y)
            if listi[0]==listi[1]==listi[2]==listi[3]==listi[5]==listi[6]==listi[7]==listi[8]==1 and listi[4]!=1 and x<y:
                listj.append([x,y])

'''

我只是想让它更快，这样我就可以找到大量的 x,y 点（>100000）。 我尝试创建一个嵌套列表，但这变成了：

listi = [[x,y] for x in num1 for y in num1 if numcalc(x,y)[0]==
         numcalc(x,y)[1]==numcalc(x,y)[2]==numcalc(x,y)[3]==
         numcalc(x,y)[5]==numcalc(x,y)[6]==numcalc(x,y)[7]==
         numcalc(x,y)[8]==1 and numcalc(x,y)[4]!=1 and x<y]

这实际上比以前慢，我需要多次调用函数 numcalc(x,y) ，我认为这会减慢代码速度。我想知道是否有办法在嵌套列表中创建列表，所以我尝试了以下方法：

listj = [[x,y] for x in num1 for y in num1 if listi = numcalc(x, y)
         and listi[0]==listi[1]==listi[2]==listi[3]==listi[5]==
         listi[6]==listi[7]==listi[8]==1 and listi[4]!=1 and x<y]

但是我收到语法错误:(

有谁知道如何使此代码更快，以便我可以迭代 100000 个整数的列表？

Answer 1

我想现在是介绍 numba.njit 的好时机。它可以帮助您以指数方式加速代码，特别是当您的代码大量使用列表、numpy 和数学时。

from math import gcd
from numba import njit

@njit(fastmath=True)
def numcalc (x,y):
    n1 = gcd((x-1),(y-1))
    n2 = gcd((x),(y-1))
    n3 = gcd((x+1),(y-1))
    n4 = gcd((x-1),y)
    n5 = gcd((x),y)
    n6 = gcd((x+1),y)
    n7 = gcd((x-1),(y+1))
    n8 = gcd((x),(y+1))
    n9 = gcd((x+1),(y+1))
    return n1,n2,n3,n4,n5,n6,n7,n8,n9


def append_list(n):
    listj = []
    num1 = [i for i in range(2,n+1)]

    for x in num1:
        for y in num1:
            listi = numcalc(x, y)
            if listi[0]==listi[1]==listi[2]==listi[3]==listi[5]==listi[6]==listi[7]==listi[8]==1 and listi[4]!=1 and x<y:
                listj.append([x,y])
    
    return listj

%timeit append_list(1000)
684 ms ± 22.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit append_list(10000)

此外，您还可以从 itertools 查看 product 和 count 来提高循环效率。

Answer 2

使用Python的内置map()函数。查看帮助(地图)

from math import gcd
from time import time


def numcalc(x, y):
    n1 = gcd((x - 1), (y - 1))
    n2 = gcd((x), (y - 1))
    n3 = gcd((x + 1), (y - 1))
    n4 = gcd((x - 1), y)
    n5 = gcd((x), y)
    n6 = gcd((x + 1), y)
    n7 = gcd((x - 1), (y + 1))
    n8 = gcd((x), (y + 1))
    n9 = gcd((x + 1), (y + 1))
    return n1, n2, n3, n4, n5, n6, n7, n8, n9


n, listj = 1000, []
num1 = [i for i in range(2, n + 1)]
start = time()
for x in num1:
    for y in num1:
        listi = numcalc(x, y)
        if listi[0] == listi[1] == listi[2] == listi[3] == listi[5] == listi[
            6] == listi[7] == listi[8] == 1 and listi[4] != 1 and x < y:
            listj.append([x, y])
elapsed_time_first_approach = time() - start
listj_version_1 = listj[:]

# 2nd approach using map()
start = time()
numberator_denominator = []
for x in num1:
    for y in num1:
        # Create list of tuples
        numberator_denominator.append((x, y))
# Next process the tuples using the map function.
listi = list(map(numcalc, numberator_denominator[0],numberator_denominator[1]))
if listi[0] == listi[1] == listi[2] == listi[3] == listi[5] == listi[
    6] == listi[7] == listi[8] == 1 and listi[4] != 1 and x < y:
    listj.append([x, y])
listj_version_2 = listj[:]
elapsed_time_second_approach = time() - start
print(f'{elapsed_time_first_approach=}')
print(f'{elapsed_time_second_approach=}')
# The next line verified an new listj has been generated by each method
print(f'{listj_version_1 is listj_version_2=}')
# The next line verifies the listj generated by each method have the same contentss
print(f'{listj_version_1 == listj_version_2=}')

验证

elapsed_time_first_approach=1.0969998836517334
elapsed_time_second_approach=0.10849332809448242
listj_version_1 is listj_version_2=False
listj_version_1 == listj_version_2=True