Как я могу улучшить этот метод рандомизации 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

Вы хотите перемешать, и лучший способ сделать это - Фишер-Йейтс перемешивание:

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

Мне понравилась идея Денниса Палмерса возвращать перемешанный 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];
  }
}

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

Answer 3

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

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 4

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

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

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

public interface IRandom
{
    byte NextRandomByte ();
}

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

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

Конечно, вам нужно с осторожностью относиться к предвзятости в ваших данных ...

б. Гарантируйте качество данных, уменьшая смещение через произвольные интервалы. Предполагая, что лежащие в основе данные являются равномерно случайными, любой интервал, который НЕ является фактором 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);

---

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

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

Answer 5

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

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

Answer 6

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

Проверьте это отличная статья для примера.

Answer 7

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