Czy używanie algorytmu losowego i OrderBy jest dobrym algorytmem shuffle?

Jest to oparte na odpowiedzi Jona Skeeta .

W tej odpowiedzi tablica jest tasowana, a następnie zwracana za pomocą yield. Wynikiem jest to, ż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, gdzie trzy pierwsze przedmioty są wybierane, a pozostałe będą potrzebne dopiero później, jeśli w ogóle. Moja propozycja to yield Liczby, gdy tylko zostaną zamienione. Zmniejszy to koszty rozruchu, przy jednoczesnym utrzymaniu kosztów iteracji na poziomie O (1) (zasadniczo 5 operacji na iterację). Całkowity koszt pozostałby taki sam, ale samo tasowanie byłoby szybsze. W przypadkach, gdy jest to nazywane collection.Shuffle().ToArray(), teoretycznie nie będzie to miało znaczenia, ale w wyżej wymienionych przypadkach przyspieszy rozruch. Ponadto algorytm byłby przydatny w przypadkach, w których potrzebujesz tylko kilku unikalnych elementów. Na przykład, jeśli trzeba wyciągnąć trzy karty z talii 52, można wywołać deck.Shuffle().Take(3) i tylko trzy swapy będą miały miejsce (chociaż cała tablica musiałaby być 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]; 
}

Zaczynając od tego cytatu Skeeta:

Nie jest to sposób tasowania, który lubię, głównie ze względu na to, że jest O(n log n) bez dobrego powodu, kiedy łatwo jest zaimplementować O(n) shuffle. Kod w pytaniu "działa" w zasadzie dając losowy (miejmy nadzieję unikalny!) numer do każdego elementu, a następnie uporządkowanie elementów według tej liczby.

Wyjaśnię trochę powód mam nadzieję, że unikalny!

Teraz, Od wyliczyć.OrderBy :

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

Jak zawsze, w razie wątpliwości, napisz kilka linijek programu: http://pastebin.com/5CDnUxPG

Ten mały blok kodu tasuje tablicę 3 elementów pewną liczbę razy używając algorytmu Fisher-Yates wykonanego wstecz, algorytmu Fisher-Yates wykonanego do przodu (na stronie wiki znajdują się dwa pseudo-algorytmy kodu... Dają one równoważne wyniki, ale jeden jest wykonywany od pierwszego do ostatniego element, podczas gdy drugi jest wykonywany od ostatniego do pierwszego elementu), naiwny błędny algorytm http://blog.codinghorror.com/the-danger-of-naivete / i używając .OrderBy(x => r.Next()) i .OrderBy(x => r.Next(someValue)).

Teraz, Losowo.Następna to

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

Jest więc odpowiednikiem

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

Aby sprawdzić, czy ten problem istnieje, możemy powiększyć tablicę (coś bardzo powolnego) lub po prostu zmniejszyć maksymalna wartość generatora liczb losowych (int.MaxValue nie jest liczbą "specjalną"... Jest to po prostu bardzo duża liczba). W końcu, jeśli algorytm nie jest stronniczy ze względu na stableness OrderBy, to każdy zakres wartości powinien dać taki sam wynik.

Program następnie testuje niektóre wartości z zakresu 1...4096. Patrząc na wynik, jest całkiem jasne, że dla niskich wartości (r.Next(1024). Jeśli powiększysz tablicę (4 lub 5), wtedy nawet r.Next(1024) to za mało. Nie jestem ekspertem w tasowaniu i matematyce, ale myślę, że dla każdego dodatkowego bitu długości tablicy potrzebne są 2 dodatkowe bity maksymalnej wartości(ponieważ paradoks urodzinowy jest połączony z sqrt (numvalues)), więc jeśli maksymalna wartość wynosi 2^31, powiem, że powinieneś być w stanie sortować tablice do 2^12/2^13 bitów (4096-8192 elementy)

Jest prawdopodobnie ok dla większości celów, i prawie zawsze generuje naprawdę losowy rozkład (z wyjątkiem sytuacji, gdy losowy.Next () tworzy dwie identyczne losowe liczby całkowite).

Działa poprzez przypisanie każdemu elementowi serii losowej liczby całkowitej, a następnie uporządkowanie sekwencji przez te liczby całkowite.

Jest to całkowicie dopuszczalne dla 99,9% aplikacji(chyba że bezwzględnie musisz obsłużyć powyższy przypadek edge). Również sprzeciw skeeta wobec jego działania jest ważny, więc jeśli tasujesz długi lista może nie chcesz jej używać.

Wydaje się dobrym algorytmem tasowania, jeśli nie martwisz się wydajnością. Jedynym problemem, na który chciałbym zwrócić uwagę jest to, że jego zachowanie nie jest kontrolowalne, więc możesz mieć problem z testowaniem go.

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

To było już wiele razy. Szukaj Fishera-Yatesa na StackOverflow.

Oto próbka kodu C# , którą napisałem dla tego algorytmu. Możesz sparametryzować go na innym typie, jeśli wolisz.

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;
                }
        }
}

