[C#/VB.net] 集合的亂數排序：Java有shuffle方法一行Code馬上實現，C#/VB.net 就用......

2011-12-30

20310
0
.Net Framework
2012-09-08

一般要做亂數排序的話

大概會像此發問者，遵守學校老師教的方式

弄一個while迴圈，然後在迴圈裡產生亂數，並判斷如果集合裡沒有此亂數的話，才加入集合裡

但此位發問者也不是省油的燈，請看第二點

確實若要產生的亂數數量比較多的時候，還在用while迴圈+if判斷的方法，很容易因為產生出來的亂數第一輪迴圈重覆了，第二輪又重覆，第三輪再重覆…等等，造成程式多跑幾次迴圈的現象

要解決此問題，Java可以使用Collections.shuffle();實現亂數排序(或手寫洗牌演算法)

package javaapplicationtest;

import java.util.ArrayList;
/*要引用此命名空間*/
import java.util.Collections;


public class JavaApplicationTest {

    /*Java版Console程式*/
    public static void main(String[] args) {
       
        //Step 1.產生一個泛型集合
        ArrayList<String> list=new ArrayList<String>();
        //Step 2.依序加入Apple、Banana、Cherry和Grape字串
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");
        list.add("Grape");
        //Step 3.※重點在這，Java只要使用一行Code，亂數排序便完成
        Collections.shuffle(list);
        
        //之後只要樂勝地走訪印出剛剛排序完後的結果就沒了
        for(String result:list)
        {
         System.out.println(result);
        }
        
    }
}

執行結果：

反觀.net 方面，我只有找到.net 2005的J# 語言有shuffle()方法，不過J#在台灣業界應該超少人使用，另外跟Java版的說明文件比起來，呃…

回歸正題

很久以前就一直想把Java的shuffle這個好用的方法在.net C#/VB.net上實現，無奈一直找不到短碼的演算法

我的程度太差還停留在乖乖地做隨機交換動作(洗牌演算法)

直到昨天發現對岸論壇的帖子：生成不重复随机数和固定数组乱序的问题

Wei_Dong (MCC) 提出了一個不錯的點子

一直以來在論壇上鬼混終於有收穫，很感謝此位MCC提供這麼好的思路

自己先做個實驗的Code


using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleShuffle
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> list = new List<string>();
            //Step 1.加入字串Apple、Banana、Blueberry、Cherry、Grape
            list.Add("Apple"); list.Add("Banana"); list.Add("Blueberry");
            list.Add("Cherry"); list.Add("Grape");

            Random rand = new Random(Guid.NewGuid().GetHashCode());
            List<string> newList = new List<string>();//儲存結果的集合
            foreach (string item in list)
            {
                newList.Insert(rand.Next(0, newList.Count), item);
            }
          
            //顯示結果
            foreach (string item in newList)
            {
                Console.WriteLine(item);
            }


            Console.ReadKey();
        }
    }
}

執行看看：

第一次

第二次

第三次

會發現有個小Bug，由於這句


foreach (string item in list)
{
    newList.Insert(rand.Next(0, newList.Count), item);
}

迴圈第一次執行時候就把Apple字串加到0的位置，之後才是真正的隨機亂插入位置，才會導致每次執行結果

最後一筆永遠都是Apple

所以程式碼須再加入兩行Code改良


static void Main(string[] args)
        {
            List<string> list = new List<string>();
            //Step 1.加入字串Apple、Banana、Blueberry、Cherry、Grape
            list.Add("Apple"); list.Add("Banana"); list.Add("Blueberry");
            list.Add("Cherry"); list.Add("Grape");

            Random rand = new Random(Guid.NewGuid().GetHashCode());
            List<string> newList = new List<string>();//儲存結果的集合
            foreach (string item in list)
            {
                newList.Insert(rand.Next(0, newList.Count), item);
            }
            newList.Remove(list[0]);//移除list[0]的值(Apple)
            newList.Insert(rand.Next(0, newList.Count), list[0]);//再重新隨機插入
            //顯示結果
            foreach (string item in newList)
            {
                Console.WriteLine(item);
            }


            Console.ReadKey();
        }

