Rastgelelik Algoritmaları: Fisher–Yates Shuffle, Reservoir Sampling, Weighted Random ve .NET'te Random.Shared, Shuffle, GetItems

Sürüm notu: Bu yazıdaki kodlar .NET 10, C# 14 ve System.IO.Hashing 10.0.15 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Sitedeki serilerin ortak örnek uygulaması Bookstore (bir online kitapçı), ana sayfadaki "önerilen kitaplar" listesini karıştırarak gösteriyor. Code review'da iki öneri var. Birincisi her pozisyonu array'in rastgele bir pozisyonuyla yer değiştiriyor:

for (int i = 0; i < items.Length; i++)
{
    int j = random.Next(items.Length);
    (items[i], items[j]) = (items[j], items[i]);
}

İkincisi tek satır: Array.Sort(items, (_, _) => random.Next(-1, 2)). A, B ve C'yi 600.000 kez karıştırırsak altı sıralamanın her biri yaklaşık yüzde 16,7 çıkmalı. Hangisi bunu sağlar: ikisi de mi, biri mi, hiçbiri mi?

Fisher–Yates ve Neden Doğru Olduğu

// Fisher-Yates (Durstenfeld): sondan başa yürü, i'yi [0, i] aralığından rastgele bir index'le değiştir
public static void FisherYates<T>(Span<T> items, Random random)
{
    for (int i = items.Length - 1; i > 0; i--)
    {
        int j = random.Next(i + 1);
        (items[i], items[j]) = (items[j], items[i]);
    }
}

Fisher ve Yates 1938'de bu yöntemi kâğıt kalemle istatistik tabloları için tarif etti; bilgisayar için O(n) versiyonunu Richard Durstenfeld 1964'te yayımladı. Fikir: son pozisyona kalan n element'ten biri eşit olasılıkla seçilir, sonra kalan n−1 element için aynı iş tekrarlanır. Toplam n·(n−1)·…·1 = n! eşit olasılıklı yol var ve her permütasyona tam olarak bir yol gidiyor. Açılıştaki iki öneriyle birlikte ölçtüm:

Fisher-Yates     ABC=16.7% ACB=16.6% BAC=16.8% BCA=16.6% CAB=16.6% CBA=16.6%
naive swap       ABC=14.8% ACB=18.5% BAC=18.5% BCA=18.6% CAB=14.8% CBA=14.9%
OrderBy(Guid)    ABC=16.5% ACB=16.8% BAC=16.6% BCA=16.7% CAB=16.7% CBA=16.7%
random comparer  ABC=29.6% ACB=14.8% BAC=14.9% BCA=7.4% CAB=14.8% CBA=18.5%
Random.Shuffle   ABC=16.7% ACB=16.6% BAC=16.7% BCA=16.7% CAB=16.7% CBA=16.7%

Cevap: hiçbiri. İlk önerideki tek fark j'nin bütün array'den seçilmesi ve bu bias'ın sebebi aritmetik: 3 adımın her birinde 3 seçenek, toplam 27 eşit olasılıklı yol; 27, 6 permütasyona eşit bölünmez, bazı sıralamalar 4, bazıları 5 yoldan gelir (4/27 = yüzde 14,8, 5/27 = yüzde 18,5). Rastgele cevap veren comparer daha da kötü: ABC yüzde 29,6, BCA yüzde 7,4. Sıralama algoritması karşılaştırmaların tutarlı olduğunu varsayar; serinin 9. yazısında gördüğümüz gibi tutarsız bir comparer hata vermeden yanlış sonuç üretir. Burada "yanlış sonuç" bias'ın kendisi.

OrderBy(_ => Guid.NewGuid()) bu ölçümde düzgün dağılıyor; her element'e rastgele bir key verip sıralamak doğru bir yöntem. Yine de iki sorunu var: maliyeti O(n log n) ve her element için bir key ayırıyor; ayrıca Guid.NewGuid'in dokümanı benzersizlik vaat ediyor, istatistiksel bir dağılım vaat etmiyor. .NET 8 ile gelen Random.Shuffle runtime kaynağına göre Fisher–Yates'in baştan sona yürüyen versiyonu: her i için [i, n) aralığından bir index seçiyor.

100.000 int'i karıştırmanın maliyeti; mutlak süreler makineye bağlı, oranlara bak:

| Method          | N      | Mean        | Ratio | Allocated |
|---------------- |------- |------------:|------:|----------:|
| FisherYatesOurs | 100000 |    475.0 us |  1.00 |         - |
| RandomShuffle   | 100000 |    482.2 us |  1.02 |         - |
| OrderByGuid     | 100000 | 25,942.6 us | 54.63 | 2803943 B |

