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>.
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?
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.
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.
+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.
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.
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.
staticIEnumerable<SomeType>PickSomeInRandomOrder<SomeType>(IEnumerable<SomeType> someTypes,int maxCount){Random random =newRandom(DateTime.Now.Millisecond);Dictionary<double,SomeType> randomSortTable =newDictionary<double,SomeType>();foreach(SomeType someType in someTypes)
randomSortTable[random.NextDouble()]= someType;return randomSortTable.OrderBy(KVP => KVP.Key).Take(maxCount).Select(KVP => KVP.Value);}
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)
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 1do
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.
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ć):
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.
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.
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.
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
publicstaticclassEnumerableExtensions{publicstaticRandom randomizer =newRandom();// you'd ideally be able to replace this with whatever makes you comfortablepublicstaticIEnumerable<T>GetRandom<T>(thisIEnumerable<T>list,int numItems){return(listas 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 confusingpublicstaticIEnumerable<T>GetRandom<T>(this T[]list,int numItems){var items =newHashSet<T>();// don't want to add the same item twice; otherwise use a listwhile(numItems >0)// if we successfully added it, move onif( items.Add(list[randomizer.Next(list.Length)])) numItems--;return items;}// and because it's really fun; note -- you may get repetitionpublicstaticIEnumerable<T>PluckRandomly<T>(thisIEnumerable<T>list){while(true)yieldreturnlist.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]publicclassRandomizingTests:UnitTestBase{[TestMethod]publicvoidGetRandomFromList(){this.testGetRandomFromList((list, num)=>list.GetRandom(num));}[TestMethod]publicvoidPluckRandomly(){this.testGetRandomFromList((list, num)=>list.PluckRandomly().Take(num), requireDistinct:false);}privatevoid 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);}}}
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>publicstaticIEnumerable<TElem>TakeRandom<TElem>(thisIEnumerable<TElem> items,int k,int n){var r =newFastRandom();var itemsList = items asIList<TElem>;if(k >= n ||(itemsList !=null&& k >= itemsList.Count))foreach(var item in items)yieldreturn 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>)newHashSet<int>():(ISet<int>)newSortedSet<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))yieldreturn itemsList[itemIndex];}}else{// positions contains all the indices of elements to Take.foreach(var itemIndex in positions)yieldreturn 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){yieldreturn 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]publicclassTakeRandomTests{/// <summary>/// Ensure that when randomly choosing items from an array, all items are chosen with roughly equal probability./// </summary>[TestMethod]publicvoidTakeRandom_Array_Uniformity(){constint numTrials =2000000;constint expectedCount = numTrials/20;var timesChosen =newint[100];var century =newint[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]publicvoidTakeRandom_IEnumerable_Uniformity(){constint numTrials =2000000;constint expectedCount = numTrials /20;var timesChosen =newint[100];for(var trial =0; trial < numTrials; trial++){foreach(var i inRange(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));}privateIEnumerable<int>Range(int low,int count){for(var i = low; i < low + count; i++)yieldreturn i;}privatestaticvoidAssertBetween(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));}privatestaticvoidAssertBetween(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));}}
Czy w teście nie ma błędu? Masz, if (itemsList != null && k < n/2)co oznacza, że ifinvertSetzawsze 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 thisYourList.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
To najlepsze, co mogłem wymyślić przy pierwszym cięciu:
publicList<String> getRandomItemsFromList(int returnCount,List<String>list){List<String> returnList =newList<String>();Dictionary<int,int> randoms =newDictionary<int,int>();while(randoms.Count!= returnCount){//generate new random between one and total list countint randomInt =newRandom().Next(list.Count);// store this in dictionary to ensure uniquenesstry{
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 listif(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.
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 =newList<Object>();Random rnd =newRandom();Object o;int i =0;while(i <NumberOfSelectedItems){
o = temp[rnd.Next(temp.Count)];
selectedItems.Add(o);
temp.Remove(o);
i++;}
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.
publicstaticIEnumerable<T>GetRandomSample<T>(thisIList<T>list,int sampleSize){if(list==null)thrownewArgumentNullException("list");if(sampleSize >list.Count)thrownewArgumentException("sampleSize may not be greater than list count","sampleSize");var indices =newDictionary<int,int>();int index;var rnd =newRandom();for(int i =0; i < sampleSize; i++){int j = rnd.Next(i,list.Count);if(!indices.TryGetValue(j,out index)) index = j;yieldreturnlist[index];if(!indices.TryGetValue(i,out index)) index = i;
indices[j]= index;}}
Dim ar AsNewArrayListDim numToGet AsInteger=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 AsNewArrayListDim toAdd AsString=""For i =0To numToGet -1
toAdd = ar(CInt((ar.Count-1)*Rnd()))
randomListOfProductIds.Add(toAdd)'removefrom 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#
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:
publicstaticclassCollectionExtension{publicstaticIList<TSource>RandomizeCollection<TSource>(thisIList<TSource> source,int maxItems){int randomCount = source.Count> maxItems ? maxItems : source.Count;int?[] randomizedIndices =newint?[randomCount];Random random =newRandom();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 =newList<TSource>();foreach(int index in randomizedIndices)
result.Add(source.ElementAt(index));return result;}}
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.
List<QuestionSorter> unsortedQuestions =newList<QuestionSorter>();// add the questions here
unsortedQuestions.Sort(unsortedQuestions asIComparer<QuestionSorter>);// select the first k elements
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){thrownewIllegalStateException("Can not take "+ k +" elements from a list with "+ n +" elements");}List<T> result =newArrayList<T>(k);Map<Integer,Integer> used =newHashMap<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;}
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]
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.
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
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.
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=newList<T>();var selectedItems =newList<T>();for(var i =0; i !=10; i++){var rdm =newRandom().Next(entries.Count);while(selectedItems.Contains(entries[rdm]))
rdm =newRandom().Next(entries.Count);
selectedItems.Add(entries[rdm]);}
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.
Odpowiedzi:
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.
źródło
Korzystanie z linq:
źródło
YourList
masz dużo przedmiotów, ale chcesz wybrać tylko kilka. W tym przypadku nie jest to skuteczny sposób na zrobienie tego.źródło
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:
Proponuję przejrzeć kilka przykładowych przypadków, aby zobaczyć, jak skutecznie implementuje to powyższe angielskie wyjaśnienie.
źródło
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.
źródło
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):
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ę:
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.
źródło
Możesz z tego skorzystać, ale zamawianie będzie odbywać się po stronie klienta
źródło
From Dragons in the Algorithm , interpretacja w C #:
Algorytm ten wybierze unikalne wskazania listy pozycji.
źródło
var
wynikówneeded
iavailable
oba są liczbami całkowitymi, co dajeneeded/available
zawsze 0.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ć):
Jeśli wyłączysz flagę wyjątku, możesz wybierać losowe elementy dowolną liczbę razy.
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).
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
count
się równysource.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 z1, 2, 3, 4, 5
, nie powinno sprawa jeśli jego1, 3, 4, 2, 5
albo1, 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, 4
itd. 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 - count
elementy z grupy niż dodawaniecount
elementów. Ze względu na wydajność użyłemsource
zamiastsourceDict
tego losowego indeksu w metodzie usuwania.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
HashSet
będzie lżejsze niż słownik.randoms
Zmienna skierowany jestHashSet
do uniknięcia duplikaty dodawano w najrzadszych najrzadszych przypadkachRandom.Next
mogą wywoływać tę samą wartość, w szczególności, gdy listy wejście jest mała.Niektóre z metod rozszerzających, których użyłem:
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.
źródło
Zastanawiałem się nad komentarzem @JohnShedletsky na temat zaakceptowanej odpowiedzi dotyczącej (parafraza):
Zasadniczo powinieneś być w stanie wygenerować
subset
losowe indeksy, a następnie pobrać je z oryginalnej listy.Metoda
Jeśli chcesz być jeszcze bardziej efektywny, prawdopodobnie używać
HashSet
z 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.
źródło
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:
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:
źródło
if (itemsList != null && k < n/2)
co oznacza, żeif
invertSet
zawsze jest w środku,false
co oznacza, że logika nigdy nie jest używana.Wychodząc od odpowiedzi @ ers, jeśli ktoś obawia się o możliwe różne implementacje OrderBy, powinno to być bezpieczne:
źródło
To najlepsze, co mogłem wymyślić przy pierwszym cięciu:
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.
źródło
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:
źródło
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.
źródło
W oparciu o odpowiedź Kyle'a, oto moja implementacja C #.
źródło
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.
Działa jak marzenie :)
-Alex Gilbert
źródło
czemu nie coś takiego:
źródło
Jest to o wiele trudniejsze niż mogłoby się wydawać. Zobacz wspaniały artykuł „Shuffling” autorstwa Jeffa.
Napisałem na ten temat bardzo krótki artykuł zawierający kod C #:
Zwróć losowy podzbiór N elementów z danej tablicy
źródło
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:
źródło
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.
Stosowanie:
źródło
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:
źródło
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
źródło
Użyłbym metody rozszerzenia.
źródło
Pamięć: ~ liczba
Złożoność: O (liczba 2 )
źródło
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
źródło
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:
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.
źródło
To rozwiąże Twój problem
źródło