Czy używanie algorytmu Random i OrderBy jest dobrym algorytmem losowym?

Przeczytałem artykuł o różnych algorytmach tasowania w Coding Horror . Widziałem, że gdzieś ludzie zrobili to, aby przetasować listę:

var r = new Random();
var shuffled = ordered.OrderBy(x => r.Next());

Czy to dobry algorytm odtwarzania losowego? Jak to dokładnie działa? Czy jest to akceptowalny sposób na zrobienie tego?

Nie jest to sposób tasowania, który mi się podoba, głównie ze względu na to, że jest to O (n log n) bez dobrego powodu, kiedy łatwo jest zaimplementować tasowanie O (n). Kod w pytaniu „działa” w zasadzie nadając każdemu elementowi losową (miejmy nadzieję unikalną!) Liczbę, a następnie porządkując elementy według tego numeru.

Wolę wariant Durstenfield tasowania Fishera-Yatesa, który zamienia elementy.

Implementacja prostej Shufflemetody rozszerzenia polegałaby w zasadzie na wywołaniu ToListlub ToArrayna wejściu, a następnie przy użyciu istniejącej implementacji Fisher-Yates. (Podaj Randomjako parametr, aby życie było ogólnie przyjemniejsze.) Istnieje wiele implementacji w okolicy ... Prawdopodobnie mam gdzieś jedną w odpowiedzi.

Zaletą takiej metody rozszerzającej jest to, że czytelnik będzie wtedy bardzo jasno wiedział, co tak naprawdę próbujesz zrobić.

EDYCJA: Oto prosta implementacja (bez sprawdzania błędów!):

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length-1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        T tmp = elements[i];
        elements[i] = elements[swapIndex];
        elements[swapIndex] = tmp;
    }
    // Lazily yield (avoiding aliasing issues etc)
    foreach (T element in elements)
    {
        yield return element;
    }
}

EDYCJA: Poniższe komentarze na temat wydajności przypomniały mi, że tak naprawdę możemy zwrócić elementy podczas ich tasowania:

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        // ... except we don't really need to swap it fully, as we can
        // return it immediately, and afterwards it's irrelevant.
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

Teraz wykona tylko tyle pracy, ile potrzeba.

Zauważ, że w obu przypadkach musisz uważać na wystąpienie, Randomktórego używasz jako:

• Utworzenie dwóch wystąpień Randommniej więcej w tym samym czasie da tę samą sekwencję liczb losowych (w przypadku użycia w ten sam sposób)
• Random nie jest bezpieczny dla wątków.

Mam artykuł, wRandom którym bardziej szczegółowo omawiam te problemy i podaje rozwiązania.

Jest to oparte na Jon Skeet za odpowiedź .

W tej odpowiedzi tablica jest tasowana, a następnie zwracana za pomocą yield. Wynik netto jest taki, że tablica jest przechowywana w pamięci przez czas trwania foreach, a także obiekty niezbędne do iteracji, a jednak koszt jest na początku - wydajność jest w zasadzie pustą pętlą.

Ten algorytm jest często używany w grach, w których wybierane są pierwsze trzy elementy, a pozostałe będą potrzebne później, jeśli w ogóle. Moja sugestia dotyczy yieldnumerów, gdy tylko zostaną zamienione. Zmniejszy to koszt uruchomienia, zachowując koszt iteracji na poziomie O (1) (w zasadzie 5 operacji na iterację). Całkowity koszt pozostałby taki sam, ale samo tasowanie byłoby szybsze. W przypadkach, w których jest to wywołane, ponieważ collection.Shuffle().ToArray()teoretycznie nie będzie to miało znaczenia, ale we wspomnianych powyżej przypadkach użycia przyspieszy uruchomienie. Dzięki temu algorytm będzie przydatny w przypadkach, w których potrzebujesz tylko kilku unikalnych elementów. Na przykład, jeśli chcesz wyciągnąć trzy karty z talii 52, możesz sprawdzić deck.Shuffle().Take(3)i tylko trzy zamiany będą miały miejsce (chociaż cała tablica musiałaby zostać skopiowana jako pierwsza).