Kendi Fisher–Yates'imiz ile Random.Shuffle aynı; ikisi de yerinde çalışıyor ve hiç allocation yapmıyor. OrderBy(Guid) 55 kat yavaş ve 2,8 MB ayırıyor. Production'da Random.Shared.Shuffle yeterli.

GetItems ve Akıştan Örnek Almak

.NET 8 ile Random.Shuffle'ın yanında Random.GetItems de geldi: bir listeden istenen sayıda element seçer. Runtime kaynağına göre GetItems her pozisyonu bağımsız seçiyor, yani aynı element birden fazla kez gelebilir (with replacement). "10 kitaptan 3 farklısını seç" için doğru araç GetItems değil; bir kopyayı karıştırıp ilk 3'ü almak ya da Fisher–Yates'i yalnız 3 adım çalıştırmak.

Peki seçeceğin kaynak array değil de bir akışsa? 5 milyon satırlık bir log dosyasından 5 satır örnek almak istiyorsun, dosyayı bir kez okuyabiliyorsun ve kaç satır olduğunu baştan bilmiyorsun. Reservoir sampling bunu çözer; aşağıdaki versiyon Vitter'in 1985 tarihli makalesinde Algorithm R adıyla geçer:

// Algorithm R: ilk k'yı tut; i'nci item (0'dan başlayarak) k / (i + 1) olasılıkla rastgele bir slotun yerine geçer
public static T[] Sample<T>(IEnumerable<T> source, int k, Random random)
{
    ArgumentOutOfRangeException.ThrowIfLessThan(k, 1);
    T[] reservoir = new T[k];
    long seen = 0;
    foreach (T item in source)
    {
        if (seen < k)
        {
            reservoir[seen] = item;
        }
        else
        {
            long j = random.NextInt64(seen + 1);
            if (j < k) reservoir[j] = item;
        }

        seen++;
    }

    return seen >= k ? reservoir : reservoir[..(int)seen];
}

sample: line 33162 | line 1452813 | line 2891061 | line 582690 | line 3648131

Bellek O(k), süre O(n) ve her satırın örnekte olma olasılığı k/n; tümevarımla gösterilir ve test 10 elemanlı bir akıştan 30.000 kez 3 örnek alıp her elemanın yaklaşık 9.000 kez seçildiğini doğruluyor. IEnumerable<T> ve yield return ile akışın hiçbir zaman belleğe alınmaması C# Koleksiyonlar serisinin "C# Collection Interface'leri: IEnumerable, ICollection, IList ve yield return" yazısındaki konu.

Ağırlıklı Seçim: Günün Kitabı

Ana sayfadaki "günün kitabı" eşit olasılıkla değil, kampanya önceliğine göre seçilsin: Dune yüzde 50, Emma yüzde 30, Middlemarch yüzde 15, The Hobbit yüzde 5. İlk yol, ağırlıkların kümülatif toplamını tutup [0, toplam) aralığında rastgele bir sayının hangi dilime düştüğünü binary search ile bulmak:

public T Pick(Random random)
{
    double r = random.NextDouble() * _cumulative[^1];
    int index = Array.BinarySearch(_cumulative, r);
    index = index < 0 ? ~index : index + 1; // r'den büyük ilk kümülatif değer
    return _items[Math.Min(index, _items.Length - 1)];
}

Bu, serinin 7. yazısındaki prefix sum ile 10. yazısındaki upper bound'un birleşimi: kurulum O(n), seçim O(log n). Array.BinarySearch bulamadığında dönen ~index doğrudan istediğimiz pozisyon. Seçim sayısı çok büyükse Walker'ın alias method'u, Vose'un 1991 tarihli kurulumuyla, her seçimi O(1)'e indirir: n sütunluk bir tablo kurar, her sütunu en fazla iki element'e böler; seçimde bir sütun ve bir yazı-tura atılır.

Dune         weight 50%  cumulative  50.1%  alias  50.0%
Emma         weight 30%  cumulative  29.9%  alias  30.0%
Middlemarch  weight 15%  cumulative  15.1%  alias  15.0%
The Hobbit   weight  5%  cumulative   5.0%  alias   5.0%

100.000 günde iki yöntem de ağırlıklara uyuyor. Alias tablosu ağırlıklar her değiştiğinde yeniden kurulur; birkaç düzine kampanya için kümülatif dizi yeterli ve daha kolay okunur.

