• 發行項

本文章是由機器翻譯。

程式設計師雜談

.NET 收集，第 2 篇：使用 C5

Ted Neward

 

 

Ted Neward
歡迎回來。

在本系列第一部分，我簡要介紹了「C# 哥本哈根全面集合類」(C5) 庫。這一組類旨在補充（如果不取代的話）Microsoft .NET Framework 運行時庫附帶的 System.Collections 類。這兩個庫之間的重疊部分相當多，其中部分原因是 C5 想要遵從 .NET Framework 類庫 (FCL) 使用的許多相同特性，部分原因僅僅是合理地表示某一特定集合類型的方式有多種。（不支援索引屬性語言語法的索引集合 － 例如字典或清單 － 是很難想像的：C# 中的「[]」運算子和Visual Basic中的「()」運算子。）儘管 FCL 集合非常實用，但是 C5 集合在一兩個方面還是更勝一籌，而這正是我們想要花時間探討的。

（請注意，這兩種庫之間也非常可能存在一定的性能差別，對此其各自的支援者和批評者很快就能指出 － 例如 C5 集合手冊討論了部分性能問題。儘管如此，我還是避開了大多數性能基準。理由是一般而言，某個基準所能證明的只是對於一個或一組特定用例而言。有的人認為其中一個比另一個運行快，但實際上這並非就是說它們兩個之間的所有用例都是這樣。這並不意味著所有基準都是無用的，只是具體使用環境對於基準很重要。強烈建議讀者使用自己的特定方案，將其變成基準，並對兩者進行比較，以觀察這些特定用例中是否存在顯著差異。）

實現

首先，讓我們快速看一下 C5 提供的不同的集合實現。同樣，正如我們上次所討論的，使用 C5 的開發者一般不應擔心所用的實現，除非要確定需要創建哪一種實現，其餘的問題則是集合應由介面類別型引用。（關於介面類別型的描述，請參見本系列的上期專欄文章msdn.microsoft.com/magazine/jj883961或者 C5 文檔 bit.ly/UcOcZH。）以下是實現：

  • CircularQueue<T> 同時實現 IQueue<T> 和 IStack<T>，以提供 IQueue<T> 的先進先出語義（通過 Enqueue 和 Dequeue）或 IStack<T> 的後進先出語義（通過 Push 和 Pop），是使用連結清單保存的。It grows in capacity as needed.
  • ArrayList<T> 實現 IList<T>、IStack<T> 和 IQueue<T>，是使用陣列保存的。
  • LinkedList 通過一個雙連結節點清單<T>實現 IList<T>、IStack<T> 和 IQueue<T>。
  • HashedArrayList<T> 實現 IList<T>，是使用陣列保存的，但是內部也維護著一個雜湊表，用來高效地查找清單中某個項的位置。它也不允許清單中有重複項（因為重複項會影響雜湊表查找）。
  • HashedLinkedList<T> 實現 IList<T>，是使用連結清單保存的。和使用陣列保存的同類一樣，它利用一個內部雜湊表優化查找。
  • WrappedArray<T> 實現 IList<T>，回繞保存在一維陣列中。該類的優勢是它只是「修飾」陣列，使獲得 C5 功能的速度變得快很多，而不是從陣列中複製元素並粘貼到 ArrayList<T> 中。
  • SortedArray<T> 實現 IIndexedSorted<T>，這意味著可以對集合進行索引和排序（稍後我們將進行探討）。它使自己的項保持排序，不允許存在重複項。
  • TreeSet<T> 實現 IIndexedSorted<T> 和 IPersistedSorted<T>，保存在平衡紅黑樹中，這對於插入、移除和排序非常有用。像所有集一樣，它也不允許存在重複項。
  • TreeBag<T> 實現 IIndexedSorted<T> 和 IPersistedSorted<T>，保存在平衡紅黑樹中，但基本上是一個「包」（有時稱為「多重集」），意味著它允許存在重複項。
  • HashSet<T> 實現 IExtensible<T>，集（意味著沒有重複項）保存線上性連結雜湊表中。這意味著可以快速查找，修改更少。
  • HashBag<T> 實現 IExtensible<T>，包（意味著允許重複項）保存線上性連結雜湊表中，同樣可以快速查找。
  • IntervalHeap<T> 使用一個成對資料的陣列存儲的間隔堆實現 IPriorityQueue<T>，從而提高了從優先級佇列的「最大」或「最小」端進行提取的效率。