public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, Random rng)
{
    T[] elements = source.ToArray();
    // Note i > 0 to avoid final pointless iteration
    for (int i = elements.Length - 1; i > 0; i--)
    {
        // Swap element "i" with a random earlier element it (or itself)
        int swapIndex = rng.Next(i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
        // we don't actually perform the swap, we can forget about the
        // swapped element because we already returned it.
    }

    // there is one item remaining that was not returned - we return it now
    yield return elements[0]; 
}

Począwszy od tego cytatu ze Skeeta:

Nie jest to sposób tasowania, który mi się podoba, głównie ze względu na to, że jest to O (n log n) bez dobrego powodu, kiedy łatwo jest zaimplementować tasowanie O (n). Kod w pytaniu „działa” w zasadzie nadając każdemu elementowi losową ( miejmy nadzieję unikalną! ) Liczbę, a następnie porządkując elementy według tego numeru.

Pójdę dalej, wyjaśniając powód, miejmy nadzieję, wyjątkowego!

Teraz z Enumerable.OrderBy :

Ta metoda wykonuje stabilne sortowanie; to znaczy, jeśli klucze dwóch elementów są równe, kolejność elementów zostaje zachowana

To jest bardzo ważne! Co się stanie, jeśli dwa elementy „otrzymają” tę samą liczbę losową? Zdarza się, że pozostają w tej samej kolejności, w jakiej znajdują się w tablicy. Jaka jest więc możliwość, że tak się stanie? Trudno jest dokładnie obliczyć, ale jest Problem Urodzinowy, który jest właśnie tym problemem.

Czy to jest prawdziwe? Czy to prawda?

Jak zawsze, jeśli masz wątpliwości, napisz kilka linii programu: http://pastebin.com/5CDnUxPG

Ten mały blok kodu tasuje tablicę 3 elementów określoną liczbę razy, używając algorytmu Fishera-Yatesa wykonanego wstecz, algorytmu Fishera-Yatesa wykonanego do przodu (na stronie wiki są dwa algorytmy pseudokodu ... wyników, ale jeden jest wykonywany od pierwszego do ostatniego elementu, a drugi od ostatniego do pierwszego elementu), naiwny zły algorytm http://blog.codinghorror.com/the-danger-of-naivete/ i przy użyciu .OrderBy(x => r.Next())i .OrderBy(x => r.Next(someValue)).

Teraz Random.Next jest

32-bitowa liczba całkowita ze znakiem, która jest większa lub równa 0 i mniejsza niż MaxValue.

więc jest to odpowiednik

OrderBy(x => r.Next(int.MaxValue))

Aby sprawdzić, czy ten problem istnieje, możemy powiększyć tablicę (coś bardzo wolnego) lub po prostu zmniejszyć maksymalną wartość generatora liczb losowych ( int.MaxValuenie jest to „specjalna” liczba… To po prostu bardzo duża liczba). Ostatecznie, jeśli algorytm nie jest obciążony stabilnością wartości OrderBy, to każdy zakres wartości powinien dać ten sam wynik.

Następnie program testuje niektóre wartości z zakresu 1 ... 4096. Patrząc na wynik, jest całkiem jasne, że dla niskich wartości (<128) algorytm jest bardzo obciążony (4-8%). Przy 3 wartościach potrzebujesz przynajmniej r.Next(1024). Jeśli powiększysz tablicę (4 lub 5), to nawet r.Next(1024)nie wystarczy. Nie jestem ekspertem w tasowaniu i matematyce, ale myślę, że na każdy dodatkowy bit długości tablicy potrzebne są 2 dodatkowe bity o maksymalnej wartości (ponieważ paradoks urodzin jest powiązany z sqrt (numvalues)), więc że jeśli maksymalna wartość to 2 ^ 31, powiem, że powinieneś móc sortować tablice do 2 ^ 12/2 ^ 13 bitów (4096-8192 elementów)

Prawdopodobnie jest to w porządku dla większości celów i prawie zawsze generuje prawdziwie losowy rozkład (z wyjątkiem sytuacji, gdy Random.Next () generuje dwie identyczne losowe liczby całkowite).

Działa poprzez przypisanie każdemu elementowi serii losowej liczby całkowitej, a następnie uporządkowanie sekwencji według tych liczb całkowitych.

Jest to całkowicie akceptowalne dla 99,9% aplikacji (chyba że absolutnie musisz obsługiwać powyższy przypadek skrajny). Ponadto sprzeciw skeeta co do jego środowiska wykonawczego jest ważny, więc jeśli tasujesz długą listę, możesz nie chcieć jej używać.

Zdarzało się to już wielokrotnie. Wyszukaj Fisher-Yates w StackOverflow.

Oto przykładowy kod C #, który napisałem dla tego algorytmu. Jeśli wolisz, możesz sparametryzować go na innym typie.

static public class FisherYates
{
        //      Based on Java code from wikipedia:
        //      http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
        static public void Shuffle(int[] deck)
        {
                Random r = new Random();
                for (int n = deck.Length - 1; n > 0; --n)
                {
                        int k = r.Next(n+1);
                        int temp = deck[n];
                        deck[n] = deck[k];
                        deck[k] = temp;
                }
        }
}

Wygląda na dobry algorytm tasowania, jeśli nie martwisz się zbytnio o wydajność. Jedynym problemem, na który zwróciłbym uwagę, jest to, że jego zachowanie nie jest kontrolowane, więc możesz mieć trudności z jego przetestowaniem.

Jedną z możliwych opcji jest przekazanie ziarna jako parametru do generatora liczb losowych (lub generatora losowego jako parametru), dzięki czemu można mieć większą kontrolę i łatwiej go przetestować.

Uznałem, że odpowiedź Jona Skeeta jest całkowicie satysfakcjonująca, ale robo-skaner mojego klienta zgłosi każdy przypadek Randomjako lukę w zabezpieczeniach. Więc zamieniłem to na System.Security.Cryptography.RNGCryptoServiceProvider. Jako bonus naprawia wspomniany problem z bezpieczeństwem wątków. Z drugiej strony RNGCryptoServiceProviderzostał zmierzony jako 300x wolniej niż przy użyciuRandom .

Stosowanie:

using (var rng = new RNGCryptoServiceProvider())
{
    var data = new byte[4];
    yourCollection = yourCollection.Shuffle(rng, data);
}

Metoda:

/// <summary>
/// Shuffles the elements of a sequence randomly.
/// </summary>
/// <param name="source">A sequence of values to shuffle.</param>
/// <param name="rng">An instance of a random number generator.</param>
/// <param name="data">A placeholder to generate random bytes into.</param>
/// <returns>A sequence whose elements are shuffled randomly.</returns>
public static IEnumerable<T> Shuffle<T>(this IEnumerable<T> source, RNGCryptoServiceProvider rng, byte[] data)
{
    var elements = source.ToArray();
    for (int i = elements.Length - 1; i >= 0; i--)
    {
        rng.GetBytes(data);
        var swapIndex = BitConverter.ToUInt32(data, 0) % (i + 1);
        yield return elements[swapIndex];
        elements[swapIndex] = elements[i];
    }
}

Szukasz algorytmu? Możesz użyć mojej ShuffleListklasy:

class ShuffleList<T> : List<T>
{
    public void Shuffle()
    {
        Random random = new Random();
        for (int count = Count; count > 0; count--)
        {
            int i = random.Next(count);
            Add(this[i]);
            RemoveAt(i);
        }
    }
}

Następnie użyj tego w ten sposób:

ShuffleList<int> list = new ShuffleList<int>();
// Add elements to your list.
list.Shuffle();

Jak to działa?

Weźmy początkową posortowaną listę 5 pierwszych liczb całkowitych: { 0, 1, 2, 3, 4 } .

Metoda rozpoczyna się od policzenia liczby elementów i wywołania go count. Następnie, wraz ze countzmniejszaniem się na każdym kroku, przyjmuje losową liczbę od 0docount i przenosi ją na koniec listy.

W poniższym przykładzie krok po kroku elementy, które można przenieść, są oznaczone kursywą , a wybrany element jest pogrubiony :

0 1 2 3 4
0 1 2 3 4
0 1 2 4 3
0 1 2 4 3
1 2 4 3 0
1 2 4 3 0
1 2 3 0 4
1 2 3 0 4
2 3 0 4 1
2 3 0 4 1
3 0 4 1 2

Ten algorytm tasuje, generując nową losową wartość dla każdej wartości na liście, a następnie porządkując listę według tych losowych wartości. Potraktuj to jako dodanie nowej kolumny do tabeli w pamięci, a następnie wypełnienie jej identyfikatorami GUID, a następnie sortowanie według tej kolumny. Wydaje mi się, że to skuteczny sposób (zwłaszcza z cukrem lambda!)

Trochę niepowiązane, ale tutaj jest interesująca metoda (która mimo że jest naprawdę przesada, została NAPRAWDĘ zaimplementowana) na prawdziwie losowe generowanie rzutów kostką!

Dice-O-Matic

Powodem, dla którego to piszę, jest to, że przedstawia kilka interesujących uwag na temat tego, jak jego użytkownicy zareagowali na pomysł użycia algorytmów do tasowania rzeczywistych kostek. Oczywiście w prawdziwym świecie takie rozwiązanie jest tylko dla naprawdę skrajnych krańców spektrum, gdzie losowość ma tak duży wpływ i być może wpływa na pieniądze;).

