2009-02-24 220 views
3

我目前有一個算法,可以在大小爲n的鄰接矩陣上運算。在我的算法中,我需要一次將整行或列整除。我的實現目前是O(m)或O(n),取決於它是列還是行。速度提升到鄰接矩陣

有什麼辦法零出在O(1)時間一列或行?

+0

爲什麼使用鄰接矩陣而不是鄰接表?如果圖形不完整,你可能會在adjacency_matrix中有很多無用的零(如果它是完整的,那麼你應該使用距離矩陣)。 – baol 2010-04-04 15:35:08

回答

3

本質上,這取決於您正在處理的芯片架構。對於大多數CPU而言,不可能在整個過程中將整個存儲器清零,因此無論編程語言提供什麼設施,每個單詞都需要單獨的存儲器操作。

它幫助很大,如果你的內存是連續的內存訪問時間,因爲毗鄰剛剛訪問內存的內存將被緩存,以及隨後的訪問將命中緩存,導致快速的性能。

這樣做的結果是,如果矩陣很大,一次一行或一列零列可能會更快,而反之亦然,這取決於您的數據是按列寫入還是按列寫入按行。

編輯:我認爲你的矩陣是不疏,或三角形,或其他特殊的,因爲你談論「歸零一整排」。如果你知道你的矩陣大部分是空的或者以某種方式適合一種特殊的模式,你可以用不同的方式表示你的矩陣(而不是一個簡單的nxm數組),故事會有所不同。但是如果你現在有一個nxm矩陣,那麼情況就是這樣。

+0

嗯,我從算法的角度來看更多,而不是依賴硬件的一個,所以我想這意味着沒有。 – samoz 2009-02-24 21:32:18

+0

我明白你的意思,但你的算法畢竟在硬件上運行。換句話說,如果有n件事要改變,從算法的角度來說,只有在改變這些n項是一個單一操作時才能做到這一點。 – 2009-02-24 21:37:09

0

是距離度量,並且是無向圖? (在這種情況下矩陣是對稱的)。在這種情況下,您可以在整個程序中對較低或較高的三角形矩陣進行操作。用這種方法,你只需要輸出一行(或者如果你正在處理上三角)。即使如此,它也不會是整排,平均一半。

0

這取決於你的矩陣是如何實現的。

如果你有一個表示諸如數組的數組,可以爲您檢查不隨後寫入它指向一個共享歸零元件陣列,只要。這意味着一行或一行中的一行可以在O(N)中歸零,而在所有其他寫操作上的成本不變。

你也可以有一對數組 - 一個用於行,一個列 - 這縮放值矩陣。將零置入其中將是O(1)操作來屏蔽掉一行或一列,但以每次讀取的額外處理爲代價;但是如果這是一個常見的用例,它可能是一種臨時從圖形中刪除節點的方式。它也會保持矩陣的原始版本不變,因此您可以對算法進行並行處理(假設它需要的唯一操作是修剪所有邊緣進入或離開節點)。