此外，還有一些實現，如果感興趣，可以參閱 C5 手冊和文檔瞭解詳細資訊。但是，除了性能問題外，關鍵在於知道哪些實現可以實現哪些介面，這樣在選擇要具現化的實現時，才會胸有成竹。（您隨時可以在以後改用另一種實現，條件是遵守 C5 設計原則，即始終通過介面而不是其實現類型引用集合。）

Functionality

如果 C5 只是包含集合實現的更大集合，這固然很有趣，但是未必引起多大的興趣或討論。幸運的是，它為開發者提供的幾項新功能很值得討論。

視圖 C5 庫的有趣小特性之一，是「視圖」的概念：源集合中元素的子集合，實際上它們不是副本，而是保存在原集合中。這實際是上一期專欄中的代碼在探勘測試中所做的。關於如何創建集合的視圖，請參見圖 1。

圖 1 創建集合的視圖

 

[TestMethod]
public void GettingStarted()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  // Print item 1 ("Roosevelt") in the list
  Assert.AreEqual("Roosevelt", names[1]);
  Console.WriteLine(names[1]);
  // Create a list view comprising post-WW2 presidents
  IList<String> postWWII = names.View(2, 3);
  // Print item 2 ("Kennedy") in the view
  Assert.AreEqual("Kennedy", postWWII[2]);
}

該視圖是使用原始清單保存的，這意味著如果原始清單由於任何原因發生變化，它的視圖也會受影響。 關於視圖的潛在不穩定性，請參見圖 2。

圖 2 視圖具有潛在不穩定性

[TestMethod]
public void ViewExploration()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Washington", "Adams", "Jefferson",
      "Hoover", "Roosevelt", "Truman",
      "Eisenhower", "Kennedy" });
  IList<String> postWWII = names.View(4, names.Count - 4);
  Assert.AreEqual(postWWII.Count, 4);
  IList<String> preWWII = names.View(0, 5);
  Assert.AreEqual(preWWII.Count, 5);
  Assert.AreEqual("Washington", preWWII[0]);
  names.Insert(3, "Jackson");
  Assert.AreEqual("Jackson", names[3]);
  Assert.AreEqual("Jackson", preWWII[3]);
}

正如本測試所示，改變基礎清單（「names」）意味著在它之上定義的視圖（本示例中為「preWWII」視圖）的內容也會變化。因此，現在視圖中的第一個元素是「Washington」而不是「Hoover」。

但是，C5 將盡可能保留視圖的穩定性；例如，如果插入發生在集合前面（也就是 C5 可以在不改變「preWWII」視圖內容的情況下插入它），那麼視圖的內容保持不變。

[TestMethod]
public void ViewUnchangingExploration()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  IList<String> preWWII = names.View(0, 2);
  Assert.AreEqual(preWWII.Count, 2);
  names.InsertFirst("Jackson");
  Assert.AreEqual("Jackson", names[0]);
  Assert.AreEqual("Hoover", preWWII[0]);
}

不可變（受保護）集合隨著功能概念和程式設計風格的興起，不可變數據和不可變物件得到很大重視。在很大程度上，這是因為不可變物件具備諸多優勢，即併發和並行程式設計，而且許多開發者發現不可變物件更容易理解和推理。 這個概念的必然結果是遵循不可變集合的概念 － 該觀點認為，無論集合中的物件是否不可變，集合本身都是固定、無法更改（添加或移除）集合中的元素。 (Note:您可以在 MSDN 基類庫 (BCL) 博客 bit.ly/12AXD78 中查看 NuGet 上發佈的不可變集合預覽。）

在 C5 中，不可變集合是通過對包含相關資料的集合外的「包裝」集合進行具現化處理的；這些集合是「受保護」的集合，以經典的修飾器模式風格進行使用。

public void ViewImmutableExploration()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  names = new GuardedList<String>(names);
  IList<String> preWWII = names.View(0, 2);
  Assert.AreEqual("Hoover", preWWII[0]);
  names.InsertFirst("Washington");
  Assert.AreEqual("Washington", names[0]);
}