Deterministik Rastgelelik: Yüzde 10 Rollout

Yeni checkout sayfası kullanıcıların yüzde 10'una açılacak. Her istekte Random.Shared.Next(100) < 10 demek yanlış: aynı kullanıcı bir istekte yeni sayfayı, diğerinde eskisini görür. Atama kullanıcıya sabit, sunucudan ve process'ten bağımsız olmalı. Rastgele görünen ama deterministik olan bir şey gerekiyor: hash.

// Deterministik bucket: aynı flag ve kullanıcı her sunucuda ve her çalıştırmada aynı bucket'a düşer
public static int Bucket(string flag, string userId)
{
    ulong hash = XxHash3.HashToUInt64(Encoding.UTF8.GetBytes($"{flag}:{userId}"));
    return (int)(hash % 100);
}

public static bool IsEnabled(string flag, string userId, int percentage) => Bucket(flag, userId) < percentage;

Demoyu iki kez, iki ayrı process olarak çalıştırdım. İkisinin de çıktısı:

user-42 new-checkout bucket: 50
user-42 dark-mode bucket:    95
new-checkout at 10%: 10,048 of 100,000 users; also in dark-mode at 10%: 1,049

Tek fark son satırdaydı: birinci çalıştırmada "user-42".GetHashCode() −1040352849, ikincisinde 1759377789. Serinin 6. yazısında gördüğümüz randomized string hashing yüzünden GetHashCode bucket'lama için kullanılamaz; kullanıcı her deploy'da başka gruba düşer. Üç ayrıntı daha önemli. Flag adını hash'e katmak, flag'leri birbirinden bağımsız yapıyor: new-checkout'taki 10.048 kişinin yüzde 10'u (1.049) dark-mode'da da var; flag adı olmasaydı aynı yüzde 10 her deneyde olurdu. Yüzdeyi 10'dan 20'ye çıkarmak ilk yüzde 10'u korur, çünkü bucket < 10 olan herkes bucket < 20'dir. Ve 2⁶⁴ 100'e tam bölünmediği için mod işleminin bias'ı var ama 10⁻¹⁷ mertebesinde. Feature flag'lerin kod tarafı Çözüm Desenleri serisinin "Feature Flag'leri Kodda Tasarlamak: Toggle Türleri, Microsoft.FeatureManagement ve Flag Borcu" yazısında, A/B testinin istatistiği Product Management serisinin "Deneyle Karar Vermek: A/B Test, Feature Flag ve İstatistiksel Tuzaklar" yazısında.

Seed, Thread'ler ve Güvenlik

1,000 x new Random() in a loop: 1000 distinct first values
seeded Random shared by threads: 85 of 10,000,000 calls returned 0; afterwards 0 of 1,000
Random.Shared from threads: 0 zeros
Random(12345) token: 632b808fafc222ca, again: 632b808fafc222ca
RandomNumberGenerator token length: 32 hex chars

İlk satır eski bir uyarının güncel halini gösteriyor. Random dokümanına göre .NET Framework'te parametresiz constructor seed'i sistem saatinden alıyordu ve döngüde art arda oluşturulan nesneler aynı diziyi üretebiliyordu; .NET 10'da 1.000 nesnenin ilk değerlerinin hepsi farklı. Yine de döngüde nesne oluşturmak gereksiz allocation; tek bir nesne ya da Random.Shared yeterli.

İkinci satır asıl tehlike. Seed verilmiş tek bir Random'u Parallel.For'dan çağırdım; 10 milyon çağrının 85'i 0 döndü. Aynı deneyi ayrı bir küçük programda 50 milyon çağrıyla tekrarladığımda çağrıların büyük çoğunluğu 0 döndü ve nesne sonrasında tek thread'den çağrılınca da yalnız 0 üretmeye devam etti: iç state kalıcı olarak bozuldu. Doküman bunu açıkça söylüyor: Random thread-safe değil. Thread'ler arası paylaşım için Random.Shared var.

Son iki satır güvenlik. Aynı seed'le oluşturulan iki Random aynı "token"ı üretiyor; seed'i ya da birkaç çıktıyı bilen biri sonrakileri hesaplayabilir. Şifre sıfırlama linki, API key, oturum token'ı için System.Security.Cryptography.RandomNumberGenerator kullanılır (GetHexString, GetInt32, Fill); ayrıntısı Geliştirici için Kriptografi serisinde. Seed'in meşru kullanımı testler: new Random(27) bu yazıdaki testleri tekrarlanabilir yapıyor. Ama dokümana göre aynı seed farklı .NET sürümlerinde farklı dizi üretebilir; seed'li bir diziyi veriye kaydetme ya da sürümler arası sabit bir sonuca bağlama. Rollout'ta Random değil hash kullanmamızın bir sebebi de bu.

