Mieszanie elementów kolekcji w C#

Losowość i chaos

Na początku, według Mitologii, był chaos. Człowiek nauczył się żyć z nim w symbiozie, wykorzystując go nawet do swoich celów. Nauczył się wprawdzie przewidywać pogodę w krótkim okresie, ale przewidywanie na miesiąc do przodu wydaje się być chaotyczne. Mówi się także o efekcie motyla, który jednym machnięciem skrzydłami potrafi w długim okresie wpłynąć na cała planetę. Chaos, występujący pod przykrywką losowości, wykorzystuje się w grach. Rzut monetą przed meczem, rzut kości w grze planszowej - wszystko to wydaje się nieuporządkowane i przypadkowe. Czy gra byłaby przyjemna, gdyby każdy rzucał to co chciał? Czy ludzie umawialiby się na grę w pokera wiedząc, że rozdający będzie zawsze znał dokładny układ kart? A w informatyce? Przecież tam wszystko wykonywane jest przez zaprogramowaną maszynę więc powinno być deterministyczne. Nic bardziej mylnego. Każdy szanujący się język programowania pozwala wygenerować losową wartość. A ta losowa wartość może być wykorzystywana w bardzo wielu miejscach. Przypuśćmy, że chcemy przetestować naszą aplikację pod kątem wydajności. Co robimy? Generujemy milion losowych rekordów. Co robimy, aby sztuczna inteligencja w grach nie zachowywała się za każdym razem tak samo? Wprowadzamy element losowości, chaosu. A gdybyśmy chcieli, aby teren na którym będziemy walczyć w jakiejś grze był za każdym razem inny? Znów wykorzystujemy liczby losowe (przykłady można znaleźć we wpisach Generowanie losowego terenu 2D oraz Generowanie terenu 3D). A gdybyśmy zechcieli przejąć kopię bazy danych od klienta zachowując jednocześnie prywatność użytkowników w niej zapisanych? Możemy wykonać skrypt, który wymiesza dane w taki sposób, aby stały się bezużyteczne. Mieszanie elementów w bazie najlepiej zrealizować odpowiednią procedurą składowaną. Mieszanie elementów kolekcji w .NET również można sobie napisać i to też zamierzam uczynić.

LINQ i rozszerzenia kolekcji

Decyzja o napisaniu rozszerzenia LINQ nie była przypadkowa, losowa czy też chaotyczna. Po pierwsze pojawiła się potrzeba, a po drugie, uważam LINQ za jeden z najlepszych elementów składowych platformy .NET. Tak oto z chaosu zrodziła się następująca metoda:

static IEnumerable<T> Shuffle<T>(this IEnumerable<T> collection)
{
    T[] clone = collection.ToArray();
    int cloneLength = clone.Length;
    var randomGenerator = new RNGCryptoServiceProvider();
    var shuffleArray = new byte[clone.Length + 3];
    randomGenerator.GetBytes(shuffleArray);
    for (int i = 0; i < cloneLength - 1; i++)
    {
        T temp = clone[i];
        uint picked = BitConverter.ToUInt32(shuffleArray, i) % (uint)(cloneLength - i);
        clone[i] = clone[picked + i];
        clone[picked + i] = temp;
    }
    return clone;
}

Algorytm jest krótki więc wyjaśnienie też takie będzie. Najpierw zawartość kolekcji kopiowana jest do tablicy - oczywiście dzięki wbudowanemu rozszerzeniu LINQ. Algorytm wykorzystuje indeksowanie, dlatego tablica wydaje się najrozsądniejszą strukturą. Zaskakująca może być trzecia i czwarta linijka. To tam pojawia się losowość. Istnieje wprawdzie prostsza i bardziej znana klasa Random, ale postanowiłem użyć innej, RNGCryptoServiceProvider, uznawaną za generującą bardziej losowe wartości. Można wprawdzie losować liczbę całkowitą dla każdego z elementów tablicy, ale zastosowałam pewien trik. Normalnie potrzebowalibyśmy N*4 losowych bajtów - mi wystarczy N+3. Wiemy, że uint to 4 bajty i zasadne wydaje się pobieranie bajtów 0-3 do pierwszej wartości losowej, 4-7 dla drugiej, 8-11 dla trzeciej i tak dalej. Ale, skoro wartości są prawdziwie losowe, możemy nieco zoptymalizować algorytm. Pierwsza wartość powstanie z pierwszych czterech bajtów, 0-3, tak jak wcześniej. Druga, i tu zmiana, to będą bajty 1-4, trzecia 2-5, czwarta 3-6. Mówiąc wprost, kolejne wartości zachodzą na siebie.

