使用純 Python 時，以下代碼運行時間為 45 秒。for iteration in range(maxiter): for node in range(n): for dest in adjacency_list[node]: rs[iteration + 1][dest] += beta * rs[iteration][node] / len(adjacency_list[node])但是，通過簡單地初始化rs為 numpy ndarray 而不是 python 列表列表，代碼在 145 秒內運行。我真的不知道為什么 numpy 使用此數組索引需要 3 倍的時間。我的想法是盡可能多地向量化，但只設法向量化beta/len(adjacency_list[node]). 此代碼在 77 秒內運行。beta_over_out_degree = np.array([beta / len(al) for al in adjacency_list])for iteration in range(1, maxiter + 1): r_next = np.full(shape=n, fill_value=(1 - beta) / n) f = beta_over_out_degree * r for i in range(n): r_next[adjacency_list[i]] += f[i] r = np.copy(r_next) rs[iteration] = np.copy(r)問題是這adjacency_list是一個具有不同列大小的列表列表，包含 100 000 行和 1-15 列。使用鄰接矩陣的更標準方法，至少作為普通的 ndarray，不是一種選擇，因為對于 n=100 000，其 (n,n) 的形狀太大而無法分配給內存。有什么方法可以使用其索引進行矢量化以進行 numpy 高級索引（可能將其變成 numpy ndarray）？我也非常感謝任何其他速度提示。提前致謝！編輯：感謝@stevemo，我設法創建adjacency_matrix了csr_matrix功能并將其用于迭代乘法。程序現在只需 2 秒即可運行！for iteration in range(1, 101): rs[iteration] += rs[iteration - 1] * adjacency_matrix
1 回答
三國紛爭
TA貢獻1804條經驗 獲得超7個贊
如果我理解正確的話，這可以通過使用鄰接矩陣的矩陣冪的單線公式來完成。
根據您的原始代碼片段，您似乎有一些n節點網絡，鄰接信息存儲為中的列表列表adjacency，并且您有一個r與每個節點相關聯的值，這樣它在迭代時的值k+1是每個節點beta的總和的r倍數它的鄰居在 iter k。（你的循環在相反的方向構造它，但同樣的事情。）
如果您不介意將您的adjacency列表列表改造成更標準的鄰接矩陣，例如A_ij = 1ifij是鄰居，否則為 0，那么您可以使用一個簡單的矩陣乘積完成內部兩個循環，r[k+1] = beta * (A @ r[k])。
按照這個邏輯，r[k+2] = beta * (A @ (beta * (A @ r[k]))) = (beta * A)**2 @ r[k]或者一般來說，
r[k] = (beta * A)**k @ r[0]
讓我們在一個小型網絡上試試這個：
# adjacency matrix
A = np.array([
[0, 1, 1, 0, 0],
[1, 0, 1, 0, 0],
[1, 1, 0, 1, 0],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 0]
])
# initial values
n = 5
beta = 0.5
r0 = np.ones(n)
maxiter = 10
# after one iteration
print(beta * (A @ r0))
# [1. 1. 1.5 1. 0.5]
# after 10 iterations
print(np.linalg.matrix_power((beta * A), maxiter) @ r0)
# [2.88574219 2.88574219 3.4921875 1.99414062 0.89257812]
添加回答
舉報
0/150
提交
取消