Перемешать с помощью IComparer

Ответ 1

Одним из предложений, которое я получил в другом месте, было создание отдельного интерфейса IArranger, который описывает одну операцию для Упорядочить коллекцию. Это может работать там, где IComparer/IComparable не может, потому что он работает со всей коллекцией, а не с отдельными элементами. Это может выглядеть примерно так:

public interface IArranger<T>
{
    IEnumerable<T> Arrange(IEnumerable<T> items);
}

Тогда я мог бы реализовать Shuffle из интерфейса IArranger с использованием правильного алгоритма Фишера-Йейса, а также иметь реализации, которые обертывают все дополнительные IEnumerable.Sort()/IComparable/IComparer варианты, которые меня волнуют. Это может выглядеть примерно так:

public class ComparerArranger<T> : IArranger<T>
{
    private IComparer<T> comparer;

    public ComparableArranger(IComparer<T> comparer)
    {
        this.comparer = comparer;
    }

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i, comparer);
    }
}

или

//uses the default Comparer for the type (Comparer<T>.Default)
public class TypeArranger<T> : IArranger<T> 
{
    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
       return items.OrderBy(i => i);
    }
}

или

public class ShuffleArranger<T> : IArranger<T>
{
    //naive implementation for demonstration
    // if I ever develop this more completely I would try to
    // avoid needing to call .ToArray() in here
    // and use a better prng
    private Random r = new Random();

    public IEnumerable<T> Arrange(IEnumerable<T> items)
    {
        var values = items.ToArray();

        //valid Fisher-Yates shuffle on the values array
        for (int i = values.Length; i > 1; i--)
        {
            int j = r.Next(i);
            T tmp = values[j];
            values[j] = values[i - 1];
            values[i - 1] = tmp;
        }
        foreach (var item in values) yield return item;
    }
}

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

public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
    return arranger.Arrange(items);
}

Ответ 2

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

int[] nums = new int[1000];
for (int i = 0; i < nums.Length; i++)
{
    nums[i] = i;
}

Random r = new Random();
Array.Sort<int>(nums, (x, y) => r.Next(-1, 2));

foreach(var num in nums)
{
    Console.Write("{0} ", num);
}

Однако код иногда генерирует исключение, но не всегда. Это делает его забавным для отладки. Если вы запустили его достаточно времени или выполните процедуру сортировки в цикле 50 или около того, вы получите сообщение об ошибке:

IComparer (or the IComparable methods it relies upon) did not return zero when Array.Sort called x. CompareTo(x). x: '0' x type: 'Int32' The IComparer: ''.

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

Array.Sort<int>(nums, (x, y) =>
    {
        if (x == y) return 0;
        else return r.NextDouble() < 0.5 ? 1 : -1;
    });

Но даже это не работает, потому что есть случаи, когда .NET сравнивает 3 числа друг против друга, которые возвращают несогласованные результаты, такие как A > B, B > C и C > A (oops!). Независимо от того, используете ли вы Guid, GetHashCode или любой другой случайный ввод, решение, подобное показанному выше, по-прежнему является неправильным.

С учетом сказанного, Fisher-Yates является стандартным способом перетасовки массивов, поэтому нет реальной причины использовать IComparer в первую очередь. Fisher-Yates - O (n), тогда как любая реализация, использующая IComparer, использует quicksort позади сцен, которые имеют сложность по времени O (n log n). Просто нет оснований не использовать хорошо известный, эффективный стандартный алгоритм для решения этой проблемы.

Однако, если вы действительно настаиваете на использовании IComparer и rand, тогда примените ваши случайные данные перед сортировкой. Для этого требуется проекция данных на другой объект, чтобы вы не потеряли свои случайные данные:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApplication1
{
    class Pair<T, U>
    {
        public T Item1 { get; private set; }
        public U Item2 { get; private set; }
        public Pair(T item1, U item2)
        {
            this.Item1 = item1;
            this.Item2 = item2;
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            Pair<int, double>[] nums = new Pair<int, double>[1000];
            Random r = new Random();
            for (int i = 0; i < nums.Length; i++)
            {
                nums[i] = new Pair<int, double>(i, r.NextDouble());
            }

            Array.Sort<Pair<int, double>>(nums, (x, y) => x.Item2.CompareTo(y.Item2));

            foreach (var item in nums)
            {
                Console.Write("{0} ", item.Item1);
            }

            Console.ReadKey(true);
        }
    }
}

Или получите LINQy с вашим плохим я:

Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
           orderby r.NextDouble()
           select x;

Ответ 3

IComparer, требующий нулевого возврата в какой-либо точке (для равных экземпляров T), делает математически невозможным создание общего IComparer, который будет имитировать статистический анализ Fisher-Yates Shuffle. Всегда будет предубеждение. Для реального перетасовки вы никогда не захотите заставить его возвращать какое-либо конкретное значение.

Ответ 4

Как сортировать бит на основе скрытого поля, которое предварительно назначено случайным значением?

Ответ 5

Чтобы следить за идеей Джеймса Каррана: пусть IComparer сохранит "отсортированные" значения в виде списка; если возникает новое значение, вставьте его в список в произвольной позиции; сравнить по списку. Оптимизируйте, поддерживая список как сбалансированное дерево или что-то в этом роде. Каждый экземпляр такого IComparer будет поддерживать последовательный и случайный порядок сортировки, поэтому у вас есть выбор позволить случайной сортировке быть последовательно одинаковым случайным порядком или другим. Малая модификация позволит даже "сортировать" одинаковые элементы в разных позициях заказа, если вы предпочитаете читать "случайные" таким образом.

Ответ 6

Интересная работа. Скорее всего, злоупотребление/злоупотребление IComparer.

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

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

Ответ 7

Не делай этого.

Все предложенные до сих пор алгоритмы вносят некоторый уклон в результат (несколько больше, чем другие).

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

Худший случай для этого был бы, если процедура сортировки является "стабильной" (то есть объекты, которые считаются равными, всегда выводятся в том же порядке, в каком они были введены). Array.Sort не является стабильным (он использует QuickSort внутренне), но есть все еще предвзятость, которая возникает, когда два элемента имеют одинаковое значение, которое зависит от того, где они находятся на входе (и, в частности, где они относятся к QuickSort поворот).

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

Для целочисленного ключа для ключа есть 2 ^ 32 уникальных значения, и даже если предположить, что существует абсолютно равномерное распределение случайных значений с 75 000 строк, вероятность того, что произойдет столкновение, будет на 50%. Wikipedia.

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

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

Если вы используете Array.Sort, есть перегрузка, которая принимает массив "ключей" и массив "значений". Массив ключей сортируется нормально, но всякий раз, когда значение в массиве ключей перемещается, также перемещается соответствующая запись в массиве значений.

Что-то вроде:

Something[] data;//populated somewhere
int[] keys = new int[data.Length];//or long if you might have lots of data
for(int i=0;i<keys.Length;++i) {
 keys[i] = i;
}

Shuffle(keys);

Array.Sort(keys, data);