Czas na algorytm właściwy. Polega on na pobieraniu kolejnych elementów z kolekcji w sposób losowy. I tak, pierwszym elementem pomieszanej tablicy będzie losowy element tablicy wejściowej. Przestawiamy go na początek zamieniając z tym, który na początku się znajdował. I teraz najważniejsze: uznajemy, że pierwszy, losowy element jest nie do rudzenia. Zajmujemy się elementami 1..N-1. Spośród nich wybieramy losowy i przestawiamy na nowy początek, to jest na pozycję pierwszą. Mamy zatem dwa losowo wybrane elementy i tablicę do rozważenia 2..N-1. Czynność powtarzamy aż dojdziemy do końca tablicy.

Algorytm działa w czasie liniowym i zawsze wykonuje N-1 iteracji. LINQ ma jednak taką właściwość, że pozwala łączyć wywołania rozszerzeń w łańcuchy. Gdybyśmy zechcieli wybrać trzy losowe elementy spośród tysiąca wykonalibyśmy 999 iteracji. Jest jednak na to sposób. Popatrzmy na alternatywne rozwiązanie:

static IEnumerable<T> Shuffle<T>(this IEnumerable<T> collection)
{
    T[] clone = collection.ToArray();
    int cloneLength = clone.Length;
    var randomGenerator = new RNGCryptoServiceProvider();
    var shuffleArray = new byte[clone.Length + 3];
    randomGenerator.GetBytes(shuffleArray);
    for (int i = 0; i < cloneLength - 1; i++)
    {
        uint picked = BitConverter.ToUInt32(shuffleArray, i) % (uint)(cloneLength - i);
        yield return clone[picked + i];
        clone[picked + i] = clone[i];
    }
    yield return clone[cloneLength - 1];
}

W tym przypadku, gdy potrzebujemy tylko kilku rekordów (Take(M)), pętla zostanie zakończona przedwcześnie.

Przykłady wywołań

Popatrzmy jeszcze na koniec na jakiś przykład:

//Kier, Karo, Trefl, Pik
var suits = new[] { "\u2665", "\u2666", "\u2663", "\u2660" };
var ranks = new[] { "A", "K", "Q", "J", "10", "9" };

var cards = new string[suits.Length * ranks.Length];
for (int rank = 0; rank < ranks.Length; rank++)
{
    for (int suit = 0; suit < suits.Length; suit++)
    {
        cards[rank * suits.Length + suit] = ranks[rank] + suits[suit];
    }
}

var cardsShuffled = cards.Shuffle();

var articles = new List<string> { "Art1", "Art2", "Art3", "Art4", "Art5" }.Shuffle().Take(3);

Pierwszy przykład pokazuje w jaki sposób można potasować talię kart. Znacznie dłuższy jest kod uzupełniający tablicę niż samo mieszanie, sprowadzone do jednej metody. Drugi przykład pokazuje, jak można na swojej stronie z artykułami wyświetlić trzy losowe - pomieszać i wybrać trzy pierwszeWersja ze słowem kluczowym yield nie musi mieszać całej tablicy - zakończy działanie po trzech iteracjach..

Pisałem na początku o algorytmie mieszania danych w bazie tak, aby stały się bezużyteczne. Wymieszanie rekordów to najczęściej za mało, bo dane w jednym rekordzie mogą stanowić pewną całość. Jako przykład podajmy sobie obiekt zawierający imię, nazwisko i telefon - to, że pomieszamy imiona i nazwiska doprowadzi do tego, że utracimy możliwość rozpoznania osób. Sam telefon będzie jednak prawidłowy i może się okazać przydatny w kontekście bazy (np. baza uczelni zawiera telefony studentów - napastnik może wykorzystać ten numer podając się za pracownika dziekanatu i bez podejrzeń wymusić jakieś działanie studenta). A gdybyśmy tak pomieszali litery w telefonie? Nic prostszego:

var number = string.Concat("0123456789".Shuffle());

To jedno z tych mniej oczywistych wywołań metody mieszającej. Mniej oczywistych, ale przydatnych.

Podsumowanie

Czasami wydaje mi się, że pisanie dużych programów jest jak projektowanie klocków LEGO. Dobrze jest tak zaprojektować klocki, aby dało się je łączyć w dowolny sposób. I tak jak z klocków LEGO powstają całe miasteczka klockowe, tak z programistycznych klocków powstają duże systemy. Tak działa LINQ, i tak, mam nadzieję, wpasuje się do tego ekosystemu klocek mieszający.

Kategoria:C#LINQ