使用純 Python 時(shí)，以下代碼運(yùn)行時(shí)間為 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])但是，通過(guò)簡(jiǎn)單地初始化rs為 numpy ndarray 而不是 python 列表列表，代碼在 145 秒內(nèi)運(yùn)行。我真的不知道為什么 numpy 使用此數(shù)組索引需要 3 倍的時(shí)間。我的想法是盡可能多地向量化，但只設(shè)法向量化beta/len(adjacency_list[node]). 此代碼在 77 秒內(nèi)運(yùn)行。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)問(wèn)題是這adjacency_list是一個(gè)具有不同列大小的列表列表，包含 100 000 行和 1-15 列。使用鄰接矩陣的更標(biāo)準(zhǔn)方法，至少作為普通的 ndarray，不是一種選擇，因?yàn)閷?duì)于 n=100 000，其 (n,n) 的形狀太大而無(wú)法分配給內(nèi)存。有什么方法可以使用其索引進(jìn)行矢量化以進(jìn)行 numpy 高級(jí)索引（可能將其變成 numpy ndarray）？我也非常感謝任何其他速度提示。提前致謝！編輯：感謝@stevemo，我設(shè)法創(chuàng)建adjacency_matrix了csr_matrix功能并將其用于迭代乘法。程序現(xiàn)在只需 2 秒即可運(yùn)行！for iteration in range(1, 101): rs[iteration] += rs[iteration - 1] * adjacency_matrix
1 回答
三國(guó)紛爭(zhēng)
TA貢獻(xiàn)1804條經(jīng)驗(yàn) 獲得超7個(gè)贊
如果我理解正確的話，這可以通過(guò)使用鄰接矩陣的矩陣冪的單線公式來(lái)完成。
根據(jù)您的原始代碼片段，您似乎有一些n節(jié)點(diǎn)網(wǎng)絡(luò)，鄰接信息存儲(chǔ)為中的列表列表adjacency，并且您有一個(gè)r與每個(gè)節(jié)點(diǎn)相關(guān)聯(lián)的值，這樣它在迭代時(shí)的值k+1是每個(gè)節(jié)點(diǎn)beta的總和的r倍數(shù)它的鄰居在 iter k。（你的循環(huán)在相反的方向構(gòu)造它，但同樣的事情。）
如果您不介意將您的adjacency列表列表改造成更標(biāo)準(zhǔn)的鄰接矩陣，例如A_ij = 1ifij是鄰居，否則為 0，那么您可以使用一個(gè)簡(jiǎn)單的矩陣乘積完成內(nèi)部?jī)蓚€(gè)循環(huán)，r[k+1] = beta * (A @ r[k])。
按照這個(gè)邏輯，r[k+2] = beta * (A @ (beta * (A @ r[k]))) = (beta * A)**2 @ r[k]或者一般來(lái)說(shuō)，
r[k] = (beta * A)**k @ r[0]
讓我們?cè)谝粋€(gè)小型網(wǎng)絡(luò)上試試這個(gè)：
# 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]
添加回答
舉報(bào)
0/150
提交
取消