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

164

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?

Svish
źródło

Odpowiedzi:

205

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.

Jon Skeet
źródło
5
Cóż, implementacje dla małych, ale ważnych rzeczy, które powiedziałbym, zawsze są przyjemne do znalezienia w StackOverflow. Więc tak, proszę, jeśli chcesz =)
Svish
9
Jon - twoje wyjaśnienie Fishera-Yatesa jest równoważne z implementacją podaną w pytaniu (wersja naiwna). Durstenfeld / Knuth osiąga O (n) nie przez przypisanie, ale przez wybór z malejącego zbioru i zamiany. W ten sposób wybrana liczba losowa może się powtarzać, a algorytm przyjmuje tylko O ​​(n).
tvanfosson
8
Prawdopodobnie masz dość słuchania ode mnie o tym, ale napotkałem niewielki problem w moich testach jednostkowych, o którym być może chciałbyś wiedzieć. Istnieje dziwactwo z ElementAt, które powoduje, że wywołuje rozszerzenie za każdym razem, dając niewiarygodne wyniki. W moich testach materializuję wynik przed sprawdzeniem, aby tego uniknąć.
tvanfosson
3
@tvanfosson: Wcale nie chory :) Ale tak, dzwoniący powinni być świadomi, że jest oceniany leniwie.
Jon Skeet
4
Trochę późno, ale pamiętaj, source.ToArray();że musisz mieć using System.Linq;w tym samym pliku. Jeśli tego nie zrobisz, pojawi się ten błąd:'System.Collections.Generic.IEnumerable<T>' does not contain a definition for 'ToArray' and no extension method 'ToArray' accepting a first argument of type 'System.Collections.Generic.IEnumerable<T>' could be found (are you missing a using directive or an assembly reference?)
Powerlord
70

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]; 
}
konfigurator
źródło
Auć! To prawdopodobnie nie zwróci wszystkich elementów w źródle. Nie można polegać na unikalności losowej liczby w N iteracjach.
P Daddy
2
Sprytny! (I nienawidzę tego 15 znaków ...)
Svish
@P Daddy: Hę? Możesz rozwinąć temat?
Svish
1
Albo możesz zamienić> 0 na> = 0 i nie musisz tego robić (chociaż dodatkowe trafienie RNG plus nadmiarowe przypisanie)
FryGuy
4
Koszt uruchomienia wynosi O (N) jako koszt źródła.ToArray ();
Dave Hillier
8

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)

xanatos
źródło
Dobrze sformułowane i doskonale wyświetla problem z oryginalnym pytaniem. To powinno zostać połączone z odpowiedzią Jona.
TheSoftwareJedi
6

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ć.

zrywak234
źródło
4

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;
                }
        }
}
hughdbrown
źródło
2
Nie powinieneś używać Randomjako takiej zmiennej statycznej - Randomnie jest bezpieczna dla wątków. Zobacz csharpindepth.com/Articles/Chapter12/Random.aspx
Jon Skeet,
@Jon Skeet: jasne, to uzasadniony argument. OTOH, OP pytał o algorytm, który był całkowicie błędny, podczas gdy ten jest poprawny (inny niż przypadek użycia wielowątkowego tasowania kart).
hughdbrown,
1
Oznacza to po prostu, że jest to „mniej błędne” niż podejście PO. Nie oznacza to, że jest to kod, którego należy używać bez zrozumienia, że ​​nie można go bezpiecznie używać w kontekście wielowątkowym ... o czym nie wspomniałeś. Istnieje uzasadnione oczekiwanie, że statyczne elementy członkowskie mogą być bezpiecznie używane z wielu wątków.
Jon Skeet,
@Jon Skeet: Jasne, mogę to zmienić. Gotowe. Zwykle myślę, że wracając do pytania, na które odpowiedziano trzy i pół roku temu i mówiąc: „Jest niepoprawne, ponieważ nie obsługuje wielowątkowego przypadku użycia”, kiedy OP nigdy nie pytał o nic więcej, niż algorytm jest przesadny. Przejrzyj moje odpowiedzi na przestrzeni lat. Często udzielałem odpowiedzi PO, które wykraczały poza określone wymagania. Byłem za to krytykowany. Nie spodziewałbym się jednak, że OP otrzymają odpowiedzi pasujące do wszystkich możliwych zastosowań.
hughdbrown
W ogóle odwiedziłem tę odpowiedź tylko dlatego, że ktoś inny wskazał mi ją na czacie. Chociaż OP nie wspomniał konkretnie o wątkach, myślę, że zdecydowanie warto o tym wspomnieć, gdy metoda statyczna nie jest bezpieczna dla wątków, ponieważ jest niezwykła i sprawia, że ​​kod jest nieodpowiedni w wielu sytuacjach bez modyfikacji. Twój nowy kod jest bezpieczny dla wątków - ale nadal nie jest idealny, jakbyś wywoływał go z wielu wątków „mniej więcej” w tym samym czasie, aby przetasować dwie kolekcje tego samego rozmiaru, tasowanie będzie równoważne. Zasadniczo Randomjest to ból w użyciu, jak wspomniano w moim artykule.
Jon Skeet
3

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ć.