如果有人嘗試編寫用來在清單中添加或移除元素的代碼，C5 很快會讓開發者放棄這種想法：只要一調用任何「修改」方法（Add、Insert、InsertFirst 等等），會立即引發異常。

再者，這提供了一個非常難得的機會。 在上期專欄中我曾經提到，C5 的主要設計思想之一是集合只應通過介面使用。 如果使用 C5 的開發者支援這一設計理念，現在很容易確保集合不會被傳遞到的方法修改。（图 3）。

圖 3 受保護（不可變）集合

public void IWannaBePresidentToo(IList<String> presidents)
{
  presidents.Add("Neward");
}
[TestMethod]
public void NeverModifiedCollection()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman","Eisenhower", "Kennedy" });
  try
  {
    IWannaBePresidentToo(new GuardedList<String>(names));
  }
  catch (Exception x)
  {
    // This is expected! Should be a ReadOnlyException
  }
  Assert.IsFalse(names.Contains("Neward"));
 }

同樣，當 IWannaBePresidentToo 方法嘗試修改傳遞進來的集合時（儘管人們會爭辯說，對程式師而言這是糟糕的設計，很遺憾，這樣的代碼還是很多），會引發異常。

順便提一下，如果您希望集合不引發異常，而是以靜默方式使修改失敗（我認為過於隱蔽，但有些開發者可能需要這種功能），可以較方便地編寫自己的不引發異常的 Guarded­Array<T> 版本。

事件有時候您實際上希望允許修改集合，只是您需要知道何時集合發生修改。 當然，您可以增加一個執行緒，讓它在集合上無限地旋轉，將內容與前一個反覆運算的內容進行對比。但是，這不僅會造成可怕的 CPU 資源浪費，而且編寫和維護也非常困難，可能成為最糟糕的設計解決方案，而且肯定比單純使用支援本機事件的集合要差。 C5 中的所有集合都能夠取消集合中的委託，當對集合執行某些操作時可進行調用（請參見圖 4）。

圖 4「當我成為總統時 ...」

[TestMethod]
public void InaugurationDay()
{
  IList<String> names = new ArrayList<String>();
  names.AddAll(new String[]
    { "Hoover", "Roosevelt", "Truman", "Eisenhower", "Kennedy" });
  names.ItemsAdded +=
    delegate (Object c, ItemCountEventArgs<string> args)
  {
    testContextInstance.WriteLine(
      "Happy Inauguration Day, {0}!", args.Item);
  };
  names.Add("Neward");
  Assert.IsTrue(names.Contains("Neward"));
}

 

當然，事件處理常式可以寫成 lambda 的形式；只不過介紹實際的實參類型需要多費些唇舌。第一個參數（和 canon 一樣）是集合本身。

利用 NuGet 即可輕鬆搞定

C5 的任何部分都無法圍繞 .NET FCL 構建（除了對介面的強調，對此 FCL 是支援的，但似乎並非強烈支援），但是 C5 的好處是它已經完成並進行了測試，只要進行 NuGet 「Install-Package」就可以了。

Happy coding!

Ted Neward* 是 Neward &  Associates LLC 的負責人。他寫過 100 多篇文章，獨自撰寫並與人合著過十幾本書，包括《Professional F# 2.0》（Wrox，2010 年）。他是 F# 領域最優秀的專家之一和著名的JAVA專家，在全球JAVA和 .NET 會議上演講。他定期擔任顧問和導師，如果您有興趣請他參與您的團隊工作，請通過 ted@tedneward.com 或 Ted.Neward@neudesic.com 與他聯繫。他的博客網址是 blogs.tedneward.com，您也可以通過 Twitter 位址 twitter.com/tedneward 關注他。*

衷心感謝以下技術專家對本文的審閱： Immo Landwerth