Wybierz N losowych elementów z List <T> w C #

158

Potrzebuję szybkiego algorytmu, aby wybrać 5 losowych elementów z ogólnej listy. Na przykład chciałbym uzyskać 5 losowych elementów z pliku List<string>.

JC Grubbs
źródło
11
Termin „losowy” oznacza „włączający” czy „wyłączny”? IOW, czy ten sam element można wybrać więcej niż raz? (naprawdę losowe) Czy też po wybraniu elementu, czy nie będzie można go już wybrać z dostępnej puli?
Precel,

Odpowiedzi:

127

Iteruj przez i dla każdego elementu określ prawdopodobieństwo wyboru = (wymagana liczba) / (liczba po lewej)

Więc gdybyś miał 40 elementów, pierwszy miałby 5/40 szans na wybranie. Jeśli tak, następny ma szansę 4/39, w przeciwnym razie ma szansę 5/39. Zanim dojdziesz do końca, będziesz miał 5 przedmiotów, a często będziesz mieć je wszystkie przedtem.

Kyle Cronin
źródło
33
Czuję, że to subtelnie złe. Wygląda na to, że tylny koniec listy będzie wybierany częściej niż przód, ponieważ tylny koniec będzie widział znacznie większe prawdopodobieństwa. Na przykład, jeśli pierwsze 35 liczb nie zostanie wybranych, należy wybrać ostatnie 5 liczb. Pierwsza liczba zawsze będzie miała szansę 5/40, ale ostatnia liczba będzie miała 1/1 częściej niż 5/40 razy. Zanim zaimplementujesz ten algorytm, będziesz musiał najpierw zmienić listę losową.
Ankur Goel
23
ok, uruchomiłem ten algorytm 10 milionów razy na liście 40 elementów, każdy z 5/40 (0,125) strzałem w celu wybrania, a następnie uruchomiłem tę symulację kilka razy. Okazuje się, że nie jest to równomiernie rozłożone. Elementy od 16 do 22 są niedostarczane (16 = 0,123, 17 = 0,124), podczas gdy element 34 jest wybierany zbyt daleko (34 = 0,129). Elementy 39 i 40 również zostaną niedocenione, ale nie tak bardzo (39 = .1247, 40 = .1246)
Ankur Goel,
21
@Ankur: Nie sądzę, żeby to było istotne statystycznie. Uważam, że istnieje indukcyjny dowód na to, że zapewni to równomierną dystrybucję.
rekurencyjne
9
Powtórzyłem tę samą próbę 100 milionów razy, aw mojej próbie najmniej wybrany przedmiot był wybierany mniej niż 0,106% rzadziej niż najczęściej wybierany przedmiot.
rekurencyjne
5
@recursive: Dowód jest prawie trywialny. Wiemy, jak wybrać K elementów z K dla dowolnego K i jak wybrać 0 elementów z N dla dowolnego N. Załóżmy, że znamy metodę jednolitego wybierania elementów K lub K-1 z N-1> = K; następnie możemy wybrać K pozycji z N, wybierając pierwszą pozycję z prawdopodobieństwem K / N, a następnie stosując znaną metodę, aby wybrać nadal potrzebne K lub K-1 z pozostałych N-1.
Ilmari Karonen
216

Korzystanie z linq:

YourList.OrderBy(x => rnd.Next()).Take(5)
Ers
źródło
2
+1 Ale jeśli dwa elementy otrzymają ten sam numer z rnd.Next () lub podobny, to pierwszy zostanie wybrany, a drugi prawdopodobnie nie (jeśli nie potrzeba więcej elementów). Jest jednak odpowiednio losowy w zależności od użycia.
Lasse Espeholt,
7
Myślę, że kolejność według to O (n log (n)), więc wybrałbym to rozwiązanie, jeśli głównym problemem jest prostota kodu (np. Przy małych listach).
Guido
2
Ale czy to nie wylicza i nie sortuje całej listy? Chyba że przez „szybkie” OP oznaczało „łatwe”, a nie „wydajne” ...
drzaus
2
To zadziała tylko wtedy, gdy OrderBy () wywoła selektor kluczy tylko raz dla każdego elementu. Jeśli wywoła ją za każdym razem, gdy chce przeprowadzić porównanie między dwoma elementami, za każdym razem otrzyma inną wartość, co zepsuje sortowanie. [Dokumentacja] ( msdn.microsoft.com/en-us/library/vstudio/… ) nie mówi, co to robi.
Oliver Bock
2
Uważaj, jeśli YourListmasz dużo przedmiotów, ale chcesz wybrać tylko kilka. W tym przypadku nie jest to skuteczny sposób na zrobienie tego.
Callum Watkins
39
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
    return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
wag
źródło
27

W rzeczywistości jest to trudniejszy problem, niż się wydaje, głównie dlatego, że wiele matematycznie poprawnych rozwiązań nie pozwoli na trafienie wszystkich możliwości (więcej na ten temat poniżej).

Po pierwsze, oto kilka łatwych do zaimplementowania, poprawnych, jeśli masz-naprawdę-losowy generator liczb:

(0) Odpowiedź Kyle'a, czyli O (n).

(1) Wygeneruj listę n par [(0, rand), (1, rand), (2, rand), ...], posortuj je według drugiej współrzędnej i użyj pierwszego k (dla ciebie, k = 5), aby otrzymać losowy podzbiór. Myślę, że jest to łatwe do wykonania, chociaż jest to czas O (n log n).

