Как эффективно преобразовать матрицу смежности в словарь?

Question

Мне интересно, как эффективно преобразовать матрицу смежности в словарь, представляющий соединения между одним узлом?

Пример матрицы:

matrix = [
[0,1,0,0,0,0],
[0,0,0,0,0,0],
[0,1,0,1,0,0],
[0,0,0,0,0,0],
[0,0,0,1,0,1],
[1,0,0,0,0,0]
]

Пример вывода:

{0: [1], 1: [], 2: [1, 3], 3: [], 4: [3, 5], 5: [0]}

Мой код ниже на самом деле генерирует правильный вывод;однако я считаю, что это очень неэффективно, потому что я использую два для циклов.Есть ли способ оптимизировать мой код без использования каких-либо библиотек?Пожалуйста, дайте мне знать, и спасибо!

def convertAdjMatrixtoDict(m):

    graph = {}
    for idx, row in enumerate(m):
        res = []
        for r in range(len(row)):
            if row[r] != 0:
                res.append(r)
            graph[idx] = res
    return graph

Answer 1

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

import numpy as np
{i: np.nonzero(row)[0].tolist() for i,row in enumerate(matrix)}

Время для случайной матрицы 1000x1000:

1. оригинальный код: 310мс
2. @ Код Дэнксилоэ: 91ms
3. Этот код: 20 мс

Answer 2

Вот более Pythonic решение, которое может быть немного быстрее.

{i: [j for j, adjacent in enumerate(row) if adjacent] for i, row in enumerate(matrix)}

Я сомневаюсь, что вы получите намного быстрее в сыром Python.Я подумаю, есть ли какие-нибудь решения, использующие быстрые библиотеки, такие как numpy.

Обновление: я рассчитал время для двух решений, используя следующее.

import numpy as np

# Make a big example
num_nodes = 1000
matrix = np.random.randint(0, 2, [num_nodes, num_nodes])

# Convert to raw Python
matrix = [[element for element in row] for row in matrix]

Ваше решение заняло 0,62секунды мои заняли 0,12 секунды.Так что на самом деле есть хорошее ускорение примерно в 5 раз.