Выбор N случайных предметов из группы не должен иметь ничего общего с order ! Случайность связана с непредсказуемостью, а не с перетасовкой позиций в группе. Все ответы, связанные с каким-то порядком, обязательно будут менее эффективными, чем те, которые этого не делают. Поскольку эффективность здесь является ключевым фактором, я опубликую то, что не сильно меняет порядок элементов.
1) Если вам нужно true случайные значения, что означает, что нет ограничений на выбор элементов (т. Е. Один раз выбранный элемент может быть повторно выбран):
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);
}
Если все дело в производительности с десятками тысяч элементов в списке, которые нужно повторять 10000 раз, то вы можете захотеть иметь более быстрый случайный класс , чем System.Random, но я не думаю, что это большое дело, учитывая, что последнее, скорее всего, никогда не является узким местом, оно достаточно быстрое ...
Редактировать: Если вам нужно изменить порядок возвращаемых предметов, то нет ничего, что могло бы превзойти подход Дхакима Фишера-Йейтса - короткий, приятный и простой.