(2) Wstaw pustą listę s = [], która będzie stanowić wskaźniki k losowych elementów. Wybierz losowo liczbę r z {0, 1, 2, ..., n-1}, r = rand% n, i dodaj ją do s. Następnie weź r = rand% (n-1) i włóż s; dodaj do r # elementów mniej niż w s, aby uniknąć kolizji. Następnie weź r = rand% (n-2) i zrób to samo, itd., Aż uzyskasz k różnych elementów w s. W najgorszym przypadku czas działania O (k ^ 2). Więc dla k << n może to być szybsze. Jeśli będziesz posortować s i śledzić, które ciągłe przedziały ma, możesz zaimplementować to w O (k log k), ale to więcej pracy.

@Kyle - masz rację, po zastanowieniu zgadzam się z twoją odpowiedzią. Na początku pospiesznie go przeczytałem i błędnie pomyślałem, że sugerujesz sekwencyjne wybieranie każdego elementu ze stałym prawdopodobieństwem k / n, co byłoby błędne - ale twoje podejście adaptacyjne wydaje mi się prawidłowe. Przepraszam za to.

Ok, a teraz dla kickera: asymptotycznie (dla ustalonego k, n rosnącego) jest n ^ k / k! wybory k elementów podzbioru z n elementów [jest to przybliżenie (n wybierz k)]. Jeśli n jest duże, a k nie jest bardzo małe, to te liczby są ogromne. Najlepsza długość cyklu, na jaką możesz liczyć w dowolnym standardowym 32-bitowym generatorze liczb losowych, to 2 ^ 32 = 256 ^ 4. Jeśli więc mamy listę 1000 elementów i chcemy losowo wybrać 5, nie ma mowy, żeby standardowy generator liczb losowych trafił we wszystkie możliwości. Jednakże, o ile nie przeszkadza Ci wybór, który działa dobrze dla mniejszych zestawów i zawsze „wygląda” losowo, to te algorytmy powinny działać.

Dodatek : Po napisaniu tego zdałem sobie sprawę, że trudno jest poprawnie wdrożyć pomysł (2), więc chciałem wyjaśnić tę odpowiedź. Aby uzyskać czas O (k log k), potrzebujesz struktury przypominającej tablicę, która obsługuje wyszukiwania i wstawianie O (log m) - może to zrobić zrównoważone drzewo binarne. Używając takiej struktury do zbudowania tablicy o nazwie s, oto kilka pseudopytonów:

# Returns a container s with k distinct random numbers from {0, 1, ..., n-1}
def ChooseRandomSubset(n, k):
  for i in range(k):
    r = UniformRandom(0, n-i)                 # May be 0, must be < n-i
    q = s.FirstIndexSuchThat( s[q] - q > r )  # This is the search.
    s.InsertInOrder(q ? r + q : r + len(s))   # Inserts right before q.
  return s

Proponuję przejrzeć kilka przykładowych przypadków, aby zobaczyć, jak skutecznie implementuje to powyższe angielskie wyjaśnienie.

Tyler
źródło
2
dla (1) możesz tasować listę szybciej niż sortowanie, dla (2) będziesz promował swoją dystrybucję używając%
jk.
Ze względu na sprzeciw ty podniesiony o długości cyklu z RNG, czy jest jakiś sposób, że można skonstruować algorytm, który wybierze wszystkie zestawy z równym prawdopodobieństwem?
Jonah,
W przypadku (1), aby poprawić O (n log (n)), możesz użyć sortowania przez wybór, aby znaleźć k najmniejszych elementów. To będzie działać w O (n * k).
Jared
@Jonah: Myślę, że tak. Załóżmy, że możemy połączyć wiele niezależnych generatorów liczb losowych, aby utworzyć większy ( crypto.stackexchange.com/a/27431 ). Wtedy potrzebny jest tylko wystarczająco duży zakres, aby poradzić sobie z rozmiarem danej listy.
Jared
16

Myślę, że wybrana odpowiedź jest poprawna i całkiem słodka. Zaimplementowałem to jednak inaczej, ponieważ chciałem również uzyskać wynik w losowej kolejności.

    static IEnumerable<SomeType> PickSomeInRandomOrder<SomeType>(
        IEnumerable<SomeType> someTypes,
        int maxCount)
    {
        Random random = new Random(DateTime.Now.Millisecond);

        Dictionary<double, SomeType> randomSortTable = new Dictionary<double,SomeType>();

        foreach(SomeType someType in someTypes)
            randomSortTable[random.NextDouble()] = someType;

        return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);
    }
Frank Schwieterman
źródło
NIESAMOWITE! Naprawdę mi pomogło!
Armstrongest
1
Czy masz jakiś powód, aby nie używać nowej funkcji Random () opartej na środowisku Environment.TickCount i DateTime.Now.Millisecond?
Lasse Espeholt,
Nie, po prostu nie zdawałem sobie sprawy, że istnieje domyślne ustawienie.
Frank Schwieterman
Ulepszenie randomSortTable: randomSortTable = someTypes.ToDictionary (x => random.NextDouble (), y => y); Zapisuje foreach pętlę.
Keltex
2
OK rok późno, ale ... Czy to nie pasuje do raczej krótszej odpowiedzi @ ersin i czy nie zawiedzie, jeśli otrzymasz powtarzającą się liczbę losową (gdzie Ersin będzie miał tendencję do uprzedzenia w kierunku pierwszej pozycji z powtarzanej pary)
Andiih
12

Właśnie natknąłem się na ten problem, a dalsze wyszukiwanie w Google doprowadziło mnie do problemu losowego tasowania listy: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle

Aby całkowicie losowo potasować listę (w miejscu), wykonaj następujące czynności:

Aby przetasować tablicę a złożoną z n elementów (indeksy 0..n-1):

  for i from n  1 downto 1 do
       j  random integer with 0  j  i
       exchange a[j] and a[i]

Jeśli potrzebujesz tylko pierwszych 5 elementów, to zamiast uruchamiać i od n-1 do 1, wystarczy uruchomić go do n-5 (tj .: n-5)

