Выберите N случайных элементов из List<T> в C#
https://stackoverflow.com/questions/48087
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Мне нужен быстрый алгоритм для выбора 5 случайных элементов из общего списка.Например, я хотел бы получить 5 случайных элементов из List<string>.
Решение
Перебрать и для каждого элемента сделать вероятность выбора = (нужное число)/(оставшееся число)
То есть, если у вас 40 предметов, вероятность выбора первого будет 5/40.Если да, то вероятность следующего будет 4/39, в противном случае — 5/39.К тому времени, как вы дойдете до конца, у вас будут 5 предметов, а зачастую и все они будут у вас раньше.
Другие советы
Использование linq:
YourList.OrderBy(x => rnd.Next()).Take(5)
public static List<T> GetRandomElements<T>(this IEnumerable<T> list, int elementsCount)
{
return list.OrderBy(arg => Guid.NewGuid()).Take(elementsCount).ToList();
}
На самом деле это более сложная проблема, чем кажется, главным образом потому, что многие математически правильные решения не позволят вам реализовать все возможности (подробнее об этом ниже).
Во-первых, вот несколько простых в реализации и правильных, если у вас есть действительно генератор случайных чисел:
(0) Ответ Кайла — O(n).
(1) Сгенерируйте список из n пар [(0, rand), (1, rand), (2, rand), ...], отсортируйте их по второй координате и используйте первые k (для вас k =5) индексы для получения случайного подмножества.Я думаю, это легко реализовать, хотя на это уходит время O(n log n).
(2) Создайте пустой список s = [], который вырастет до индексов k случайных элементов.Выберите случайное число r из {0, 1, 2, ..., n-1}, r = rand % n, и добавьте его к s.Далее возьмем r = rand % (n-1) и вставим s;добавьте в r # элементов меньше, чем в s, чтобы избежать коллизий.Затем возьмите r = rand % (n-2) и сделайте то же самое и т. д.пока у вас не будет k различных элементов в s.Это имеет худшее время работы O(k^2).Итак, для k << n это может быть быстрее.Если вы сохраняете сортировку s и отслеживаете, какие у него смежные интервалы, вы можете реализовать это за O(k log k), но это требует больше работы.
@Кайл - ты прав, если подумать, я согласен с твоим ответом.Сначала я прочитал это наспех и ошибочно подумал, что вы указываете последовательно выбирать каждый элемент с фиксированной вероятностью k/n, что было бы неправильно - но ваш адаптивный подход кажется мне правильным.Извини за это.
Хорошо, а теперь самое интересное:асимптотически (при фиксированном росте k, n) существует n^k/k!выбор подмножества k элементов из n элементов [это приближение (n выбирает k)].Если n велико, а k не очень мало, то эти числа огромны.Лучшая длина цикла, на которую вы можете рассчитывать в любом стандартном 32-битном генераторе случайных чисел, составляет 2^32 = 256^4.Итак, если у нас есть список из 1000 элементов и мы хотим выбрать 5 случайным образом, стандартный генератор случайных чисел не сможет учесть все возможности.Однако, если вас устраивает выбор, который хорошо работает для меньших наборов и всегда «выглядит» случайным, тогда с этими алгоритмами все будет в порядке.
Приложение:Написав это, я понял, что правильно реализовать идею (2) сложно, поэтому я хотел уточнить этот ответ.Чтобы получить время O(k log k), вам нужна структура, подобная массиву, которая поддерживает поиск и вставку O(log m) — сбалансированное двоичное дерево может это сделать.Используя такую структуру для создания массива с именем s, вот некоторый псевдопитон:
# 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
Я предлагаю просмотреть несколько примеров, чтобы увидеть, насколько эффективно реализуется приведенное выше объяснение на английском языке.
Я думаю, что выбранный ответ правильный и довольно приятный.Однако я реализовал это по-другому, поскольку мне также хотелось, чтобы результат был в случайном порядке.
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);
}
Я только что столкнулся с этой проблемой, и еще несколько поисков в Google привели меня к проблеме случайного перетасовки списка: http://en.wikipedia.org/wiki/Fisher-Yates_shuffle
Чтобы совершенно случайно перетасовать ваш список (на месте), вы делаете это:
Чтобы перетасовать массив a из n элементов (индексы 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
Если вам нужны только первые 5 элементов, то вместо того, чтобы запускать i от n-1 до 1, вам нужно запустить его только до n-5 (т.е.:н-5)
Допустим, вам нужно k предметов,
Это становится:
for (i = n − 1; i >= n-k; i--)
{
j = random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
}
Каждый выбранный элемент меняется местами ближе к концу массива, поэтому выбранные k элементов являются последними k элементами массива.
Это занимает время O(k), где k — количество случайно выбранных элементов, которые вам нужны.
Кроме того, если вы не хотите изменять свой первоначальный список, вы можете записать все свои замены во временный список, перевернуть этот список и применить их снова, выполнив таким образом обратный набор замен и вернув вам исходный список без изменений. время работы O(k).
Наконец, для настоящего приверженца, если (n == k), вам следует остановиться на 1, а не на n-k, поскольку случайно выбранное целое число всегда будет 0.
Вы можете использовать это, но заказ будет происходить на стороне клиента.
.AsEnumerable().OrderBy(n => Guid.NewGuid()).Take(5);
От Драконы в алгоритме, интерпретация на 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--;
}
Этот алгоритм выберет уникальные индексы списка элементов.
Думал о комментарии @JohnShedletsky на принятый ответ относительно (перефраз):
вы должны иметь возможность сделать это за O(subset.Length), а не за O(originalList.Length)
По сути, вы должны иметь возможность генерировать subset случайные индексы, а затем выбрать их из исходного списка.
Метод
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()));
}
}
Если бы вы хотели быть еще более эффективными, вы, вероятно, использовали бы HashSet принадлежащий индексы, а не сами элементы списка (в случае, если у вас есть сложные типы или дорогостоящие сравнения);
Юнит-тест
И чтобы убедиться, что у нас нет столкновений и т. д.
[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);
}
}
}
Выбор N случайный элементы из группы не должны иметь ничего общего с заказ!Случайность – это непредсказуемость, а не перетасовка позиций в группе.Все ответы, касающиеся определенного порядка, обязательно будут менее эффективными, чем те, которые этого не делают.Поскольку эффективность здесь является ключевым моментом, я опубликую что-нибудь, что не слишком сильно изменит порядок элементов.
1) Если вам нужно истинный случайные значения, что означает отсутствие ограничений на выбор элементов (т. е. однажды выбранный элемент можно выбрать повторно):
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;
}
Если вы отключите флаг исключения, вы сможете выбирать случайные элементы любое количество раз.
Если у вас есть { 1, 2, 3, 4 }, то он может дать { 1, 4, 4 }, { 1, 4, 3 } и т. д. за 3 предмета или даже { 1, 4, 3, 2, 4 } за 5 пунктов!
Это должно быть довольно быстро, так как проверять нечего.
2) Если вам нужно индивидуальный членов группы без повторений, то я бы полагался на словарь (как уже отмечали многие).
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();
}
Код здесь немного длиннее, чем в других словарных подходах, потому что я не только добавляю, но и удаляю из списка, так что это своего рода два цикла.Здесь вы можете видеть, что у меня нет переупорядочен вообще что угодно, когда count становится равным source.Count.Это потому, что я верю случайность должна быть в возвращенный набор в целом.Я имею в виду, если ты хочешь 5 случайные предметы из 1, 2, 3, 4, 5, это не должно иметь значения, если это 1, 3, 4, 2, 5 или 1, 2, 3, 4, 5, но если вам нужно 4 предметы из одного и того же набора, то он должен непредсказуемо уступить в 1, 2, 3, 4, 1, 3, 5, 2, 2, 3, 5, 4 и т. д.Во-вторых, когда количество возвращаемых случайных элементов превышает половину исходной группы, их легче удалить source.Count - count предметы из группы чем добавление count предметы.По соображениям производительности я использовал source вместо sourceDict чтобы получить случайный индекс в методе удаления.
Итак, если у вас есть { 1, 2, 3, 4 }, это может закончиться { 1, 2, 3 }, { 3, 4, 1 } и т. д. для 3 предметов.
3) Если вам нужны действительно отдельные случайные значения из вашей группы с учетом дубликатов в исходной группе, вы можете использовать тот же подход, что и выше, но HashSet будет легче словаря.
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();
}
А randoms переменная становится HashSet чтобы избежать добавления дубликатов в самых редких из редких случаев, когда Random.Next может дать одно и то же значение, особенно если список входных данных небольшой.
Итак, { 1, 2, 2, 4 } => 3 случайных элемента => { 1, 2, 4 } и никогда { 1, 2, 2}
{ 1, 2, 2, 4 } => 4 случайных элемента => исключение!или { 1, 2, 4 } в зависимости от установленного флага.
Некоторые из методов расширения, которые я использовал:
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);
}
Если все дело в производительности, когда десятки тысяч элементов в списке необходимо повторять 10 000 раз, то вам может потребоваться более быстрый случайный класс чем System.Random, но я не думаю, что это имеет большое значение, учитывая, что последний, скорее всего, никогда не является узким местом, он достаточно быстрый..
Редактировать: Если вам также необходимо изменить порядок возвращаемых товаров, то нет ничего лучше, чем подход Фишера-Йейтса Дакима - коротко, мило и просто..
Простое решение, которое я использую (вероятно, не подходит для больших списков):Скопируйте список во временный список, затем в цикле случайным образом выберите элемент из временного списка и поместите его в список выбранных элементов, удаляя его из временного списка (чтобы его нельзя было выбрать повторно).
Пример:
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++;
}
Я объединил несколько приведенных выше ответов, чтобы создать метод расширения с ленивой оценкой.Мое тестирование показало, что подход Кайла (Order(N)) во много раз медленнее, чем использование набора Drzaus для предложения случайных индексов на выбор (Order(K)).Первый выполняет гораздо больше вызовов генератора случайных чисел, а также выполняет большее количество итераций по элементам.
Целями моего внедрения были:
1) Не реализуйте полный список, если задан IEnumerable, который не является IList.Если мне дана последовательность из миллиона элементов, я не хочу, чтобы у меня кончилась память.Используйте подход Кайла для онлайн-решения.
2) Если я могу сказать, что это IList, используйте подход Drzaus, но с изюминкой.Если K больше половины N, я рискую потерпеть неудачу, поскольку снова и снова выбираю множество случайных индексов и вынужден их пропускать.Таким образом, я составляю список индексов, которые НЕ следует сохранять.
3) Я гарантирую, что товары будут возвращены в том же порядке, в котором они были обнаружены.Алгоритм Кайла не требовал изменений.Алгоритм Дрзауса требовал, чтобы я не выдавал элементы в том порядке, в котором выбраны случайные индексы.Я собираю все индексы в SortedSet, а затем выдаю элементы в отсортированном порядке индексов.
4) Если K велико по сравнению с N и я инвертирую смысл набора, тогда я перечисляю все элементы и проверяю, нет ли индекса в наборе.Это означает, что я теряю время выполнения порядка (k), но, поскольку в этих случаях K близок к N, я не теряю много.
Вот код:
/// <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;
}
}
}
}
Я использую специализированный генератор случайных чисел, но вы можете просто использовать C#. Случайный если ты хочешь.(FastRandom был написан Колином Грином и является частью SharpNEAT.Его период составляет 2^128-1, что лучше, чем у многих ГСЧ.)
Вот модульные тесты:
[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));
}
}
Здесь у вас есть одна реализация, основанная на Фишер-Йейтс Шафл сложность алгоритма которого равна O(n), где n — подмножество или размер выборки, а не размер списка, как указал Джон Шедлецкий.
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;
}
}
Основываясь на ответе Кайла, вот моя реализация на С#.
/// <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 ;
}
Этот метод может быть эквивалентен методу Кайла.
Предположим, ваш список имеет размер n, и вам нужно k элементов.
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--;
}
}
Работает как шарм :)
-Алекс Гилберт
Исходя из ответа @ers, если кто-то беспокоится о возможных различных реализациях OrderBy, это должно быть безопасно:
// 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
Это лучшее, что я мог придумать при первом разрезе:
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;
}
Использование списка случайных чисел в диапазоне от 1 до общего количества в списке, а затем простое извлечение этих элементов из списка кажется лучшим способом, но использование словаря для обеспечения уникальности — это то, над чем я все еще размышляю.
Также обратите внимание, что я использовал список строк, при необходимости замените.
почему бы не что-то вроде этого:
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#
Это намного сложнее, чем можно было бы подумать.См. отличная статья "Перетасовка" от Джеффа.
Я написал очень короткую статью на эту тему, включая код C#:
Вернуть случайное подмножество из N элементов заданного массива
Цель:Выберите количество N элементов из источника коллекции без дублирования.Я создал расширение для любой общей коллекции.Вот как я это сделал:
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;
}
}
Недавно я сделал это в своем проекте, используя идею, похожую на Пункт Тайлера 1.
Я загружал кучу вопросов и случайным образом выбирал пять.Сортировка осуществлялась с помощью IComparer.
aВсе вопросы загружались в список сортировщика вопросов, который затем сортировался с помощью Функция сортировки списка и первые k элементов выбраны.
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;
}
}
}
Использование:
List<QuestionSorter> unsortedQuestions = new List<QuestionSorter>();
// add the questions here
unsortedQuestions.Sort(unsortedQuestions as IComparer<QuestionSorter>);
// select the first k elements
Вот мой подход (полный текст здесь http://krkadev.blogspot.com/2010/08/random-numbers-without-repetition.html ).
Он должен работать за O(K) вместо O(N), где K — количество нужных элементов, а N — размер списка на выбор:
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;
}
Это не так элегантно и эффективно, как принятое решение, но его можно быстро записать.Сначала переставьте массив случайным образом, затем выберите первые K элементов.В питоне
import numpy
N = 20
K = 5
idx = np.arange(N)
numpy.random.shuffle(idx)
print idx[:K]
Я бы использовал метод расширения.
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;
}
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;
}
}
Объем памяти:~количество
Сложность:О(счет2)
Когда N очень велико, обычный метод, который случайным образом перемешивает N чисел и выбирает, скажем, первые k чисел, может быть неприемлемым из-за пространственной сложности.Следующий алгоритм требует только O(k) как для временной, так и для пространственной сложности.
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
Использование LINQ с большими списками (когда прикасаться к каждому элементу дорого) И если вы можете жить с возможностью дублирования:
new int[5].Select(o => (int)(rnd.NextDouble() * maxIndex)).Select(i => YourIEnum.ElementAt(i))
Для моего использования у меня был список из 100 000 элементов, и из-за того, что они были извлечены из БД, я сократил время примерно вдвое (или лучше) по сравнению с rnd на весь список.
Наличие большого списка значительно уменьшит вероятность появления дубликатов.
