我要在這裡說明的所謂「集合型別」指的並不是泛指 System.Collections 命名空間下的各種型別, 而是特別指自從 .Net 3.5 之後才出現的 Sets (集合) 型別, 特別是 System.Collections.Generic.HashSet 與 System.Collections.Generic.SortedSet 這兩個實作 ISet 介面的類別。ISet 介面是專門針對集合作業而設計的, 它提供了幾個特別的方法:
- ExceptWith() - 取差集
- IntersectWith() - 取交集
- IsProperSubsetOf() - 判斷是否為另一集合的嚴格子集合
- IsSubsetOf() - 判斷是否為另一集合的子集合
- IsProperSupersetOf() - 判斷是否為另一集合的嚴格母集合
- IsSupersetOf() - 判斷是否為另一集合的母集合
- Overlaps() - 判斷是否與指定的集合重疊
- SetEquals() - 判斷和指定的集合是否包含相同項目
- SymmetricExceptWith() - 取僅包含目前資料集或指定之集合 (但非兩者) 中出現的項目
- UnionWith() - 取聯集
以上提到的「嚴格子集合」(英文是 Proper Subset 或 Strict Subset) 意思是指一個集合是另一個集合的子集合, 但是兩集合不可以相等。例如 {1, 2, 3} 可以是 {1, 2, 3} 的子集合, 但不是其嚴格子集合。而 {1, 2} 則是 {1, 2, 3} 的子集合, 也是其嚴格子集合。同理可推「嚴格母集合」。
在數學上, 「嚴格子集合」也可稱為「真子集」, 「嚴格母集合」可稱為「真母集」。
HashSet 與 SortedSet 和其它集合型別不同; 基本上, 這兩種型別的資料結構是採用雜湊表(HashTable) 的邏輯來實作的。以白話來講, 你可以把它當作是「一個蘿蔔一個坑」; 來一顆白蘿蔔就為它挖一個坑, 來一顆紅蘿蔔就再挖一個坑, 依此類推。不過, 這種集合型別並不允許你把同一種蘿蔔放在不同的坑裡面 (因為這是雜湊表的特性)。例如以下的程式碼:
HashSet<int> hs = new HashSet<int>() { 1, 1, 2 };
Console.WriteLine(hs.Count);
其輸出值是 2。如果你把上面的 HashSet<int> 改成 List<int>, 那麼輸出值會是 3, 而不是 2。
至於 SortedSet 只是把 HashSet 加上自動排序的功能而已, 其本質和 HashSet 是差不多的。
如果我們拿 HashSet<T>、SortedSet<T> 和 List<T> 這三種型別來做比較, 那麼首先我們可以看出 List<T> 實作了 IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable 這幾種介面, 而 HashSet<T> 和 SortedSet<T> 則實作了 ISerializable, IDeserializationCallback, ISet<T>, ICollection<T>, IEnumerable<T>, IEnumerable 這幾種介面。中間最大的差異在於HashSet<T> 和 SortedSet<T> 有實作 ISet 而 List<T> 有實作 IList。
ISet 比 IList 多了許多集合專用的方法, 但是卻比 IList 少了 Insert()、IndexOf() 和 RemoveAt() 等方法。
在效率方面, 如果我們把 10 萬個整數加入到 HashSet、SortedSet 和 List 物件中, 那麼 List 物件的新增 (Add) 操作是最快的, HashSet 其次, SortedSet 最慢。這是很容易理解的, 因為每次我們新增一筆資料到 SortedSet 集合之後, 它必須重新排序一次, 所以難免影響效能。
其實如果你熟悉 Hashing 邏輯的話, 你也許會和我一樣, 懷疑為什麼 Microsoft 並沒有提供 HashSet 在其建構函式中指定容量大小的功能。相對的, Microsoft 卻提供 HashTable 型別的建構函式這個功能 (如果你把程式中的 HashSet 改成 HashTable 型別並預先定義大小的話, 你會發現把內容新增到 HashTable 物件的花費時間將只有使用 HashSet 的一半還不到)。我認為這是因為 HashSet 是一個泛型的型別, 它所使用的 Hashing 函數也許不適合讓使用者自行宣告其雜湊表大小的緣故。.Net 會自己根據你所指定的 <T> 型別以動態的決定其雜湊表大小, 不允許使用者自己決定。但是相對的, 這也會稍為影響到效能和可接受的物件大小。而且, 如果你的電腦容量不大的話, 你也許會發現你甚至無法建立起 10 萬筆的 HashSet 物件, 可能會出現記憶體不足的錯誤, 而 List 物件卻可以輕鬆而快速的建立完成, 因為 List 採用 Linked List 邏輯來實作, 而不是一個無法預先定義大小的雜湊表。
其次, 如果我們打算在剛才加入的 10 萬個整數中搜尋任意一筆資料, 那麼 SortedSet 物件是最快的; List 物件也不遑多讓, 至於 HashSet 則是最慢的。不過這三者的差異其實並不明顯。
但是如果我們打算進行集合操作的話(例如取交集), 那麼差距就會非常、非常明顯了。我分別建立了一個 10 萬筆和 5 萬筆的兩個 HashSet 物件/SortedSet 物件/List 物件, 然後互相比較運算時間之後, 發現 List 物件需要比 SortedSet 多花上 1,504 倍的時間, 比 HashSet 物件多花上 3,760 倍的時間。我認為以上這個數字恐怕還是低估的, 因為我觀察到在我的電腦上, 當這個程式在執行時, 我從工作管理員上看到我的八個 CPU 處理緒中至少有四個 CPU 使用率是特別高的。我懷疑 .Net 可能自動把某些運算分派給不同的 CPU 核心去處理了。如果你的電腦並非多核心的 CPU, 上述差距恐怕只會更大, 不會更小。
程式執行結果如下:
由於 List 型別並沒有提供 IntersectWith() 之類的方法, 所以我們必須自己寫程式去做。以取交集為例, 對目標集合的每一個值而言, 其拜訪對象集合的效能計量為 O(n), 但對於 HashSet 為 O(1), 對 SortedSet 則為 O(log n), 難怪效率差距那麼巨大了。如果你希望進一步研究這個主題的話, 可以參考 James Michael Hare 的部落格。
以下是完整的原始程式。由於這個程式都是平舖直鈙的, 我就不多加說明了。
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace TrySets
{
class Program
{
const int maxSize = 100000;
static Stopwatch watch = new Stopwatch();
static HashSet<int> hashSet1 = new System.Collections.Generic.HashSet<int>();
static HashSet<int> hashSet2 = new System.Collections.Generic.HashSet<int>();
static SortedSet<int> sortedSet1 = new System.Collections.Generic.SortedSet<int>();
static SortedSet<int> sortedSet2 = new System.Collections.Generic.SortedSet<int>();
static List<int> list1 = new System.Collections.Generic.List<int>();
static List<int> list2 = new System.Collections.Generic.List<int>();
static void Main(string[] args)
{
Console.WriteLine("Initiate collection objects by inserting {0:N0} integers.\r\n" +
"============================================================",
maxSize);
Console.Write("Initiating HashSet<int> object");
Console.WriteLine(" - elapsed time: {0}",
addHashSets().ToString());
Console.Write("Initiating SortedSet<int> object");
Console.WriteLine("- elapsed {0}",
addSortedSets().ToString());
Console.Write("Initiating List<int> object");
Console.WriteLine("- elapsed {0}",
addLists().ToString());
Random rnd = new Random(DateTime.Now.Millisecond);
int r = rnd.Next(0, maxSize);
bool isContains = false;
Console.WriteLine("\r\nFind specific number \"{0:N0}\" in collections.\r\n" +
"============================================================",
r);
Console.Write("Finding in HashSet<int> object");
Console.WriteLine(" - elapsed time: {0}, found? {1}",
measureHashSetContains(r, out isContains).ToString(), isContains);
Console.Write("Finding in SortedSet<int> object");
Console.WriteLine(" - elapsed time: {0}, found? {1}",
measureSortedSetContains(r, out isContains).ToString(), isContains);
Console.Write("Finding in List<int> object");
Console.WriteLine(" - elapsed time: {0}, found? {1}",
measureListContains(r, out isContains).ToString(), isContains);
int remains = 0;
Console.WriteLine("\r\nMeasure intersect operations on collections.\r\n" +
"============================================================");
Console.Write("Processing HashSet<int> objects");
Console.WriteLine(" - elapsed time: {0}, {1:N0} items remained.",
measureHashSetIntersects(out remains).ToString(), remains);
Console.Write("Processing SortedSet<int> objects");
Console.WriteLine(" - elapsed time: {0}, {1:N0} items remained",
measureSortedSetIntersects(out remains).ToString(), remains);
Console.Write("Processing List<int> objects");
Console.WriteLine(" - elapsed time: {0}, {1:N0} items remained",
measureListIntersects(out remains).ToString(), remains);
Console.Write("Press any key to exit... ");
Console.ReadKey(true);
}
private static TimeSpan addHashSets()
{
watch.Restart();
for (int i = 0; i < maxSize; i++)
{
hashSet1.Add(i);
if (i % 2 == 0)
hashSet2.Add(i); // set2 contains only even numbers
}
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan addSortedSets()
{
watch.Restart();
for (int i = 0; i < maxSize; i++)
{
sortedSet1.Add(i);
if (i % 2 == 0)
sortedSet2.Add(i); // set2 contains only even numbers
}
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan addLists()
{
watch.Restart();
for (int i = 0; i < maxSize; i++)
{
list1.Add(i);
if (i % 2 == 0)
list2.Add(i); // list2 contains only even numbers
}
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan measureHashSetContains(int num, out bool isTrue)
{
watch.Restart();
isTrue = hashSet1.Contains(num);
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan measureSortedSetContains(int num, out bool isTrue)
{
watch.Restart();
isTrue = sortedSet1.Contains(num);
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan measureListContains(int num, out bool isTrue)
{
watch.Restart();
isTrue = list1.Contains(num);
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan measureHashSetIntersects(out int intersects)
{
watch.Restart();
hashSet1.IntersectWith(hashSet2);
intersects = hashSet1.Count;
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan measureSortedSetIntersects(out int intersects)
{
watch.Restart();
sortedSet1.IntersectWith(sortedSet2);
intersects = sortedSet1.Count;
watch.Stop();
return watch.Elapsed;
}
private static TimeSpan measureListIntersects(out int intersects)
{
watch.Restart();
List<int> list3 = new List<int>();
foreach (int i in list1)
if (list2.Contains(i))
list3.Add(i);
intersects = list3.Count;
watch.Stop();
return watch.Elapsed;
}
}
}
沒有留言:
張貼留言