Odpowiedź Jona Skeeta jest całkowicie zadowalająca, ale robo-skaner mojego klienta zgłosi każdy przypadek jako wadę bezpieczeństwa. Więc zamieniłem go na System.Security.Cryptography.RNGCryptoServiceProvider. Jako bonus naprawia wspomniany problem z bezpieczeństwem wątku. Z drugiej strony, RNGCryptoServiceProvider był mierzony 300x wolniej niż przy użyciu Random.

Użycie:

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];
    }
}

Trochę niepowiązane, ale tutaj jest ciekawa metoda (że choć jest naprawdę ekscessibe, naprawdę został wdrożony) dla naprawdę losowej generacji rzutów kostką!

Dice-O-Matic

Powodem, dla którego zamieszczam to tutaj, jest to, że robi kilka ciekawych punktów o tym, jak jego użytkownicy zareagowali na pomysł wykorzystania algorytmów do przetasowania, nad rzeczywistymi kostkami. Oczywiście w realnym świecie takie rozwiązanie jest tylko dla naprawdę ekstremalnych krańców widma, gdzie przypadkowość ma tak duży wpływ i być może wpływ wpływa na pieniądze ;).

Powiedziałbym, że wiele odpowiedzi tutaj takich jak "ten algorytm tasuje generując nową losową wartość dla każdej wartości na liście, a następnie porządkowanie listy przez te losowe wartości" może być bardzo błędne!

Wydaje mi się, że nie przydziela to losowej wartości każdemu elementowi zbioru źródłowego. Zamiast tego może istnieć algorytm sortowania działający jak Quicksort, który wywołałby funkcję porównawczą w przybliżeniu n log n razy. Pewnego rodzaju algorytm naprawdę oczekuje, że ta funkcja porównywania będzie stabilny i zawsze zwraca ten sam wynik!

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

W takim przypadku możesz naprawdę zepsuć algorytm sortowania i uczynić go znacznie gorszym niż oczekiwania, na których opiera się algorytm. Oczywiście w końcu stanie się stabilny i coś zwróci.

Mogę sprawdzić później, umieszczając debugowanie wyjścia wewnątrz nowej funkcji "Next", aby zobaczyć, co się dzieje. W Reflector nie mogłem od razu dowiedzieć się, jak to działa.

Szukasz algorytmu? Możesz użyć mojej klasy ShuffleList:

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 go tak:

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 zliczania nubmerów elementów i nazywa ją count. Następnie, gdy count maleje na każdym kroku, pobiera losową liczbę między 0 a count i przenosi ją na koniec listy.

W poniższym przykładzie krok po kroku, elementy które można przenieść to kursywa , zaznaczony element to pogrubienie :

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

Algorytm ten 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. Wygląda mi to na skuteczny sposób (szczególnie z cukrem lambda!)

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

Pierwszy nieudany kod. Działa na LINQPad. Jeśli zastosujesz się do przetestowania tego kodu.

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);

Lista.OrderBy (x => R.Next ()) używa 38.6528 ms

Lista.OrderBy (x = > Guid.NewGuid()) używa 36.7634 ms (jest to zalecane z MSDN.)

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

EDIT: Kod testowy na Intel Core i7 [email protected], Ram 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: LINQ OrderBy (R. Next ()) i OrderBy (Guid.NewGuid()) nie są gorsze od zdefiniowanej przez użytkownika metody Shuffle w pierwszym rozwiązaniu.