Powiedzmy, że potrzebujesz k przedmiotów,

To staje się:

  for (i = n  1; i >= n-k; i--)
  {
       j = random integer with 0  j  i
       exchange a[j] and a[i]
  }

Każdy zaznaczony element jest zamieniany pod koniec tablicy, więc k wybranych elementów to ostatnie k elementów tablicy.

Zajmuje to czas O (k), gdzie k to liczba losowo wybranych elementów, których potrzebujesz.

Ponadto, jeśli nie chcesz modyfikować swojej początkowej listy, możesz zapisać wszystkie swoje zamiany na liście tymczasowej, odwrócić tę listę i zastosować je ponownie, wykonując w ten sposób odwrotny zestaw zamian i zwracając swoją początkową listę bez zmiany czas pracy O (k).

Wreszcie, dla prawdziwego sticklera, jeśli (n == k), powinieneś zatrzymać się na 1, a nie nk, ponieważ losowo wybrana liczba całkowita będzie zawsze wynosić 0.

dhakim
źródło
Zaimplementowałem to za pomocą C # na moim blogu: vijayt.com/post/random-select-using-fisher-yates-algorithm . Mam nadzieję, że pomoże to komuś, kto szuka sposobu C #.
vijayst,
9

Możesz z tego skorzystać, ale zamawianie będzie odbywać się po stronie klienta

 .AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
Marwan Roushdy
źródło
Zgoda. Może nie jest to najlepszy wynik lub najbardziej losowy, ale dla większości ludzi to wystarczy.
Richiban
Negocjowane, ponieważ Guidy są unikalne, a nie losowe .
Theodor Zoulias
8

From Dragons in the Algorithm , interpretacja w C #:

int k = 10; // items to select
var items = new List<int>(new[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 });
var selected = new List<int>();
double needed = k;
double available = items.Count;
var rand = new Random();
while (selected.Count < k) {
   if( rand.NextDouble() < needed / available ) {
      selected.Add(items[(int)available-1])
      needed--;
   }
   available--;
}

Algorytm ten wybierze unikalne wskazania listy pozycji.

spoulson
źródło
Zdobądź tylko wystarczającą liczbę pozycji na liście, ale nie otrzymuj losowo.
culithay
2
Ta implementacja jest zepsuta, ponieważ użycie varwyników neededi availableoba są liczbami całkowitymi, co daje needed/availablezawsze 0.
Niko
1
Wydaje się, że jest to implementacja zaakceptowanej odpowiedzi.
DCShannon
6

Wybór N losowych przedmiotów z grupy nie powinien mieć nic wspólnego z porządkiem ! Losowość dotyczy nieprzewidywalności, a nie tasowania pozycji w grupie. Wszystkie odpowiedzi, które dotyczą jakiegoś rodzaju zamawiania, z pewnością będą mniej efektywne niż te, które tego nie robią. Ponieważ efektywność jest tutaj kluczowa, opublikuję coś, co nie zmienia zbytnio kolejności przedmiotów.

1) Jeśli potrzebujesz prawdziwie losowych wartości, co oznacza, że ​​nie ma ograniczeń co do elementów do wyboru (tj. Raz wybrany element można ponownie wybrać):

public static List<T> GetTrueRandom<T>(this IList<T> source, int count, 
                                       bool throwArgumentOutOfRangeException = true)
{
    if (throwArgumentOutOfRangeException && count > source.Count)
        throw new ArgumentOutOfRangeException();

    var randoms = new List<T>(count);
    randoms.AddRandomly(source, count);
    return randoms;
}

Jeśli wyłączysz flagę wyjątku, możesz wybierać losowe elementy dowolną liczbę razy.

Jeśli masz {1, 2, 3, 4}, to może dać {1, 4, 4}, {1, 4, 3} itd. Za 3 elementy lub nawet {1, 4, 3, 2, 4} za 5 sztuk!

Powinno to nastąpić dość szybko, ponieważ nie ma nic do sprawdzenia.

2) Jeśli potrzebujesz pojedynczych członków z grupy bez powtórzeń, skorzystam ze słownika (jak wielu już zauważyło).

public static List<T> GetDistinctRandom<T>(this IList<T> source, int count)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    if (count == source.Count)
        return new List<T>(source);

    var sourceDict = source.ToIndexedDictionary();

    if (count > source.Count / 2)
    {
        while (sourceDict.Count > count)
            sourceDict.Remove(source.GetRandomIndex());

        return sourceDict.Select(kvp => kvp.Value).ToList();
    }

    var randomDict = new Dictionary<int, T>(count);
    while (randomDict.Count < count)
    {
        int key = source.GetRandomIndex();
        if (!randomDict.ContainsKey(key))
            randomDict.Add(key, sourceDict[key]);
    }

    return randomDict.Select(kvp => kvp.Value).ToList();
}

Kod jest nieco dłuższy niż inne podejścia słownikowe, ponieważ nie tylko dodam, ale także usuwam z listy, więc jest to rodzaj dwóch pętli. Widać tutaj, że w ogóle niczego nie zmieniłem , gdy stanie countsię równy source.Count. To dlatego, że uważam, że losowość powinna występować w zwracanym zestawie jako całości . To znaczy, jeśli chcesz 5 losowych elementów z 1, 2, 3, 4, 5, nie powinno sprawa jeśli jego 1, 3, 4, 2, 5albo 1, 2, 3, 4, 5, ale jeśli potrzebujesz 4 pozycji z tego samego zestawu, to powinien w sposób nieprzewidywalny wydajność 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4itd. Po drugie, gdy liczba przypadkowych elementów, które należy zwrócona jest więcej niż połowa pierwotnej grupy, więc łatwiej ją usunąćsource.Count - countelementy z grupy niż dodawanie countelementów. Ze względu na wydajność użyłem sourcezamiast sourceDicttego losowego indeksu w metodzie usuwania.

