Сортировка по Random.Next ()

Question

В этот вопрос одно из предложений - отсортировать список по Random.Next ().

Я полагаю (возможно, неправильно), что он предлагает это

    public static IEnumerable<T> RandomSort<T>(this IEnumerable<T> items)
    {
        Random r = new Random();
        var a = items.ToArray();
        Array.Sort(a, (t1, t2) => (r.Next()%2==0)?-1 : 1);
        return a;
    }

(Да, уже есть функция Array.RandomShuffle, которую вы, очевидно, использовали бы вместо этого. Это не вопрос)

РЕДАКТИРОВАТЬ: постер разъяснил ответ. Он предлагал использовать пункт OrderBy

Вопрос в том, безопасен ли приведенный выше код (с использованием Array.Sort ()) для запуска?

Моя проблема в том, что это нарушит фундаментальный закон сортировки предикатов:

если (a Это даже не гарантирует, что если (a Приведет ли это вас к территории "неопределенного поведения"?

Например, он может зависнуть или упасть в бесконечный цикл в зависимости от последовательности чисел, возвращаемой Random ()?

Answer 1

Это полезное устройство для создания случайной перестановки списка. Для данной перестановки абсолютно верно, что если a до b и b до c, то a до c.

Еще один способ думать об этом так: если вы запускаете генератор случайных чисел с одним и тем же начальным числом каждый раз, то он всегда будет производить одинаковое упорядочение. Таким образом, вы можете думать о каждом семени генератора случайных чисел как о (возможно) различающемся порядке списка.

Это даже не гарантирует, что если (a

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

Answer 2

Просто для быстрого наблюдения, поскольку я только что попытался выполнить такую ​​рандомизированную сортировку, используя следующий код (чтобы некоторые базовые модульные тесты выполнялись в случайном порядке):

Action<object>[] tests = new Action<object>[] {
    delegate { SearchStringByTree(SOURCE, distinctor.Keys, out treeResults, out treeTicks); },
    delegate { SearchStringByIndexOf(SOURCE, distinctor.Keys, out indexOfResults, out indexOfTicks); },
    delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.UTF8, TERMS), out utf8Results, out utf8Ticks); },
    delegate { SearchBinaryByTree(Encoding.UTF8.GetBytes(SOURCE), GetBytes(Encoding.ASCII, TERMS), out asciiResults, out asciiTicks); }
};
Random r = new Random();
Array.Sort(tests, delegate { return r.Next(-1, 2); });

Iслучайным образом получил следующее ArgumentException:

IComparer (or the IComparable methods it relies upon) did not return zero 
when Array.Sort called x. CompareTo(x). x: ''  x's type: 'Action`1' 
The IComparer: 'System.Array+FunctorComparer`1[System.Action`1[System.Object]]'.

Кажется, что Sort утверждает равенство для элементов, которые, как он знает, совпадают (при условии object.ReferenceEquals), и, если Comparer не возвращает 0 для этихте, которые он знает, должны быть равны, он делает недействительным весь вид.

Answer 3

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

Текущая реализация LINQ, кажется, вычисляет все ключи сортировки заранее. Следующий код демонстрирует, что ключи сортировки получены последовательно и ровно один раз. Вероятно, это разумная реализация, поскольку она позволяет избежать проблемных сценариев, о которых вы беспокоитесь.

Тем не менее, я бы не стал полагаться на это поведение (оно не задокументировано в MSDN для Enumerable.OrderBy .

    public void Test()
    {
        int[] nums = Enumerable.Range(1, 100).ToArray();
        var sorted = from i in nums orderby Display(i) select i;
        sorted.ToArray();
    }

    private static int Display(int i)
    {
        Console.WriteLine(i);
        return i;
    }

(Приведенный выше код печатает последовательно от 1 до 100, показывая, как orderby оценивает ключи сортировки.)

Answer 4

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

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

Answer 5

Просто используйте случайный случайный порядок.

http://www.techtalkz.com/c-c-sharp/66613-shuffle-collection.html