執行結果：

第一次

第二次

第三次

這樣集合夠亂了吧

程式碼邏輯和Bug都確認沒問題後，接著開始打造自己的shuffle方法

先新增一個類別


using System;
using System.Collections.Generic;
using System.Text;


public class MyCollections
{
    public static void shuffle<T>(ref List<T> list)
    {
      
            
    }
}

然後把Console裡的紅框處(亂序插入邏輯)拆開到自己新增的類別MyCollections

接著再把string型別通通改成T，避免以下紅底線出現

並把傳入的參數list指向newList(打亂過後的List集合)


using System;
using System.Collections.Generic;
using System.Text;


public class MyCollections
{
    public static void shuffle<T>(ref List<T> list)
    {
        Random rand = new Random(Guid.NewGuid().GetHashCode());
        List<T> newList = new List<T>();//儲存結果的集合
        foreach (T item in list)
        {
            newList.Insert(rand.Next(0, newList.Count), item);
        }
        newList.Remove(list[0]);//移除list[0]的值
        newList.Insert(rand.Next(0, newList.Count), list[0]);//再重新隨機插入第一筆

        list = newList;

    }
}

自己手工打造的shuffle方法於是完成～

接著回到Console看使用方式


using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleShuffle
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> list = new List<string>();
            //Step 1.加入字串Apple、Banana、Blueberry、Cherry、Grape
            list.Add("Apple"); list.Add("Banana"); list.Add("Blueberry");
            list.Add("Cherry"); list.Add("Grape");

            //Step 2.打亂順序
            MyCollections.shuffle(ref list);

             
            //Step 3 .Net也可以很樂勝地顯示結果
            foreach (string item in list)
            {
                Console.WriteLine(item);
            }
            

            Console.ReadKey();
        }
    }
}

執行結果：

第一次

第二次

第三次

另外看VB.net 語法


Imports System.Collections.Generic
Imports System.Text


Public Class MyCollections
    Public Shared Sub shuffle(Of T)(ByRef list As List(Of T))
        Dim rand As New Random(Guid.NewGuid().GetHashCode())
        Dim newList As New List(Of T) '儲存結果的集合

        For Each item As T In List
            newList.Insert(rand.Next(0, newList.Count), item)
        Next
        newList.Remove(List(0)) '移除list(0)的值

        newList.Insert(rand.Next(0, newList.Count), List(0)) '再重新隨機插入第一筆
        List = newList

    End Sub
End Class

VB.net 的Console程式，使用方式


Imports System.Collections.Generic
Imports System.Text


Module Module1

    Sub Main()
        Dim list As New List(Of String)
        'Step 1.加入字串Apple、Banana、Blueberry、Cherry、Grape
        list.Add("Apple")
        list.Add("Banana")
        list.Add("Blueberry")
        list.Add("Cherry")
        list.Add("Grape")

        'Step 2.打亂順序
        MyCollections.shuffle(list)


        'Step 3 .Net也可以很樂勝地顯示結果
        For Each item As String In list
            Console.WriteLine(item)
        Next


        Console.ReadKey()
    End Sub
End Module

開放下載 C#和VB.net兩種語言的MyCollections類別，可依自行需求做修改或其他最佳化後丟到類別庫專案Build成.dll檔

(適用於.net 2.0以上)


using System;
using System.Collections.Generic;
using System.Text;


public class MyCollections
{
    public static void shuffle<T>(ref List<T> list)
    {
        Random rand = new Random(Guid.NewGuid().GetHashCode());
        List<T> newList = new List<T>();//儲存結果的集合
        foreach (T item in list)
        {
            newList.Insert(rand.Next(0, newList.Count), item);
        }
        newList.Remove(list[0]);//移除list[0]的值
        newList.Insert(rand.Next(0, newList.Count), list[0]);//再重新隨機插入第一筆

        list = newList;

    }
}