Powiedziałbym, że wiele odpowiedzi, takich jak „Ten algorytm tasuje, generując nową losową wartość dla każdej wartości na liście, a następnie porządkując listę według tych losowych wartości”, może być bardzo błędnych!

Myślę, że to NIE PRZYPISUJE losowej wartości do każdego elementu kolekcji źródłowej. Zamiast tego może istnieć algorytm sortowania działający jak Quicksort, który wywoływałby funkcję porównującą około n log n razy. Niektóre algorytmy sortowania naprawdę oczekują, że funkcja porównująca będzie stabilna i zawsze zwraca ten sam wynik!

Czy nie może być tak, że IEnumerableSorter wywołuje funkcję porównującą dla każdego kroku algorytmu np. Quicksort i za każdym razem wywołuje funkcję x => r.Next()dla obu parametrów bez ich buforowania!

W takim przypadku możesz naprawdę zepsuć algorytm sortowania i sprawić, że będzie znacznie gorszy niż oczekiwania, na których algorytm został zbudowany. Oczywiście ostatecznie ustabilizuje się i coś zwróci.

Mogę to sprawdzić później, umieszczając wyjście debugowania wewnątrz nowej funkcji „Dalej”, więc zobacz, co się stanie. W Reflector nie mogłem od razu dowiedzieć się, jak to działa.