Więc jeśli masz {1, 2, 3, 4}, może to skończyć się na {1, 2, 3}, {3, 4, 1} itd. Dla 3 elementów.

3) Jeśli potrzebujesz naprawdę odrębnych losowych wartości ze swojej grupy, biorąc pod uwagę duplikaty w oryginalnej grupie, możesz użyć tego samego podejścia, co powyżej, ale HashSetbędzie lżejsze niż słownik.

public static List<T> GetTrueDistinctRandom<T>(this IList<T> source, int count, 
                                               bool throwArgumentOutOfRangeException = true)
{
    if (count > source.Count)
        throw new ArgumentOutOfRangeException();

    var set = new HashSet<T>(source);

    if (throwArgumentOutOfRangeException && count > set.Count)
        throw new ArgumentOutOfRangeException();

    List<T> list = hash.ToList();

    if (count >= set.Count)
        return list;

    if (count > set.Count / 2)
    {
        while (set.Count > count)
            set.Remove(list.GetRandom());

        return set.ToList();
    }

    var randoms = new HashSet<T>();
    randoms.AddRandomly(list, count);
    return randoms.ToList();
}

randomsZmienna skierowany jest HashSetdo uniknięcia duplikaty dodawano w najrzadszych najrzadszych przypadkach Random.Nextmogą wywoływać tę samą wartość, w szczególności, gdy listy wejście jest mała.

Więc {1, 2, 2, 4} => 3 losowe elementy => {1, 2, 4} i nigdy {1, 2, 2}

{1, 2, 2, 4} => 4 losowe przedmioty => wyjątek !! lub {1, 2, 4} w zależności od ustawionej flagi.

Niektóre z metod rozszerzających, których użyłem:

static Random rnd = new Random();
public static int GetRandomIndex<T>(this ICollection<T> source)
{
    return rnd.Next(source.Count);
}

public static T GetRandom<T>(this IList<T> source)
{
    return source[source.GetRandomIndex()];
}

static void AddRandomly<T>(this ICollection<T> toCol, IList<T> fromList, int count)
{
    while (toCol.Count < count)
        toCol.Add(fromList.GetRandom());
}

public static Dictionary<int, T> ToIndexedDictionary<T>(this IEnumerable<T> lst)
{
    return lst.ToIndexedDictionary(t => t);
}

public static Dictionary<int, T> ToIndexedDictionary<S, T>(this IEnumerable<S> lst, 
                                                           Func<S, T> valueSelector)
{
    int index = -1;
    return lst.ToDictionary(t => ++index, valueSelector);
}

Jeśli chodzi o wydajność z dziesiątkami tysięcy pozycji na liście, które muszą być iterowane 10000 razy, możesz chcieć mieć szybszą klasę losową niż System.Random, ale nie sądzę, że to wielka sprawa, biorąc pod uwagę, że ta druga prawdopodobnie nigdy nie jest wąskie gardło, jest dość szybkie.

Edycja: Jeśli chcesz zmienić kolejność zwracanych produktów, nic nie może pokonać podejścia dhakima Fisher-Yates - krótkie, słodkie i proste.

nawfal
źródło
6

Zastanawiałem się nad komentarzem @JohnShedletsky na temat zaakceptowanej odpowiedzi dotyczącej (parafraza):

powinieneś być w stanie to zrobić w O (subset.Length), a nie O (originalList.Length)

Zasadniczo powinieneś być w stanie wygenerować subsetlosowe indeksy, a następnie pobrać je z oryginalnej listy.

Metoda

public static class EnumerableExtensions {

    public static Random randomizer = new Random(); // you'd ideally be able to replace this with whatever makes you comfortable

    public static IEnumerable<T> GetRandom<T>(this IEnumerable<T> list, int numItems) {
        return (list as T[] ?? list.ToArray()).GetRandom(numItems);

        // because ReSharper whined about duplicate enumeration...
        /*
        items.Add(list.ElementAt(randomizer.Next(list.Count()))) ) numItems--;
        */
    }

    // just because the parentheses were getting confusing
    public static IEnumerable<T> GetRandom<T>(this T[] list, int numItems) {
        var items = new HashSet<T>(); // don't want to add the same item twice; otherwise use a list
        while (numItems > 0 )
            // if we successfully added it, move on
            if( items.Add(list[randomizer.Next(list.Length)]) ) numItems--;

        return items;
    }

    // and because it's really fun; note -- you may get repetition
    public static IEnumerable<T> PluckRandomly<T>(this IEnumerable<T> list) {
        while( true )
            yield return list.ElementAt(randomizer.Next(list.Count()));
    }

}

Jeśli chcesz być jeszcze bardziej efektywny, prawdopodobnie używać HashSetz indeksami , a nie rzeczywiste elementy listy (w przypadku, gdy mamy złożonych typów lub kosztowne porównań);

Test jednostkowy

Aby upewnić się, że nie mamy żadnych kolizji itp.

[TestClass]
public class RandomizingTests : UnitTestBase {
    [TestMethod]
    public void GetRandomFromList() {
        this.testGetRandomFromList((list, num) => list.GetRandom(num));
    }

    [TestMethod]
    public void PluckRandomly() {
        this.testGetRandomFromList((list, num) => list.PluckRandomly().Take(num), requireDistinct:false);
    }

