如何在常量時間從稀疏表中刪除行/列？

Question

我有一個非常稀疏填充表與巨大的尺寸。

即，我的表的索引可能非常大，但表中元素的數量非常少。

我一直在想這個數據結構。

我排除了rows x cols表，因爲它佔用太多的內存和太多時間來查找行/列中的所有元素。

相反，我想使用兩個地圖：rows和cols。我們來看看rows。鍵是行索引，鍵k的值是行k中所有元素的列號列表。

示例（1表示的元素存在那裏）：

0 1 0 
1 0 1 

將是這樣rows地圖：

0: [1] 
1: [0, 2] 

我會保持類似cols地圖，鍵是列號和所述值對於密鑰k是列k中所有元素的行號列表。

當我想在我的表刪除行k，我會做： del rows[k]

但這不會從cols地圖中刪除頂點。 我將不得不遍歷所有列的某些元素被刪除，並刪除cols地圖中的每個元素。

是否有O(1)這樣做的方法？

Answer 1

那麼，我一直在思考和思考，我認爲這是可能的。

然而，解決方案並不理想，因爲它可能在開始時是O（1），但O（n）依賴關係仍然存在，但對於某些類型的數據和用法，它應該接近常量時間。所以這取決於它是否對你有用（與陣列長度和/或操作次數相比，更改次數顯着減少）。

對於每次刪除，您應該添加到更改的「更改列表」中。例如，您刪除了第no行。 10，所以你加入你的清單：「10號以上，減1」。

當計算正確的行數時，必須通過「更改列表」進行減法/添加。

此外，您還需要一個更多的數組，其中包含使用的最後一個減去的/添加的數字以及「更改列表」的數量，因此您不必計算已經爲該行計數的更改。

在最壞的情況下，它仍然是「a * n」，其中a是某個常數。

---

實施例：

rows, cols = 1000; 
delete(row,573); 
//=> list_of_changes[0] = {573, 'deleted'} 
access_row(581) 
//=> help_array[581] = {-1, 1} 
//=> help_array.structure = {"how much add/subtract on this line", "number of changes used"} 
access_row(581) 
//=> look at the help_array[581] seeing having used 1 change, 
// the size of list_of_change is 1, so you don't have to count 
// anything, using the -1 value. - constant time 

---

當然，如果我刪除行[0]，然後我訪問所有的0..998值，這將是O（n）的原因它必須計算n次help_array。

Answer 2

由於您的主要用途cols圖的是儘可能快地數列，而不是從它那裏得到的數據，我想創建一個table嵌套的地圖，以及地圖colCount，而不是rows和cols。

該解決方案比O（1）更接近O（n），但您不會浪費週期出現在row x cols結構中。

所以，你的榜樣，table應該是這樣的：

