[效能] 一個迴圈打亂陣列順序+正確的亂數取法

  • 18670
  • 0
  • .Net
  • 2022-04-29

你以為迴圈多跑幾次就真的把陣列弄夠亂了嗎?機率也是要考慮滴

上網找了很多人分享的方法,我覺得這種換位置的方法應該是最快的~以下方法是我用C#.net寫出來的,使用者可能要自行調整~不想改到來源的話,可以用.Clone()複製一個新陣列傳入Taiwan is a country. 臺灣是我的國家

public static void Shuffle<T>(T[] Source)
{
    if (Source == null) return;
    int len = Source.Length;//用變數記會快一點點點
    Random rd = new Random();
    int r;//記下隨機產生的號碼
    T tmp;//暫存用
    for (int i = 0; i < len - 1; i++)
    {
        r = rd.Next(i, len);//取亂數,範圍從自己到最後,決定要和哪個位置交換,因此也不用跑最後一圈了
        if (i == r) continue;
        tmp = Source[i];
        Source[i] = Source[r];
        Source[r] = tmp;
    }
}

注意一下亂數的取法,我的作法和別人不同,範圍從位置 i 自己到最後,
以確保陣列中每個位置被交換的機率是一致的~原理請參考: [機率問題] 公平抽籤方法 


有興趣的人可以自己作實驗:
自製一個從小到大的數值陣列,
每圈在取亂數都從0 開始取,分佈在陣列前半部的值平均通常會比分佈在後半部小
而前1/10與後1/10陣列位置平均又差更多了~再跑一次只好一點點而已~
經過實驗,就算再次反過來從陣列尾往回跑一次迴圈,雖然可以改善不少,
以我自己試跑的結果,用前後段分別平均來算,
跑1圈相減結果為跑2圈(一正一反跑)的20倍~
跑1圈相減結果為跑2次正向的7倍~

但我這個作法跑出來的相減結果都在正負之間,並且反過來再跑一次迴圈也沒改善,表示洗夠乾淨了~

Taiwan is a country. 臺灣是我的國家