Как я могу улучшить этот метод рандомизации C#?

Question

Я думаю, что я решил использовать это как самый простой и способный к тестированию метод рандомизации списка, но было бы интересно услышать о любых улучшениях.

public static IList<T> RandomiseList<T>(IList<T> list, int seed) 
{ 
    Random random = new Random(seed); 
    List<T> takeFrom = new List<T>(list); 
    List<T> ret = new List<T>(takeFrom.Count); 

    while (takeFrom.Count > 0) 
    { 
     int pos = random.Next(0, takeFrom.Count - 1); 
     T item = takeFrom[pos]; 
     takeFrom.RemoveAt(pos); 
     ret.Add(item); 
    } 

    return ret; 
} 

Answer 1

Вы хотите перетасовать, и лучший способ сделать это является Fisher-Yates перетасовать:

public static IList<T> Randomise<T>(IList<T> list, int seed) 
{ 
    Random rng = new Random(seed); 

    List<T> ret = new List<T>(list);  
    int n = ret.Length;    
    while (n > 1) 
    { 
     n--;       
     int k = rng.Next(n + 1); 
     // Simple swap of variables 
     T tmp = list[k]; 
     ret[k] = ret[n]; 
     ret[n] = tmp; 
    } 
    return ret; 
} 

Answer 2

Нет статистики, чтобы поддержать это, но это будет казаться лучше, если ваше возвращение значение начинается как массив той же длины, что и список, а затем вы вставляете значения непосредственно в случайно сгенерированный индекс.

Answer 3

Это выглядит хорошо для меня. Обратите внимание, что вы получите немного более высокую производительность (особенно для больших списков), если вы инициализации ret с длиной list, так что список не должен быть перераспределены:

List<T> ret = new List<T>(list.Count); 

Answer 4

Не уверен, сколько из это будет, но будет иметь преимущество в производительности, если список большой, и вам понадобятся только первые несколько случайных элементов.

public static IEnumerable<T> RandomiseList<T>(IList<T> list, int seed) 
{ 
    Random random = new Random(seed); 
    List<T> takeFrom = new List<T>(list); 

    while (takeFrom.Count > 0) 
    { 
     int pos = random.Next(0, takeFrom.Count - 1); 
     T item = takeFrom[pos]; 
     takeFrom.RemoveAt(pos); 
     yield return item; 
    } 
} 

Удаляет необходимость в списке тем или даже переменной замены темпа.

Если бы я собирался использовать это много, я бы переписал его как метод расширения.

Answer 5

Мне понравилась идея Dennis Palmers о возврате перетасованного IEnumerable вместо того, чтобы перетасовывать список на месте, но использование метода RemoveAt делает его медленным. Вот альтернативный без метода RemoveAt:

public static IEnumerable<T> Shuffle<T>(IEnumerable<T> list, int seed) { 
    Random rnd = new Random(seed); 
    List<T> items = new List<T>(list); 
    for (int i = 0; i < items.Count; i++) { 
    int pos = rnd.Next(i, items.Count); 
    yield return items[pos]; 
    items[pos] = items[i]; 
    } 
} 

Я thried это с 10000 целых чисел, и это примерно в 30 раз быстрее.

Answer 6

Какие именно предложения вы ищете? эффективность? правильности? Вы упоминаете модульное тестирование ... Я думаю, что там, безусловно, может быть улучшение.

Я действительно помог разработать онлайн-игру и их механизм перетасовки. Я действительно не подозреваю, что производительность - это большая проблема, так как большинство алгоритмов, которые вы находите, по большому счету одинаковы. Я бы предложил следующие, но

a. создать случайный интерфейс

public interface IRandom 
{ 
    byte NextRandomByte(); 
} 

Все, что в настоящее время потребляет этот интерфейс теперь может быть издевался \ протестировано в управляемом режиме или окружающей среде. Вы действительно не хотите быть модульным тестированием по-настоящему случайных алгоритмов - вы не сможете проверить свои данные!

Что касается причины возврата байта, то байт, скорее всего, является наименьшей единицей случайности, которую вы могли бы захотеть. И не только это, но и при условии создания одного случайного байта, генерация последовательности из них и объединение их вместе - это простой способ создания еще более широкого диапазона случайных данных.

Конечно, вы должны быть осторожной introduing предвзятости к данным ...

б. Обеспечение качества данных путем уменьшения смещения в течение произвольных интервалов. Предполагая, что базовые данные являются равномерно случайными, любой интервал, который НЕ является фактором в 256, приведет к смещению.Рассмотрим это,

// 250 is not a factor of 256! 
byte a = random.NextRandomByte() % 250; // values 0-5 are biased! 

В предыдущем фрагменте значения 0-5 имеют 2/255 вероятность прийти вверх, в то время как значения 6-249 имеют 1/255 вероятность придумать. Это значительное смещение с течением времени. Один из подходов состоит в проверке количества, поступающего из генератора, и отбросить его, если он превышает допустимый диапазон

// continually generate random data until it is satisfactory 
for (byte r = random.NextRandomByte(); r > 250; r = random.NextRandomByte()) 
{ 
} 
byte a = r % 250; // r is guaranteed to be on [0, 250], no longer bias 

«Допустимый диапазон», может быть определено путем нахождения наибольшего кратного вашего интервала, который может быть представлен вашим значением тип. Более обобщенная форма

byte modulo; // specified as parameter 
byte biasThreshold = (byte.MaxValue/modulo) * modulo; 
for (; unbiasedValue >= biasThreshold;) 
{ 
    // generate value 
    unbiasedValue = random.NextRandomByte(); 
} 

И если вы хотите значения больше байт, просто сцепить значения вместе,

int modulo; // specified as parameter 
int biasThreshold = (int.MaxValue/modulo) * modulo; 
for (; unbiasedValue >= biasThreshold;) 
{ 
    // generate value 
    byte a = random.NextRandomByte(); 
    byte b = random.NextRandomByte(); 
    ... 
    int unbiasedValue = a << 24 + b << 16 + c << 8 + d; 
} 

гр. Потребляйте! Поместите свои алгоритмы или помощник в безгосударственном расширении или статических классах, как

// forgive my syntax, recalling from memory 
public static class IRandomExtensions 
{ 
    public int GetUnbiasedInteger (this IRandom random, int modulo) { } 
    public int GetUnbiasedUnsignedInteger (this IRandom random, uint modulo) { } 
    public int GetUnbiasedLong (this IRandom random, long modulo) { } 
    public int GetUnbiasedUnsignedLong (this IRandom random, ulong modulo) { } 
    ... 
} 

public static class IEnumerableExtensions 
{ 
    public IEnumerable<T> Shuffle<T>(this IEnumerable<T> items, IRandom random) 
    { 
     // shuffle away! 
     ... 
    } 

} 

Принятия решения или не выполнять их в качестве методов на интерфейсе или в качестве внешних методов [как я сделал] до вас - но сохранить в виду, что их методы-члены заставляют разработчиков повторять или дублировать код. Лично мне нравятся расширения. Они очень чисты. И сексуально.

int randomNumber = random.UnbiasedInteger (i - 1); 
List<int> shuffledNumbers = numbers.Shuffle (random); 

---

Очевидно все предшествующему не является обязательным, но облегчает модульное тестирование и улучшает общее качество ваших случайных данных.

Случайные и «честные» кости - очень интересная тема в целом. Если вас вообще интересует, я настоятельно рекомендую вам его когда-нибудь и проводить некоторые исследования. :)

Answer 7

Помните о рисках наивных алгоритмов перетасовки, которые выглядят хорошо, но не выдерживают тестирования!

Для примера приведено excellent article.