見微知著：從鏈表中不重複隨機元素

如題，給出一個長度為N的List<int>，裡面每個元素都不相同，要求從中隨機M個不重複元素(1<M<N)。代碼描述如下：

public sealed class RandomFromListSample { private static Random RandomEvent = new Random(); public RandomFromListSample(int sourceCount, int resultCount) { SourceCount = sourceCount; ResultCount = resultCount; InitializeSample(); } private List<int> sourceList; public int SourceCount { get; } public int ResultCount { get; } private void InitializeSample() { sourceList = new List<int>(SourceCount); for (int i = 0; i < SourceCount; i++) { sourceList.Add(i); } } public int[] RandomItem() { //…… } }

想當初，我第一次實現RandomItem()如下：

public int[] RandomItemUglily() { int[] result = new int[ResultCount]; for (int i = 0; i < ResultCount; i++) { int index = RandomEvent.Next(0, sourceList.Count); result[i] = sourceList[index]; sourceList.RemoveAt(index); } return result; }

很直觀的思路：每次隨機一個sourceList的索引index，賦值到數組對應位置，然後移除出sourceList，重複這樣的步驟即可。讓我們接著寫一個測試，從500000個元素的鏈表中隨機不重複地取出100000個，返回一個數組。

private static void Main(string[] args) { Stopwatch sw = new Stopwatch(); int N = 500000; int M = 100000; RandomFromListSample sample = new RandomFromListSample(N, M); sw.Start(); sample.RandomItemUglily(); sw.Stop(); Console.WriteLine(sw.ElapsedMilliseconds.ToString()); Console.ReadKey(); }

在我的電腦環境下（CPU：Intel Core i3-4170 @3.70GHz，內存：8G，程序：Release版本），RandomItemUglily()的執行時間約在4000ms這個量級。

哎呀呀，感覺時間有點長啊……趕緊用性能探查器看看。

原來如此，是List<T>的RemoveAt(int index)方法作祟啊。因為List內部還是基於數組實現，移除的時候需要移動數組內元素的位置，這些都被封裝在了抽象類Array下的靜態方法Copy()中。

好吧，那我們就少點Remove操作好了：

public int[] RandomItem1() { int temp; for (int i = 0; i < ResultCount; i++) { int index = RandomEvent.Next(i, sourceList.Count); temp = sourceList[index]; sourceList[index] = sourceList[i]; sourceList[i] = temp; } sourceList.RemoveRange(SourceCount - ResultCount - 1, ResultCount); return sourceList.ToArray(); }

每次隨機的時候，我們將隨機到的index與i位置的元素做交換，這樣鏈表的前頭是隨機出的結果，後頭是待隨機的數據。最後要用的時候，將未隨機到的數據通過RemoveRange(int index, int count)方法一次性丟掉。

有細心的讀者可能會問：為啥要把待隨機的數據放在後頭？如果反過來呢？

可以想一下：鏈表的移除操作是移除頭快還是移除尾快？移除末尾的元素，直接移除就好了，不需要操作數組其他元素；移除頭部的元素呢？需要把後面的元素都左移一個索引單位。所以還是儘可能把要移除的數據往末尾放吧。

現在跑一次測試，結果是多少呢？20ms上下，比之前的做法快了2個數量級！Perfec……等等！為什麼要移除？

public int[] RandomItem2() { int[] result = new int[ResultCount]; for (int i = 0; i < ResultCount; i++) { int index = RandomEvent.Next(i, sourceList.Count); result[i] = sourceList[index]; sourceList[index] = sourceList[i]; } return result; }

好吧其實提升甚微，大多數情況下，一次移除操作的性能損耗相較於隨機過程，並不佔大頭。而且如果不返回一個數組而是返回一個有序鏈表呢？我們可以將RandomItem1()稍作修改就可以了：

public List<int> RandomItem1() { int temp; for (int i = 0; i < ResultCount; i++) { int index = RandomEvent.Next(i, sourceList.Count); temp = sourceList[index]; sourceList[index] = sourceList[i]; sourceList[i] = temp; } sourceList.RemoveRange(SourceCount - ResultCount - 1, ResultCount); sourceList.Sort(); return sourceList; }

不過，還是盡量採用RandomItem2()方法吧，代碼簡約且理論上性能影響最小，何樂而不為哉？

現在如果把題目再拓展一下：如果長度為N的原始鏈表中有K種不同元素，即存在重複元素，要求隨機M個不重複元素（1<M<K<N）。

該怎麼做呢？一種做法是先把原始鏈表「去重」，把重複的數量和元素的值包裝起來按照權重隨機，餘下的就化歸成了上面的問題，但是想想也知道……這也太費勁了。其實可以按照上面的思路，每次將隨機的結果跟鏈表頭部交換，將檢測到的重複數據跟鏈表尾部交換，每次隨機取中間段的數據，不就可以了嘛！示例如下：

public int[] RandomItem11()//因為只是展示，所以命名就比較隨意，正式環境下切勿模仿！ { int repeatCount = 0; int tempResultCount = 0; int temp; for (int i = 0; i < SourceCount; i++) { int index = RandomEvent.Next(tempResultCount, sourceList.Count - repeatCount); //檢查重複性 bool findRepeatedItem = false; for (int j = 0; j < tempResultCount; j++) { if (sourceList[j] == sourceList[index])//發現重複元素 { //把重複的元素與末尾交換 temp = sourceList[SourceCount - 1 - repeatCount]; sourceList[SourceCount - 1 - repeatCount] = sourceList[index]; sourceList[index] = temp; findRepeatedItem = true; break; } } if (findRepeatedItem) { repeatCount++; continue; } //把隨機的結果與頭部交換 temp = sourceList[tempResultCount]; sourceList[tempResultCount] = sourceList[index]; sourceList[index] = temp; tempResultCount++; if (tempResultCount >= ResultCount) { break; } } sourceList.RemoveRange(ResultCount, SourceCount - ResultCount); return sourceList.ToArray(); }

但是上述代碼檢查重複性是一個O(N)的操作，我們可以採取HashSet<T>來降低演算法複雜度：

public int[] RandomItem12() { HashSet<int> resultSet = new HashSet<int>(); int repeatCount = 0; int tempResultCount = 0; int temp; for (int i = 0; i < SourceCount; i++) { int index = RandomEvent.Next(tempResultCount, sourceList.Count - repeatCount); //檢查重複性 if (resultSet.Contains(sourceList[index])) { //把重複的元素與末尾交換 temp = sourceList[SourceCount - 1 - repeatCount]; sourceList[SourceCount - 1 - repeatCount] = sourceList[index]; sourceList[index] = temp; repeatCount++; continue; } //隨機的結果直接保存到HashSet中，不需要交換 resultSet.Add(sourceList[index]); sourceList[index] = sourceList[tempResultCount]; tempResultCount++; if (tempResultCount >= ResultCount) { break; } } int[] result = new int[ResultCount]; resultSet.CopyTo(result); return result; }

我們將RandomFromListSample類中的InitializeSample()方法稍作修改：

private void InitializeSample() { sourceList = new List<int>(SourceCount); for (int i = 0; i < SourceCount; i++) { sourceList.Add(i / 10); } }

這樣就可以產生有重複元素的原始鏈表了。設定N=500000，M=10000，讓我們看看運行時間的差距：

已經1個數量級了，畢竟HashSet<T>是O(1)的時間複雜度呀！用點內存換性能，在極端環境下，好像還是很值的。

寄語

C#（或者嚴格來說是.Net）經常被一些程序猿詬病：用的時候很爽，可運行起來效率不高。效率真的不高嗎？任何編程都有自己的劣勢，但性能絕不是C#的劣勢。我其實部分贊同這樣的觀點：「C#最大的壞處就是讓入門的程序員以為自己會編程。」但是話說回來，如果對編程感興趣的話，應該不會滿足於做一個「API使用者」吧？用C#優雅乾淨的語法都能寫出低效、醜陋的程序，這不是C#和.Net的罪過吧。

最後，祝各位新年大吉，前程錦繡！