VB.net


Imports System.Collections.Generic
Imports System.Text


Public Class MyCollections
    Public Shared Sub shuffle(Of T)(ByRef list As List(Of T))
        Dim rand As New Random(Guid.NewGuid().GetHashCode())
        Dim newList As New List(Of T) '儲存結果的集合

        For Each item As T In List
            newList.Insert(rand.Next(0, newList.Count), item)
        Next
        newList.Remove(List(0)) '移除list(0)的值

        newList.Insert(rand.Next(0, newList.Count), List(0)) '再重新隨機插入第一筆
        List = newList

    End Sub
End Class

※2011.12.30 用 System.Diagnostics.Stopwatch實際測試，發現自己寫的MyCollections洗牌的效率居然比手寫洗牌演算法還慢，囧rz

原因應該是因為MyCollections多了

List<string> newList = new List<string>();//儲存結果的集合

來操作的關係

補上測試Code：


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        
        static void Main(string[] args)
        {
            List<int> list = new List<int>(Enumerable.Range(1,100000));
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            watch.Restart();
            //打乱
            shuffle(list);
            watch.Stop();
            Console.WriteLine("手寫洗牌演算法消耗：" +watch.ElapsedMilliseconds +"毫秒");
            list = new List<int>();
            watch.Restart();
            //動態隨機插入做法
            for (int i = 1; i < 100000; i++)
            {
                list.Insert(rand.Next(0, list.Count), i);
            }
            watch.Stop();
            Console.WriteLine("動態隨機插入：" + watch.ElapsedMilliseconds + "毫秒");
            list = new List<int>(Enumerable.Range(1, 100000));//到達一百萬就不行了
            watch.Restart();
            //自己寫的MyCollections類別
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("自己寫的MyCollections類別shuffle方法："+watch.ElapsedMilliseconds + "毫秒");


            Console.ReadKey();

        }

        // swaps array elements i and j
        public static void exch(List<int> list, int i, int j)
        {

            int swap = list[i];
            list[i] = list[j];
            list[j] = swap;
        }


        // take as input an array of strings and rearrange them in random order
        public static void shuffle(List<int> list)
        {
            int N = list.Count;
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            for (int i = 0; i < N; i++)
            {
                int r = (rand.Next(0, N)); // between i and N-1
                exch(list, i, r);
            }
        }

 

    }
}

執行結果：

第一次

第二次

第三次

果然短碼偷懶是不行的，要更有效率的話，還是得手寫洗牌演算法

附上改良過後的MyCollections.shuffle()


using System;
using System.Collections.Generic;
using System.Text;


public class MyCollections
{
   

    // swaps array elements i and j
    private  static void exch<T>(List<T> list, int i, int j)
    {
        T swap = list[i];
        list[i] = list[j];
        list[j] = swap;
    }


    // take as input an array of strings and rearrange them in random order
    public static void shuffle<T>(ref List<T> list)
    {
        int N = list.Count;
        Random rand = new Random(Guid.NewGuid().GetHashCode());
        for (int i = 0; i < N; i++)
        {
            int j = (rand.Next(0, N)); // between i and N-1
            exch(list, i, j);
        }
    }
}

Console測試代碼：


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication2
{
    class Program
    {
        
        static void Main(string[] args)
        {
            
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();

            List<int> list = new List<int>();
            watch.Restart();
            //動態隨機插入做法
            for (int i = 1; i < 100000; i++) //※到1百萬就不行了
            {
                list.Insert(rand.Next(0, list.Count), i);
            }
            watch.Stop();
            Console.WriteLine("動態隨機插入：" + watch.ElapsedMilliseconds + "毫秒");
            list = new List<int>(Enumerable.Range(1, 100000)); 
            watch.Restart();
            //改良過後的MyCollections類別
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("改良過後的MyCollections類別shuffle方法：" + watch.ElapsedMilliseconds + "毫秒");


            Console.ReadKey();

        }

        

 

    }
}