    private void testGetRandomFromList(Func<IEnumerable<int>, int, IEnumerable<int>> methodToGetRandomItems, int numToTake = 10, int repetitions = 100000, bool requireDistinct = true) {
        var items = Enumerable.Range(0, 100);
        IEnumerable<int> randomItems = null;

        while( repetitions-- > 0 ) {
            randomItems = methodToGetRandomItems(items, numToTake);
            Assert.AreEqual(numToTake, randomItems.Count(),
                            "Did not get expected number of items {0}; failed at {1} repetition--", numToTake, repetitions);
            if(requireDistinct) Assert.AreEqual(numToTake, randomItems.Distinct().Count(),
                            "Collisions (non-unique values) found, failed at {0} repetition--", repetitions);
            Assert.IsTrue(randomItems.All(o => items.Contains(o)),
                        "Some unknown values found; failed at {0} repetition--", repetitions);
        }
    }
}
drzaus
źródło
2
Niezły pomysł, z problemami. (1) Jeśli twoja większa lista jest ogromna (na przykład odczytana z bazy danych), to zdajesz sobie sprawę z całej listy, która może przekraczać pamięć. (2) Jeśli K jest blisko N, będziesz dużo szarpać szukając nieodebranego indeksu w pętli, powodując, że kod będzie wymagał nieprzewidywalnej ilości czasu. Te problemy można rozwiązać.
Paul Chernoch
1
Moje rozwiązanie problemu bicia jest takie: jeśli K <N / 2, zrób to po swojemu. Jeśli K> = N / 2, wybierz wskaźniki, których NIE należy zachować, zamiast tych, które powinny być zachowane. Wciąż jest trochę bicia, ale znacznie mniej.
Paul Chernoch
Zauważyłem również, że zmienia to kolejność wyliczanych pozycji, co może być dopuszczalne w niektórych sytuacjach, ale nie w innych.
Paul Chernoch
Średnio dla K = N / 2 (najgorszy przypadek dla sugerowanej poprawy Paula), algorytm (poprawiony wbicie) wydaje się przyjmować ~ 0,693 * N iteracji. Teraz zrób porównanie prędkości. Czy to lepsze niż zaakceptowana odpowiedź? Dla jakich wielkości próbek?
mbomb007
6

Połączyłem kilka z powyższych odpowiedzi, aby utworzyć metodę rozszerzenia ocenianą leniwie. Moje testy wykazały, że podejście Kyle'a (Order (N)) jest wielokrotnie wolniejsze niż użycie zbioru przez drzausa do zaproponowania losowych wskaźników do wyboru (Order (K)). Pierwsza wykonuje o wiele więcej wywołań do generatora liczb losowych, a także wykonuje więcej iteracji po elementach.

Cele mojej realizacji to:

1) Nie uświadamiaj sobie pełnej listy, jeśli masz IEnumerable, który nie jest IList. Jeśli dostanę sekwencję miliardów pozycji, nie chcę, by zabrakło mi pamięci. Skorzystaj z podejścia Kyle'a, aby uzyskać rozwiązanie online.

2) Jeśli mogę stwierdzić, że jest to IList, użyj podejścia drzausa, z niespodzianką. Jeśli K to więcej niż połowa N, ryzykuję rzucanie się, ponieważ wielokrotnie wybieram wiele losowych wskaźników i muszę je pomijać. W ten sposób układam listę wskaźników, których NIE należy przechowywać.

3) Gwarantuję, że przedmioty zostaną zwrócone w tej samej kolejności, w jakiej zostały napotkane. Algorytm Kyle'a nie wymagał żadnych zmian. Algorytm drzausa wymagał, abym nie emitował przedmiotów w kolejności, w jakiej są wybrane wskaźniki losowe. Zbieram wszystkie indeksy w SortedSet, a następnie emituję elementy w posortowanej kolejności indeksów.

4) Jeśli K jest duże w porównaniu z N i odwracam sens zbioru, wówczas wyliczam wszystkie pozycje i sprawdzam, czy indeks nie znajduje się w zestawie. Oznacza to, że tracę czas działania Order (K), ale ponieważ K jest blisko N w tych przypadkach, nie tracę dużo.

Oto kod:

    /// <summary>
    /// Takes k elements from the next n elements at random, preserving their order.
    /// 
    /// If there are fewer than n elements in items, this may return fewer than k elements.
    /// </summary>
    /// <typeparam name="TElem">Type of element in the items collection.</typeparam>
    /// <param name="items">Items to be randomly selected.</param>
    /// <param name="k">Number of items to pick.</param>
    /// <param name="n">Total number of items to choose from.
    /// If the items collection contains more than this number, the extra members will be skipped.
    /// If the items collection contains fewer than this number, it is possible that fewer than k items will be returned.</param>
    /// <returns>Enumerable over the retained items.
    /// 
    /// See http://stackoverflow.com/questions/48087/select-a-random-n-elements-from-listt-in-c-sharp for the commentary.
    /// </returns>
    public static IEnumerable<TElem> TakeRandom<TElem>(this IEnumerable<TElem> items, int k, int n)
    {
        var r = new FastRandom();
        var itemsList = items as IList<TElem>;

        if (k >= n || (itemsList != null && k >= itemsList.Count))
            foreach (var item in items) yield return item;
        else
        {  
            // If we have a list, we can infer more information and choose a better algorithm.
            // When using an IList, this is about 7 times faster (on one benchmark)!
            if (itemsList != null && k < n/2)
            {
                // Since we have a List, we can use an algorithm suitable for Lists.
                // If there are fewer than n elements, reduce n.
                n = Math.Min(n, itemsList.Count);

                // This algorithm picks K index-values randomly and directly chooses those items to be selected.
                // If k is more than half of n, then we will spend a fair amount of time thrashing, picking
                // indices that we have already picked and having to try again.   
                var invertSet = k >= n/2;  
                var positions = invertSet ? (ISet<int>) new HashSet<int>() : (ISet<int>) new SortedSet<int>();

                var numbersNeeded = invertSet ? n - k : k;
                while (numbersNeeded > 0)
                    if (positions.Add(r.Next(0, n))) numbersNeeded--;

                if (invertSet)
                {
                    // positions contains all the indices of elements to Skip.
                    for (var itemIndex = 0; itemIndex < n; itemIndex++)
                    {
                        if (!positions.Contains(itemIndex))
                            yield return itemsList[itemIndex];
                    }
                }
                else
                {
                    // positions contains all the indices of elements to Take.
                    foreach (var itemIndex in positions)
                        yield return itemsList[itemIndex];              
                }
            }
            else
            {
                // Since we do not have a list, we will use an online algorithm.
                // This permits is to skip the rest as soon as we have enough items.
                var found = 0;
                var scanned = 0;
                foreach (var item in items)
                {
                    var rand = r.Next(0,n-scanned);
                    if (rand < k - found)
                    {
                        yield return item;
                        found++;
                    }
                    scanned++;
                    if (found >= k || scanned >= n)
                        break;
                }
            }
        }  
    } 

