Python: медленный алгоритм с сообществами

Question

У меня есть две разные структуры сообщества, но узлы одинаковы. Обе структуры сообщества хранятся в словаре (ключ: имя сообщества (строка); значение: узлы в этом сообществе (список int)), например:

community_map_friendship:

C0:[0, 20, 48, 55, 60, 68, 79, 81, 85, ...,  78190]  
C1:[1, 6, 10, 13, 18, 19, 22, 24, 26, ..., 78180]  
C2:[7, 21, 25, 29, 36, 37, 42, 49, 70, ..., 78146]  
C3:[40, 86, 103, 123, 129, 143, 154, 167, ..., 78172]  
C4:[66, 83, 133, 169, 174, 175, 205, 237, ..., 78166]  
C5:[179, 182, 188, 219, 228, 248, 265, 286, ..., 77981]

community_map_uservotes :

C0:[0, 20, 41, 48, 55, 60, 68, 79, 81, 85, ..., 78190]  
C1:[1, 6, 10, 13, 18, 19, 24, 26, 28, 30, 31, ..., 78173]  
C2:[22, 39, 43, 47, 53, 61, 69, 73, 97, 102, ..., 78180]  
C3:[7, 21, 25, 29, 36, 37, 42, 49, 70, 80, 83, ..., 78166]  
C4:[183, 483, 608, 1453, 2205, 2957, 3090, 3378, ..., 78149]

Моя цель - подсчитать случаи, когда два разных узла включены в списки сообщества в обеих структурах. (например: (0,20), (0,48), (20,48), ..., (1,6), (1,10), (6,10), ..., (7, 21), ...). Важно, что не обязательно быть одним и тем же сообществом. Например, узлы 7 и 21 находятся в сообществе C2 в первой структуре, но в сообществе C3 во второй структуре, но эту пару следует включить таким же образом.

Что я уже пробовал:

# Return true, if the two nodes are in the same community, otherwise return false

def Is_In_Same_Community(node1, node2, community_map):
    for community in community_map.values():
        if((node1 in community) and (node2 in community)):
            return True
        elif(((node1 in community) and (node2 not in community)) or ((node1 not in community) and (node2 in community))):
            return False
    return False

#The algorithm, which counts the appropriate value:

TP=0
for community in communities_map_friendship.values():
    res = [Is_In_Same_Community(x,y,communities_map_uservotes) 
          for i,x in enumerate(community) for j,y in enumerate(community) if i != j]
    TP = TP + res.count(True)

Алгоритм хорош, но проблема в том, что у меня около 30 000 узлов, поэтому он будет работать в течение нескольких дней, пока я не получу правильное значение.

У кого-нибудь есть идея ускорить этот алгоритм как-то?

Answer 1

Это не должно занять несколько дней для 30000 узлов, и хотя l oop еще можно оптимизировать:

def count_pairs( cm1, cm2 ):
    count = 0  
    for k,l1 in cm1.items():
        if k not in cm2:
            continue
        l2 = cm2[k]
        i1 = i2 = 0
        common = []
        while i1 < len(l1) and i2 < len(l2):
            v1 = l1[i1]
            v2 = l2[i2]
            if v1 < v2:
                i1 += 1
            elif v1 > v2:
                i2 += 1
            else:
                common.append(v1)
                i1 += 1
                i2 += 1
        count += len(common)*(len(common)+1)/2
    return count

Принимая во внимание последнюю версию вопроса:

def count_pairs( cm1, cm2 ):
    count = 0  
    for k,l1 in cm1.items():
        for k2,l2 in cm2.items():
            i1 = i2 = 0
            common = []
            while i1 < len(l1) and i2 < len(l2):
                v1 = l1[i1]
                v2 = l2[i2]
                if v1 < v2:
                    i1 += 1
                elif v1 > v2:
                    i2 += 1
                else:
                    common.append(v1)
                    i1 += 1
                    i2 += 1
            count += len(common)*(len(common)+1)/2
    return count

Answer 2

Есть другой способ приблизиться к этому. Рассмотрим два списка:

l1 = [0, 20, 48, 55]
l2 = [0, 20, 41, 48, 60]

Общие пары между этими списками являются просто перестановками (или комбинациями, если вы не хотите, чтобы (0, 20) и (20, 0) отличались) от общего члены. Например, пересечение этих списков:

set(l1) & set(l2)
# {0, 20, 48}

Итак, общие пары: (0, 20), (20, 0), (0, 48), (48, 0), (20, 48), (48, 20)

Если вас интересует только количество, вам даже не нужно беспокоиться о вычисление этих пар, потому что мы знаем, что количество пар определяется по формуле:

(n!)/(n -2)!

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

from itertools import product
import math

mf = {
  "C0":[0, 20, 48, 55],
  "C1":[1, 6, 10, 13],
  "C2":[7, 21, 25, 55],  
}
mu = {
   "C0":[0, 20, 41, 48, 60],
   "C1":[1, 6, 10, 13, 18],
   "C3":[7, 21, 25, 29],
}

TP = 0
for p1, p2 in product(mf.values(), mu.values()):
    num_common = len(set(p1) & set(p2))
    if num_common >= 2:
        TP += math.factorial(num_common)//math.factorial((num_common - 2))

print(TP) # 24

Это тот же ответ, который вы получите с вашим кодом.