執行結果：

第一次

第二次

第三次

※2011.12.30 中午追記，發現這樣的比較測試對動態插入法不太公平，因為動態插入法是Insert Value+亂序同時處理

所以我決定讓洗牌演算法也計算Insert Value的時間再測試一遍


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            List<int> list = new List<int>();
            watch.Restart();
            //動態隨機插入做法  
            for (int i = 1; i < 100000; i++) //※到1百萬就不行了  
            {
                list.Insert(rand.Next(0, list.Count), i);
            }
            watch.Stop();
            Console.WriteLine("動態隨機插入：" + watch.ElapsedMilliseconds + "毫秒");
            watch.Restart();
            list = new List<int>(Enumerable.Range(1, 100000));
            //改良過後的MyCollections類別  
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("洗牌演算法(Enumerable.Range()加入數字)：" + watch.ElapsedMilliseconds + "毫秒");
            list = new List<int>();//還原

            watch.Restart();
            for (int i = 1; i <= 100000; i++)//跑迴圈加入數字
            {
                list.Add(i);
            }
            //改良過後的MyCollections類別  
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("洗牌演算法(for-loop加入數字)：" + watch.ElapsedMilliseconds + "毫秒");





            Console.ReadKey();  


        }
    }
}

執行結果：

第一次

第二次

第三次

洗牌演算法已讓步，連加入Value的時間也一起算的話，仍舊大勝動態插入法

為了公平起見，把兩個演算法調換位置再測一遍


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {

            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            List<int> list = new List<int>();
            watch.Restart();
            for (int i = 1; i <= 100000; i++)//跑迴圈加入數字
            {
                list.Add(i);
            }
            //改良過後的MyCollections類別  
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("洗牌演算法(for-loop加入數字)：" + watch.ElapsedMilliseconds + "毫秒");
            watch.Restart();
            list = new List<int>(Enumerable.Range(1, 100000));
            //改良過後的MyCollections類別  
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("洗牌演算法(Enumerable.Range()加入數字)：" + watch.ElapsedMilliseconds + "毫秒");
            watch.Restart();
            //動態隨機插入做法  
            for (int i = 1; i < 100000; i++) //※到1百萬就不行了  
            {
                list.Insert(rand.Next(0, list.Count), i);
            }
            watch.Stop();
            Console.WriteLine("動態隨機插入：" + watch.ElapsedMilliseconds + "毫秒");


            Console.ReadKey();  


        }
    }
}

執行結果：

第一次

第二次

第三次

※2011.12.30 超感謝黑暗大提供Linq亂數排序

經過測試10萬筆數字


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();
            //使用本人提供的 MyCollections.shuffle(ref list);
            watch.Restart();//開始計數
            List<int> list = new List<int>(Enumerable.Range(1, 100000));
            //改良過後的MyCollections類別(採用交換位址的洗牌演算法)    
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("洗牌演算法：" + watch.ElapsedMilliseconds + "毫秒");

            //使用Linq
            watch.Restart();//開始計數
            List<int> listLinq = new List<int>(Enumerable.Range(1, 100000));
            listLinq.OrderBy(o => rand.Next()).ToList();
            watch.Stop();
            Console.WriteLine("Linq亂數排序：" + watch.ElapsedMilliseconds + "毫秒");

           



            Console.ReadKey();
        }
    }
}

執行結果：

把兩個演算法位置對調