{0: {1:"Value"}, 
{1: {0:"Value", 2:"Value"}} 

而且colCount應該是這樣的：

#Each column in the example only had one value 

{0:1, 
1:1, 
2:1} 

然後，當你刪除的行k，你只要遞減計數器對於在該行中找到的每個列。下面是一些僞代碼：臨近，這將是實現矩陣作爲ķ d樹的

for key in table[k].keys() 
    colCount[key] = colCount[key] - 1 
delete table[k] 

Answer 3

一個非常非正統的方式，與ķ = 2。您可以通過訪問與該行或列相交的所有單元格來刪除行或列;如果矩陣是正方形的，並且它有非零條目，我相信您需要檢查的單元格的平均數量爲sqrt(n)。 （我已經在Stackoverflow上的一些答案中寫了一個這樣的效果證明 - 如果需要它，我可以查看它。）

以非常類似的方式，您可以使用四叉樹;我理解這些術語的方式不同之處在於，單元邊界是預定義的，以便在四叉樹中始終將x和y範圍縮小爲一半（對於每個非葉中的四個相同的子單元），而節點確定d樹中的邊界（對於每個非葉中的兩個不相同的子單元）。

我認爲對於這兩個版本來說，這個解決方案的性能取決於複雜方式的稀疏性。首先，如果數據真的非常稀疏，比如，每行/列的非零數據的平均數遠遠小於1，那麼這個解決方案將比您提議的解決方案更具有內存效率，但可能更少時間效率。如果非零條目的數量是條目總數的一個常數部分c，並且您的矩陣是m * k，則此解決方案可能更高效：對於您的解決方案，要刪除一列，您需要平均更改c*m行名單。對於每一個這樣的行列表，你需要找到你的列的位置，並移動它後面的所有條目，一個向前。平均每行有c*k/2 = O(k)個條目，總共有c^2*m*k/2 = O(m*k)個操作。我們將有n = c*m*k，所以平均總操作數將是c*n/2 = O(n)，而對於此處提出的解決方案，它將是O(sqrt(n))。同樣，如果假設矩陣大致爲正方形，比如m*m，並且每行/列平均具有f(m)非零項（因此n = f(m)*m），那麼對於您的解決方案，操作數爲O(f(m)^2)，對於此項，操作數爲O(sqrt(m*f(m)));這意味着，如果f(m) = ω(m^(1/3))這個解決方案更好。 （注意，這是一個lower case omega;它基本上意味着，f(m)漸近快於m^(1/3)增長，例如像sqrt(m)或c*m。）

（我是假定rows地圖的每個條目是在解決方案中的陣列;一個聯列表會給出相同的複雜度，因爲它需要線性時間來查找列表中的右列。通過讓每個行和列代表一行，而不是通過一個數組，而是通過一個自平衡樹，您可以做得更好 - 然後您可以通過O(log(k))的每行操作和O(m * log(k)) = O(sqrt(n)*log(n))操作完成，假設矩陣距離方形不太遠，但仍然不如此樹業務更好，但如果您確實需要最佳性能，則可能需要執行看看它是如何工作的實踐。）

如果你的矩陣的密度確實是一個常數c，那麼密集的矩陣表示還要做O(sqrt(n))操作，因此漸近行爲應該是一樣的。恆定的因素取決於c，所以再一次，你需要實現兩者，以確定哪個更快。

爲了使四叉樹解決方案具有良好的性能，您還需要非零值不集中在一個小區域;分佈並不需要特別均勻，只是不是非常集中。

如果您也期望頻繁地添加和刪除任意條目，那麼d-tree非常難以做好 - 我認爲沒有簡單的方案可以使樹自身平衡，如紅色 - 黑色或AVL或類似的一維樹。四叉樹仍然可以工作。

Answer 4

讓我們看看，如果我理解你擁有的一切：

• 爲您維護被佔用的列清單的每一行。
• 對於每個列，您維護一個佔用的行的列表。
• 這些結構本身都足以描述矩陣。

當一行被刪除時，您只需將其關聯的列列表設置爲空。但在做 之前，爲什麼不使用這個列表來處理列表中每列的行列表呢？

一個簡單的例子。假設你有以下矩陣：

1 0 0 0 1 1 
    0 1 0 0 0 0 
    0 1 1 0 0 0 
    0 0 0 0 0 1 

每一行的列清單將是：

0 [0, 4, 5] 
    1 [1] 
    2 [1, 2] 
    3 [5] 

每列的列名單將是：

0 [1] 
    1 [1, 2] 
    2 [2] 
    3 [] 
    4 [0] 
    5 [0, 3] 

如果行2被刪除，那麼你將處理與該行相關聯的列列表，在這種情況下：2 [1, 2]。這些是 列，其中行列表將包含'2'。沒有其他的 行列表需要查看。

Delete row 2: 
    -Column list for row 2: [1, 2] 
    -Remove row '2' from the row list for columns 1 and 2 
    -Set column list for row 2 to [] 
    done. 

已更新的列列表是：

0 [0, 4, 5] 
    1 [1] 
    2 [] <== updated 
    3 [5] 

更新行列表是：

0 [1] 
    1 [1] <== updated 
    2 [] <== updated 
    3 [] 
    4 [0] 
    5 [0, 3] 

這兩種結構的描述下面的矩陣：

1 0 0 0 1 1 
    0 1 0 0 0 0 
    0 0 0 0 0 0 
    0 0 0 0 0 1 

這不是O（1）算法ithm你正在尋找，但它應該是非常有效的一個非常sparce矩陣。

Answer 5

總是有唐納德克努特的dancing links technique。沿着每一行和每列使用雙向鏈表。刪除行或列需要時間與行或列中元素的數量成線性關係。