How to iterate and check (using a function) elements in two lists and create a new list in the most-CodePudding

This is the code: It's finding points x,y (on a table with rows 1,2,3,4,...n and coloumns 1,2,3,4,...4 where the table creates rows/colums) where the fraction x/y can be reduced, but all points surrounding it cannot, if GCD(x,y) == 1 it cannot be reduced.

    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])

'''

I am just trying to make it faster so I can find a large number of x,y points (>100000). I tried creating a nested list but this became:

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]

this was actually slower then before and I needed to call the funciton numcalc(x,y) multiple times which is what I think is slowing the code down. I'm wondering whether there's a way to create a list in the nested list so I tried this:

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]

but it came back with syntax error:(. Does anyone have any ideas on how to make this code faster so I can iterate through lists of 100000 intergers?

CodePudding user response：

I guess it's good time to introduce numba.njit. It helps you to speed up your code exponentially, especially if your code heavily uses list,numpy, and math.

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)

Also, you can check out product and count from itertools to make your looping more efficient.

CodePudding user response：

Use python's builtin map() function. See help(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=}')

Verification

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