Üretimde Dikkat

Hash'i ve formatı sabitle. Rollout bucket'ı "{flag}:{userId}" string'inin XxHash3'ü; bu formatı değiştirmek ya da hash algoritmasını güncellemek bütün kullanıcıları yeniden dağıtır. Bunu bir sözleşme gibi belgele ve testle sabitle.

Rastgeleliği test edilebilir yap. Random'u method'a parametre olarak ver ya da constructor'dan inject et; testte seed'li bir nesne, production'da Random.Shared. Dağılımı tek bir çıktıyla değil, binlerce denemenin sayımıyla test et.

Örneklemin neyi temsil ettiğini bil. Reservoir sampling akıştaki her satıra eşit şans verir; hata satırlarını özellikle görmek istiyorsan ağırlıklı ya da katmanlı örnekleme gerekir.

Sık Düşülen Tuzaklar

j'yi bütün array'den seçmek. Fisher–Yates'e benzeyen ama n^n yol üreten döngü bias'lıdır; elle yazmak yerine Random.Shuffle kullan.

Rastgele comparer ile sıralamak. Sıralama tutarlı karşılaştırma bekler; sonuç en iyi ihtimalle bias'lıdır.

Bir Random nesnesini thread'ler arasında paylaşmak. Ölçümdeki gibi iç state bozulur ve nesne 0 üretmeye başlar. Random.Shared kullan.

Güvenlik token'ı için Random kullanmak. Tahmin edilebilir; RandomNumberGenerator kullan.

Feature flag atamasını her istekte rastgele yapmak ya da GetHashCode ile yapmak. Kullanıcı gruplar arasında gidip gelir; deterministik ve process'ten bağımsız bir hash kullan.

Seri Kapanışı: Uygulamada Sık Yazılan Yapılar

Serinin 22. yazısındaki karar tablosu klasik müfredatı kapsıyordu. Son beş yazı, ürün özelliği yazarken karşına çıkan beş sinyali ekledi:

Bu yapıların ortak noktası, hepsinin önceki yazılardaki temel yapıların birleşimi olması: LRU hash table ile linked list'i, Aho-Corasick trie ile KMP'yi (Knuth–Morris–Pratt string arama algoritması), alias method prefix sum ile binary search'ü birleştiriyor. Temelleri bilmek, yeni bir yapıyı ilk kez gördüğünde onu parçalarına ayırabilmek demek.

Küçük Bir Deneme

★☆☆ FisherYates'i yalnız ilk k adımı çalıştıracak şekilde değiştirip "n kitaptan k farklısını seç" method'unu yaz. 10 kitaptan 3 seçimini 100.000 kez yap ve her kitabın yaklaşık yüzde 30 seçildiğini doğrula.

★★☆ Rollout'a sticky bir A/B ataması ekle: Variant(flag, userId, ["control", "a", "b"], [50, 25, 25]). Ağırlıkları kümülatif bir array'de tut ve bucket'ı 0–99 aralığında kullan. Bir varyantın oranını değiştirdiğinde kaç kullanıcının grubu değişiyor?

★★★ Ağırlıklı reservoir sampling yaz: her satırın bir ağırlığı olsun (ör. hata satırları 10, diğerleri 1). Efraimidis ve Spirakis'in yönteminde her item için u^(1/w) key'i hesaplanır ve en büyük k key, serinin 13. yazısındaki gibi k elemanlı bir min-heap'te tutulur. Hata satırlarının örnekteki payını ölç.

Bu yazıyla "Algoritmalar ve Data Structures" serisi tamamlanıyor. Array'den başlayıp hash table'a, sorting'den tree'lere, graph'lardan dynamic programming'e ve oradan LRU cache'e, string aramaya, aralıklara, probabilistic yapılara ve rastgeleliğe kadar her yapıyı kendimiz yazdık, BCL'deki (.NET ile gelen temel class kütüphanesi) karşılığıyla ölçtük ve Bookstore'un gerçek problemlerine uyguladık. Bir sonraki adım senin projen: bir sonraki yavaş endpoint'te ya da "bunu nasıl tutsak" sorusunda, bu iki karar tablosunun hangi satırının karşına çıktığını ara.