Samuel Carrijo
źródło
3

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];
    }
}
frattaro
źródło
3

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

SteeveDroz
źródło
To nie jest O (n). Tylko RemoveAt to O (n).
paparazzo
Hmm, wygląda na to, że masz rację, moja wina! Usunę tę część.
SteeveDroz,
1

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

Dave Swersky
źródło
1

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

Irfy
źródło
1

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.

chrześcijanin
źródło
1
Tak nie jest: wewnętrzne nadpisanie void ComputeKeys (elementy TElement [], liczba int); Deklarowanie typu: System.Linq.EnumerableSorter <TElement, TKey> Assembly: System.Core, Version = 3.5.0.0 Ta funkcja tworzy najpierw tablicę ze wszystkimi kluczami, które zużywają pamięć, zanim quicksort je sortuje
Christian
Dobrze wiedzieć - to jednak tylko szczegół implementacji, który może ulec zmianie w przyszłych wersjach!
Blorgbeard wychodzi
-5

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ą.

GMzo
źródło
1
Druga opcja nie jest poprawna , dlatego jej wydajność nie ma znaczenia . To również wciąż nie odpowiada na pytanie, czy zamawianie według liczby losowej jest akceptowalne, wydajne i jak to działa. Pierwsze rozwiązanie również ma problemy z poprawnością, ale nie są one tak duże.
Servy
Przepraszam, chciałbym wiedzieć, jaki jest lepszy rodzaj parametru Quicksort of Linq OrderBy? Muszę sprawdzić wydajność. Jednak myślę, że typ int ma po prostu lepszą prędkość niż ciąg Guid, ale tak nie jest. Zrozumiałem, dlaczego zaleca MSDN. Wydajność edycji pierwszego rozwiązania jest taka sama, jak OrderBy z wystąpieniem Random.
GMzo
Jaki jest sens mierzenia wydajności kodu, który nie rozwiązuje problemu? Wydajność jest tylko uwagę, aby pomiędzy dwoma rozwiązaniami że obie prace . Gdy masz rozwiązań pracy, wówczas można rozpocząć , aby je porównać.
Servy
Muszę mieć czas na przetestowanie większej ilości danych, a jeśli to się skończy, obiecuję, że opublikuję ponownie. Załóżmy: myślę, że Linq OrderBy nie jest gorsze niż pierwsze rozwiązanie. Opinia: jest łatwy w obsłudze i zrozumiały.
GMzo
Jest zauważalnie mniej wydajny niż bardzo proste, proste algorytmy tasowania, ale po raz kolejny wydajność nie ma znaczenia . Nie tasują danych niezawodnie, a ponadto są mniej wydajne.
Servy