ускорить вложенный цикл и функции вызова в python

Question

Я программирую код на Python, и моя проблема в том, что этот код занимает много времени, и я хочу знать, можно ли сделать его быстрее? У меня есть два списка кортежей, как показано ниже:

Similarities = [(1, 1, 1.0),(1, 2, -0.0016),(1, 3, 0.01764),(1, 4, -0.0033),(1, 5, -0.0016),...]

а также

Trust = [(2, 104, 1),(5, 1509, 1),(6, 1192, 1),(7, 1510, 1),(12, 234, 1),(15, 652, 1),...]

длина Similarities = 2274064 и длина Trust = 37997мои знаки в формате: (i,j,value)

Я хочу проверить кортежи, если i и j находятся в диапазоне цикла, функция возвращает их значения в цикл и после проверки, существуют ли эти значения или нет, будет вычислено d. И затем количество d будет добавлено к 2D-массиву.

Теперь я хочу запустить следующий код:

totalDistance=[]
totalSim=[]
for i in range(1642):
    totalDistance.append([])
    totalSim.append([])
    for j in range(1642):
        //search in Trust list to find value of trust i and j
        tr=calcTrustDif(i,j)
        //search in Similarities list to find value of similarity i and j
        pc=calcPccDif(i,j)
        if tr and pc:
            d=math.sqrt(pow(pc,2)+pow(tr,2))
        elif tr and not(pc):
            d=tr
        elif pc and not(tr):
            d=pc
        else:
            d=3
        totalSim[i].append(1-d)
        totalDistance[i].append(d)
def calcTrustDif(i,j):
    
    tr=[t for t in Trust if t[0]== i and t[1]==j]
    if tr:
        return tr[0][2]
    else:
        pass
def calcPccDif(i,j):
    
    pc=[t for t in Similarities if t[0]== i and t[1]==j]
    if pc:
        return 1-pc[0][2]
    else:
        pass

Я оценил и обнаружил, что этот код займет 82 часа, и это очень плохо... Кто-нибудь может помочь мне сократить время выполнения? Я думаю, что у python есть волшебные возможности для этой ситуации, которых я не знаю.

Answer 1

Вы должны прочитать о временной сложности и нотации Big O.

Причина того, что ваш код работает так медленно, заключается в том, что вы используете тройной вложенный for циклы, которые приводят к очень плохой временной сложности ~, в частности O(n*n*(allT+allP)), где n = 1642 в твоем случае.

Я бы рекомендовал попробовать придумать алгоритм, в котором вам не нужно повторять allP а также allT 1642*1642раз. Простой выбор лучшего алгоритма может значительно улучшить время выполнения без необходимости прибегать к какой-либо "магии Python".

Примечание: вы могли бы облегчить другим понимание того, чего вы пытаетесь достичь с помощью своего кода, если бы вы использовали более значимые имена для своих переменных. Например, значениеcalcPccDif(), allP, allTможет быть очевидным для вас, но это ничего не значит для других и, таким образом, затрудняет чтение вашего кода другими людьми. (С другой стороны,totalDistance ясно и содержательно.)