Czas uruchomienia do uruchomienia na kodzie z wyczyszczeniem wszystkich wątków i buforowaniem każdego nowego testu,

Pierwszy nieudany kod. Działa na LINQPad. Jeśli wykonasz, aby przetestować ten kod.

Stopwatch st = new Stopwatch();
st.Start();
var r = new Random();
List<string[]> list = new List<string[]>();
list.Add(new String[] {"1","X"});
list.Add(new String[] {"2","A"});
list.Add(new String[] {"3","B"});
list.Add(new String[] {"4","C"});
list.Add(new String[] {"5","D"});
list.Add(new String[] {"6","E"});

//list.OrderBy (l => r.Next()).Dump();
list.OrderBy (l => Guid.NewGuid()).Dump();
st.Stop();
Console.WriteLine(st.Elapsed.TotalMilliseconds);

list.OrderBy (x => r.Next ()) zajmuje 38,6528 ms

list.OrderBy (x => Guid.NewGuid ()) wykorzystuje 36,7634 ms (zalecane z MSDN).

po raz drugi oba używają w tym samym czasie.

EDYCJA: KOD TESTOWY na Intel Core i7 4@2,1GHz, 8 GB DDR3 @ 1600, HDD SATA 5200 obr / min z [Dane: www.dropbox.com/s/pbtmh5s9lw285kp/data]

using System;
using System.Runtime;
using System.Diagnostics;
using System.IO;
using System.Collections.Generic;
using System.Collections;
using System.Linq;
using System.Threading;

namespace Algorithm
{
    class Program
    {
        public static void Main(string[] args)
        {
            try {
                int i = 0;
                int limit = 10;
                var result = GetTestRandomSort(limit);
                foreach (var element in result) {
                    Console.WriteLine();
                    Console.WriteLine("time {0}: {1} ms", ++i, element);
                }
            } catch (Exception e) {
                Console.WriteLine(e.Message);
            } finally {
                Console.Write("Press any key to continue . . . ");
                Console.ReadKey(true);
            }
        }

        public static IEnumerable<double> GetTestRandomSort(int limit)
        {
            for (int i = 0; i < 5; i++) {
                string path = null, temp = null;
                Stopwatch st = null;
                StreamReader sr = null;
                int? count = null;
                List<string> list = null;
                Random r = null;

                GC.Collect();
                GC.WaitForPendingFinalizers();
                Thread.Sleep(5000);

                st = Stopwatch.StartNew();
                #region Import Input Data
                path = Environment.CurrentDirectory + "\\data";
                list = new List<string>();
                sr = new StreamReader(path);
                count = 0;
                while (count < limit && (temp = sr.ReadLine()) != null) {
//                  Console.WriteLine(temp);
                    list.Add(temp);
                    count++;
                }
                sr.Close();
                #endregion

//              Console.WriteLine("--------------Random--------------");
//              #region Sort by Random with OrderBy(random.Next())
//              r = new Random();
//              list = list.OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with OrderBy(Guid)
//              list = list.OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with Parallel and OrderBy(random.Next())
//              r = new Random();
//              list = list.AsParallel().OrderBy(l => r.Next()).ToList();
//              #endregion

//              #region Sort by Random with Parallel OrderBy(Guid)
//              list = list.AsParallel().OrderBy(l => Guid.NewGuid()).ToList();
//              #endregion

//              #region Sort by Random with User-Defined Shuffle Method
//              r = new Random();
//              list = list.Shuffle(r).ToList();
//              #endregion

//              #region Sort by Random with Parallel User-Defined Shuffle Method
//              r = new Random();
//              list = list.AsParallel().Shuffle(r).ToList();
//              #endregion

                // Result
//              
                st.Stop();
                yield return st.Elapsed.TotalMilliseconds;
                foreach (var element in list) {
                Console.WriteLine(element);
            }
            }

        }
    }
}

Opis wyniku: https://www.dropbox.com/s/9dw9wl259dfs04g/ResultDescription.PNG
Statystyka wyników: https://www.dropbox.com/s/ewq5ybtsvesme4d/ResultStat.PNG

Wniosek:
Załóżmy, że LINQ OrderBy (r.Next ()) i OrderBy (Guid.NewGuid ()) nie są gorsze niż metoda losowania zdefiniowana przez użytkownika w First Solution.

Odpowiedź: Są sprzecznością.