Używam wyspecjalizowanego generatora liczb losowych, ale jeśli chcesz, możesz po prostu użyć funkcji Random w języku C # . ( FastRandom został napisany przez Colina Greena i jest częścią SharpNEAT. Ma okres 2 ^ 128-1, czyli lepszy niż wiele RNG).

Oto testy jednostkowe:

[TestClass]
public class TakeRandomTests
{
    /// <summary>
    /// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_Array_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials/20;
        var timesChosen = new int[100];
        var century = new int[100];
        for (var i = 0; i < century.Length; i++)
            century[i] = i;

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in century.TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount/100;
        AssertBetween(avg, expectedCount - 2, expectedCount + 2, "Average");
        //AssertBetween(min, expectedCount - allowedDifference, expectedCount, "Min");
        //AssertBetween(max, expectedCount, expectedCount + allowedDifference, "Max");

        var countInRange = timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    /// <summary>
    /// Ensure that when randomly choosing items from an IEnumerable that is not an IList, 
    /// all items are chosen with roughly equal probability.
    /// </summary>
    [TestMethod]
    public void TakeRandom_IEnumerable_Uniformity()
    {
        const int numTrials = 2000000;
        const int expectedCount = numTrials / 20;
        var timesChosen = new int[100];

        for (var trial = 0; trial < numTrials; trial++)
        {
            foreach (var i in Range(0,100).TakeRandom(5, 100))
                timesChosen[i]++;
        }
        var avg = timesChosen.Average();
        var max = timesChosen.Max();
        var min = timesChosen.Min();
        var allowedDifference = expectedCount / 100;
        var countInRange =
            timesChosen.Count(i => i >= expectedCount - allowedDifference && i <= expectedCount + allowedDifference);
        Assert.IsTrue(countInRange >= 90, String.Format("Not enough were in range: {0}", countInRange));
    }

    private IEnumerable<int> Range(int low, int count)
    {
        for (var i = low; i < low + count; i++)
            yield return i;
    }

    private static void AssertBetween(int x, int low, int high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }

    private static void AssertBetween(double x, double low, double high, String message)
    {
        Assert.IsTrue(x > low, String.Format("Value {0} is less than lower limit of {1}. {2}", x, low, message));
        Assert.IsTrue(x < high, String.Format("Value {0} is more than upper limit of {1}. {2}", x, high, message));
    }
}
Paul Chernoch
źródło
Czy w teście nie ma błędu? Masz, if (itemsList != null && k < n/2)co oznacza, że if invertSetzawsze jest w środku, falseco oznacza, że ​​logika nigdy nie jest używana.
NetMage
4

Wychodząc od odpowiedzi @ ers, jeśli ktoś obawia się o możliwe różne implementacje OrderBy, powinno to być bezpieczne:

// Instead of this
YourList.OrderBy(x => rnd.Next()).Take(5)

// Temporarily transform 
YourList
    .Select(v => new {v, i = rnd.Next()}) // Associate a random index to each entry
    .OrderBy(x => x.i).Take(5) // Sort by (at this point fixed) random index 
    .Select(x => x.v); // Go back to enumerable of entry
trudne
źródło
3

To najlepsze, co mogłem wymyślić przy pierwszym cięciu:

public List<String> getRandomItemsFromList(int returnCount, List<String> list)
{
    List<String> returnList = new List<String>();
    Dictionary<int, int> randoms = new Dictionary<int, int>();

    while (randoms.Count != returnCount)
    {
        //generate new random between one and total list count
        int randomInt = new Random().Next(list.Count);

        // store this in dictionary to ensure uniqueness
        try
        {
            randoms.Add(randomInt, randomInt);
        }
        catch (ArgumentException aex)
        {
            Console.Write(aex.Message);
        } //we can assume this element exists in the dictonary already 

        //check for randoms length and then iterate through the original list 
        //adding items we select via random to the return list
        if (randoms.Count == returnCount)
        {
            foreach (int key in randoms.Keys)
                returnList.Add(list[randoms[key]]);

            break; //break out of _while_ loop
        }
    }

    return returnList;
}

Używanie listy losowych w zakresie od 1 - całkowita liczba list, a następnie po prostu wyciąganie tych pozycji z listy wydawało się najlepszym sposobem, ale używanie Słownika w celu zapewnienia wyjątkowości jest czymś, nad czym wciąż się zastanawiam.

Zauważ również, że użyłem listy ciągów, w razie potrzeby zastąp.

IanStallings
źródło
1
Pracował przy pierwszym ujęciu!
sangam
3

Proste rozwiązanie, którego używam (prawdopodobnie nie jest dobre dla dużych list): Skopiuj listę do listy tymczasowej, a następnie w pętli losowo wybierz pozycję z listy tymczasowej i umieść ją na liście wybranych pozycji podczas usuwania z listy tymczasowej (więc nie może być wybrany ponownie).

