intrusive/non-intrusive data collection

以 LinkedList 和 Heap 為例討論

前言

討論 data collection 的設計時,會希望寫得夠一般化,方便泛用,所以直覺會用 non-intrusive data collection (被儲存的資料不知道任何 data collection 的資訊)。像 Java 的 Collections Framework,或是 C++ STL 的 list、map 等 class 屬於這類。在 non-intrusive 的前提下,某些情境會不太方便。下面討論兩個例子。

List 的 Delete

假設有 class Item, class Node, class LinkedList。Item 是我們使用的資料;Node 是 LinkedList 內儲存 Item 用的容器。

LinkedList 的 Delete(Item) 的時間複雜度是 O(n),因為得走訪整個 LinkedList 找到 Item (這篇的 erase_person() 有附程式碼說明 )。如果我們希望降低 Delete(Item) 的時間複雜度,該怎麼辦呢?

  • 傳遞 Node 而不是 Item,需要刪除時用 Delete(Node)。效率是 O(1)。
  • 還是傳遞 Item,在 LinkedList 內部引入 HashMap 存 Item → Node,可以用 O(1) 的時間找到 Node。

第一個作法表示用到 Item 的函式都知道 Item 是存在 LinkedList 裡,有些奇怪。有些情況可能比較方便傳 Item。不見得說不行,要依實際使用的情況討論。我個人偏好不這麼作。

第二個作法多了兩個負擔:

  • 要支援 Hash(Item)。
  • 多使用 HashMap 的空間。

這時回頭來看,如果 Item 和 Node 合在一起 (intrusive linked-list),Delete(Item) 天生就是 O(1),不存在 Delete(Item) 是 O(n) 的問題。

更新 Heap 結構

假設有 class Item, class Node, class Heap。一樣 Node 是 Heap 內部存 Item 的容器。

假設 Update(Item) 表示調整 Item 在 Heap 的位置 (Item 已經在 Heap 裡)。Update(Item) 的時間複雜度也是 O(n),因為得走訪整個 Heap 找到 Item。

和 LinkedList 的情況一樣,可以直接傳 Node 或在 Heap 內部引入 HashMap 存 Item → Node。然後會有對應的 trade-off。另一方面,改用 intrusive Heap 的話,Item 的值改變後,直接調整它在 Heap 的位置即可 (效率 O(lg(n) )。

結論

對於資料 Item 來說,使用 intrusive data collection 存 Item 的話,Item 可以直接找到它在 data collection 內的位置,接著可以直接操作 data collection (e.g., 從 list 中刪除、調整在 heap 內的位置)。

反觀 non-intrusive data collection 需要多一個步驟找到 Item 在 data collection 內的 container,才能對 container 操作。這個額外操作有它的成本 (設計、維護、時間、空間之間的取捨)。

如果你的目標很明確,遇到 non-intrusive data collection 用起來很卡的時候,不妨想想是否應該改用 intrusive data collection。

備忘

後記

以往學 OOP,會強調 favor composition over inheritance,所以就認定資料容器要寫得夠一般化,方便配合各種不同資料使用。剛學 OOP 時是用 Java,Java 的 Collection Framework 又寫得特別漂亮,於是我有了錯誤的刻版印象:data collection = non-intrusive data collection。

之前使用 shared pointer 都是在物件裡存 reference count (intrusive reference counting)。後來 Acer 來我們公司,和 Acer 聊到這點,才發現 C++ 標準函式庫是記在 shared pointer 上 (non-intrusive reference counting)。

後來和ScottCmd 聊到兩者的好壞 (之後再另寫文章記錄),邱提到 ZeroMQ 的作者談到 intrusive linked list 時有類似的討論。看了以後覺得很有意思。《Avoiding game crashes related to linked lists》有關於 intrusive linked list 的深入討論,值得一看。看完才發現我一直忽略這麼重要的東西。

後記 2

許多人看不懂第一版在說什麼,聽邱、Scott 說明後發覺我第一版先提結論,然後假設讀者可從結論推出問題。於是在主題不明的情況下有了一連串的誤解。後來就改寫成現在這個樣子。

之後還是得乖乖地照「問題、解法、結論」的脈絡寫吧。但要怎麼在這之中插入閒聊,就很吃寫作功力了。