Я работаю с относительно большими наборами данных (100000+ элементов), и мне нужно создать для них матрицу смежности.
Я написал очень базовый c для l oop, который выполняет это для заданного количества подключенных узлов (nx2)
nodes = np.random.randint(20000, size=(20000, 2))
def adjMat(node_list):
n = np.max(node_list)
A = np.zeros((n, n))
for tail, head in node_list:
A[tail-1, head-1] = 1
return A
Это работает нормально и не так медленно, как я думал, но предполагал, что я мог бы значительно улучшить производительность, используя numba для этой супер простой функции.
Итак, я добавил две функции с джиттингом (одна использует параллельную), чтобы увидеть разницу в производительности. Я также только что добавил networkx, чтобы убедиться, что он хорошо оптимизирован.
@njit()
def adjMat_numba(node_list):
n = np.max(node_list)
A = np.zeros((n, n))
for tail, head in node_list:
A[tail-1, head-1] = 1
return A
@njit(parallel = True)
def adjMat_numba_para(node_list):
n = np.max(node_list)
A = np.zeros((n, n))
for tail, head in node_list:
A[tail-1, head-1] = 1
return A
def getAdjacenyList(node_list):
G = nx.Graph([e for e in node_list])
A = nx.convert.to_dict_of_lists(G)
return A
Вот результат моего теста на 20000 пар подключенных узлов:
%timeit a = adjMat(nodes)
112 ms ± 3.7 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit b = adjMat_numba(nodes)
1.34 s ± 41.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit c = adjMat_numba_para(nodes)
251 ms ± 3.9 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
%timeit d = getAdjacenyList(nodes)
149 ms ± 3.31 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
Я невероятно удивлен что использование numba на самом деле делает функцию в несколько раз медленнее и что даже в параллельном режиме она все равно не такая быстрая, как для l oop. Numba также использует значительно больше памяти, чем l oop. Кроме того, я очень удивлен, что networkx работает медленнее, чем для l oop - я ожидал, что библиотека, единственной целью которой было решение такого рода проблем, будет быстрее.
Я что-то не так с декоратором numba? Есть ли какие-нибудь лучшие варианты для быстрого и эффективного создания матрицы смежности?
Я запускаю эти тесты на 12-ядерном linux рабочем столе, используя pycharm.