Przykład:

List<Object> temp = OriginalList.ToList();
List<Object> selectedItems = new List<Object>();
Random rnd = new Random();
Object o;
int i = 0;
while (i < NumberOfSelectedItems)
{
            o = temp[rnd.Next(temp.Count)];
            selectedItems.Add(o);
            temp.Remove(o);
            i++;
 }
Ząb M.
źródło
Usunięcie ze środka listy tak często będzie kosztowne. Możesz rozważyć użycie połączonej listy dla algorytmu wymagającego tak wielu usunięć. Lub równoważnie, zamień usunięty element na wartość zerową, ale wtedy będziesz trochę szarpać, gdy będziesz wybierać już usunięte elementy i będziesz musiał wybrać ponownie.
Paul Chernoch
3

Tutaj mamy jedną implementację opartą na tasowaniu Fishera-Yatesa, której złożoność algorytmu wynosi O (n), gdzie n jest podzbiorem lub rozmiarem próbki, a nie rozmiarem listy, jak wskazał John Shedletsky.

public static IEnumerable<T> GetRandomSample<T>(this IList<T> list, int sampleSize)
{
    if (list == null) throw new ArgumentNullException("list");
    if (sampleSize > list.Count) throw new ArgumentException("sampleSize may not be greater than list count", "sampleSize");
    var indices = new Dictionary<int, int>(); int index;
    var rnd = new Random();

    for (int i = 0; i < sampleSize; i++)
    {
        int j = rnd.Next(i, list.Count);
        if (!indices.TryGetValue(j, out index)) index = j;

        yield return list[index];

        if (!indices.TryGetValue(i, out index)) index = i;
        indices[j] = index;
    }
}
Jesús López
źródło
2

W oparciu o odpowiedź Kyle'a, oto moja implementacja C #.

/// <summary>
/// Picks random selection of available game ID's
/// </summary>
private static List<int> GetRandomGameIDs(int count)
{       
    var gameIDs = (int[])HttpContext.Current.Application["NonDeletedArcadeGameIDs"];
    var totalGameIDs = gameIDs.Count();
    if (count > totalGameIDs) count = totalGameIDs;

    var rnd = new Random();
    var leftToPick = count;
    var itemsLeft = totalGameIDs;
    var arrPickIndex = 0;
    var returnIDs = new List<int>();
    while (leftToPick > 0)
    {
        if (rnd.Next(0, itemsLeft) < leftToPick)
        {
            returnIDs .Add(gameIDs[arrPickIndex]);
            leftToPick--;
        }
        arrPickIndex++;
        itemsLeft--;
    }

    return returnIDs ;
}
Tom Gullen
źródło
2

Ta metoda może być równoważna z metodą Kyle'a.

Powiedzmy, że twoja lista ma rozmiar n i chcesz mieć k elementów.

Random rand = new Random();
for(int i = 0; k>0; ++i) 
{
    int r = rand.Next(0, n-i);
    if(r<k) 
    {
        //include element i
        k--;
    }
} 

Działa jak marzenie :)

-Alex Gilbert

Alex Gilbert
źródło
1
To wygląda na równoważne mnie. Porównaj z podobnym stackoverflow.com/a/48141/2449863
DCShannon,
1

czemu nie coś takiego:

 Dim ar As New ArrayList
    Dim numToGet As Integer = 5
    'hard code just to test
    ar.Add("12")
    ar.Add("11")
    ar.Add("10")
    ar.Add("15")
    ar.Add("16")
    ar.Add("17")

    Dim randomListOfProductIds As New ArrayList

    Dim toAdd As String = ""
    For i = 0 To numToGet - 1
        toAdd = ar(CInt((ar.Count - 1) * Rnd()))

        randomListOfProductIds.Add(toAdd)
        'remove from id list
        ar.Remove(toAdd)

    Next
'sorry i'm lazy and have to write vb at work :( and didn't feel like converting to c#
Cameron A. Ellis
źródło
1

Cel: Wybierz liczbę N elementów ze źródła kolekcji bez powielania. Stworzyłem rozszerzenie dla dowolnej kolekcji ogólnej. Oto jak to zrobiłem:

public static class CollectionExtension
{
    public static IList<TSource> RandomizeCollection<TSource>(this IList<TSource> source, int maxItems)
    {
        int randomCount = source.Count > maxItems ? maxItems : source.Count;
        int?[] randomizedIndices = new int?[randomCount];
        Random random = new Random();

        for (int i = 0; i < randomizedIndices.Length; i++)
        {
            int randomResult = -1;
            while (randomizedIndices.Contains((randomResult = random.Next(0, source.Count))))
            {
                //0 -> since all list starts from index 0; source.Count -> maximum number of items that can be randomize
                //continue looping while the generated random number is already in the list of randomizedIndices
            }

            randomizedIndices[i] = randomResult;
        }

        IList<TSource> result = new List<TSource>();
        foreach (int index in randomizedIndices)
            result.Add(source.ElementAt(index));

        return result;
    }
}
Jesse Gador
źródło
0

Niedawno zrobiłem to w moim projekcie, korzystając z pomysłu podobnego do punktu 1 Tylera .
Ładowałem kilka pytań i wybierałem pięć losowo. Sortowanie przeprowadzono za pomocą IComparer .
aWszystkie pytania zostały załadowane do listy QuestionSorter, która następnie została posortowana za pomocą funkcji Sortowanie listy i pierwszych k elementów, które zostały wybrane.

    private class QuestionSorter : IComparable<QuestionSorter>
    {
        public double SortingKey
        {
            get;
            set;
        }

        public Question QuestionObject
        {
            get;
            set;
        }

        public QuestionSorter(Question q)
        {
            this.SortingKey = RandomNumberGenerator.RandomDouble;
            this.QuestionObject = q;
        }

        public int CompareTo(QuestionSorter other)
        {
            if (this.SortingKey < other.SortingKey)
            {
                return -1;
            }
            else if (this.SortingKey > other.SortingKey)
            {
                return 1;
            }
            else
            {
                return 0;
            }
        }
    }

Stosowanie:

    List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();

    // add the questions here

    unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);

    // select the first k elements