using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();

            //使用Linq
            watch.Restart();//開始計數
            List<int> listLinq = new List<int>(Enumerable.Range(1, 100000));
            listLinq.OrderBy(o => rand.Next()).ToList();
            watch.Stop();
            Console.WriteLine("Linq亂數排序：" + watch.ElapsedMilliseconds + "毫秒");



            //使用本人提供的 MyCollections.shuffle(ref list);
            watch.Restart();//開始計數
            List<int> list = new List<int>(Enumerable.Range(1, 100000));
            //改良過後的MyCollections類別(採用交換位址的洗牌演算法)    
            MyCollections.shuffle(ref list);
            watch.Stop();
            Console.WriteLine("洗牌演算法：" + watch.ElapsedMilliseconds + "毫秒");




            Console.ReadKey();
        }
    }
}

執行結果：

看起來Linq小輸洗牌演算法

所以這次資料要以100萬筆資料再測試

執行結果：

兩個演算法對調位置再測時間

~~結果證明，當數據量愈多，洗牌演算法最具效率~~

※2011.12.30 感謝91版主提醒，經過測試確實.ToList()或.ToArray();會造成Linq效率較差

由於Linq有延遲執行特性，所以範例程式再改寫測試，而且為了公平，這次一個主程式只執行一種演算法

先看Linq


static void Main(string[] args)
        {
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();

           

            //使用Linq
            watch.Restart();//開始計數
            List<int> listLinq = new List<int>(Enumerable.Range(1, 1000000));//使用100萬數字
            var result = listLinq.OrderBy(o => rand.Next());//最後不能.ToList也不能.ToArray()，否則效率會慢
            //因為Linq有延遲執行特性，所以要跑foreach讓它真正執行
            foreach (var item in result)
            {
                Console.WriteLine(item);
            }
            watch.Stop();
            Console.WriteLine("Linq亂數排序：" + watch.ElapsedMilliseconds + "毫秒");



         
             
            Console.ReadKey();
        }

執行結果：

再看本人提供的洗牌演算法：


static void Main(string[] args)
        {
            Random rand = new Random(Guid.NewGuid().GetHashCode());
            System.Diagnostics.Stopwatch watch = new System.Diagnostics.Stopwatch();

            //使用本人提供的 MyCollections.shuffle(ref list);
            watch.Restart();//開始計數
            List<int> list = new List<int>(Enumerable.Range(1, 1000000));//使用100萬數字
            //改良過後的MyCollections類別(採用交換位址的洗牌演算法)    
            MyCollections.shuffle(ref list);
            foreach (int item in list)
            {
                Console.WriteLine(item);
            }
            watch.Stop();
            Console.WriteLine("洗牌演算法：" + watch.ElapsedMilliseconds + "毫秒");

           
            Console.ReadKey();
        }

執行結果：

所以目前(2011.12.30)結論

.net 3.5 以上請直接使用Linq

.net 2.0 則使用本人提供的類別MyCollections


using System;
using System.Collections.Generic;
using System.Text;


public class MyCollections
{
   

    // swaps array elements i and j
    private  static void exch<T>(List<T> list, int i, int j)
    {
        T swap = list[i];
        list[i] = list[j];
        list[j] = swap;
    }


    // take as input an array of strings and rearrange them in random order
    public static void shuffle<T>(ref List<T> list)
    {
        int N = list.Count;
        Random rand = new Random(Guid.NewGuid().GetHashCode());
        for (int i = 0; i < N; i++)
        {
            int j = (rand.Next(0, N)); // between i and N-1，建議把0改成i，底下有說明 
            exch(list, i, j);
        }
    }
}

文章：透過LINQ取得不重複的隨機數值 - 不騙你，只需要一行程式碼!!

2012.9.8 今天上部落格又長知識了

原本寫

for (int i = 0; i < N; i++)
        {
            int j = (rand.Next(0, N)); // between i and N-1
            exch(list, i, j);
        }
幹嘛每次都從位置0開始隨機挑亂數呢？已打亂過的位置就略過它吧，效率會更好點

        for (int i = 0; i < N; i++)
        {
            int j = (rand.Next(i, N)); //把0改成i
            exch(list, i, j);
        }

回首頁