hitec
źródło
0

Oto moje podejście (pełny tekst tutaj http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).

Powinien działać w O (K) zamiast O (N), gdzie K to liczba poszukiwanych elementów, a N to rozmiar listy do wyboru:

public <T> List<T> take(List<T> source, int k) {
 int n = source.size();
 if (k > n) {
   throw new IllegalStateException(
     "Can not take " + k +
     " elements from a list with " + n +
     " elements");
 }
 List<T> result = new ArrayList<T>(k);
 Map<Integer,Integer> used = new HashMap<Integer,Integer>();
 int metric = 0;
 for (int i = 0; i < k; i++) {
   int off = random.nextInt(n - i);
   while (true) {
     metric++;
     Integer redirect = used.put(off, n - i - 1);
     if (redirect == null) {
       break;
     }
     off = redirect;
   }
   result.add(source.get(off));
 }
 assert metric <= 2*k;
 return result;
}
Kristofer
źródło
0

To nie jest tak eleganckie ani wydajne jak przyjęte rozwiązanie, ale można je szybko opisać. Najpierw losowo permutuj tablicę, a następnie wybierz pierwsze K elementów. W Pythonie

import numpy

N = 20
K = 5

idx = np.arange(N)
numpy.random.shuffle(idx)

print idx[:K]
apdnu
źródło
0

Użyłbym metody rozszerzenia.

    public static IEnumerable<T> TakeRandom<T>(this IEnumerable<T> elements, int countToTake)
    {
        var random = new Random();

        var internalList = elements.ToList();

        var selected = new List<T>();
        for (var i = 0; i < countToTake; ++i)
        {
            var next = random.Next(0, internalList.Count - selected.Count);
            selected.Add(internalList[next]);
            internalList[next] = internalList[internalList.Count - selected.Count];
        }
        return selected;
    }
Kvam
źródło
0
public static IEnumerable<T> GetRandom<T>(this IList<T> list, int count, Random random)
    {
        // Probably you should throw exception if count > list.Count
        count = Math.Min(list.Count, count);

        var selectedIndices = new SortedSet<int>();

        // Random upper bound
        int randomMax = list.Count - 1;

        while (selectedIndices.Count < count)
        {
            int randomIndex = random.Next(0, randomMax);

            // skip over already selected indeces
            foreach (var selectedIndex in selectedIndices)
                if (selectedIndex <= randomIndex)
                    ++randomIndex;
                else
                    break;

            yield return list[randomIndex];

            selectedIndices.Add(randomIndex);
            --randomMax;
        }
    }

Pamięć: ~ liczba
Złożoność: O (liczba 2 )

Kardynał
źródło
0

Gdy N jest bardzo duże, normalna metoda losowego tasowania liczb N i wybierania, powiedzmy, pierwszych k liczb, może być przeszkodą ze względu na złożoność przestrzeni. Poniższy algorytm wymaga tylko O ​​(k) zarówno dla złożoności czasowej, jak i przestrzennej.

http://arxiv.org/abs/1512.00501

def random_selection_indices(num_samples, N):
    modified_entries = {}
    seq = []
    for n in xrange(num_samples):
        i = N - n - 1
        j = random.randrange(i)

        # swap a[j] and a[i] 
        a_j = modified_entries[j] if j in modified_entries else j 
        a_i = modified_entries[i] if i in modified_entries else i

        if a_i != j:
            modified_entries[j] = a_i   
        elif j in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(j)

        if a_j != i:
            modified_entries[i] = a_j 
        elif i in modified_entries:   # no need to store the modified value if it is the same as index
            modified_entries.pop(i)
        seq.append(a_j)
    return seq
Dai
źródło
0

Używanie LINQ z dużymi listami (gdy kosztowne jest dotknięcie każdego elementu) ORAZ jeśli możesz żyć z możliwością duplikatów:

new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))

Do mojego użytku miałem listę 100 000 elementów, a ponieważ były one wyciągane z bazy danych, skróciłem czas o połowę (lub lepiej) w porównaniu do rnd na całej liście.

Posiadanie dużej listy znacznie zmniejszy szanse na duplikaty.

Wolf5
źródło
To rozwiązanie może mieć powtarzające się elementy !! Losowy na liście dołków może nie.
AxelWass,
Hmm. Prawdziwe. Gdzie go używam, to jednak nie ma znaczenia. Zredagowałem odpowiedź, aby to odzwierciedlić.
Wolf5,
-1

To rozwiąże Twój problem

var entries=new List<T>();
var selectedItems = new List<T>();


                for (var i = 0; i !=10; i++)
                {
                    var rdm = new Random().Next(entries.Count);
                        while (selectedItems.Contains(entries[rdm]))
                            rdm = new Random().Next(entries.Count);

                    selectedItems.Add(entries[rdm]);
                }
Cyrille
źródło
Chociaż może to odpowiedzieć na pytanie, powinieneś edytować swoją odpowiedź, aby zawierała wyjaśnienie, w jaki sposób ten blok kodu odpowiada na pytanie. Pomaga to zapewnić kontekst i sprawia, że ​​twoja odpowiedź jest znacznie bardziej przydatna dla przyszłych czytelników.
Hoppeduppeanut