Перемешать с помощью IComparer
https://stackoverflow.com/questions/557911
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Прежде всего, я знаю о перетасовке Фишер-Йейтс.Но скажем ради аргумента, что я хочу разрешить пользователю выбирать вариант сортировки из раскрывающегося списка.Этот список будет включать опцию «Случайный».Основываясь на результате их выбора, я просто хочу заменить свою сортировку экземпляром IComparer.Как будет выглядеть IComparer?
Google выдает множество ошибочных результатов, которые все имеют следующую форму:
public class NaiveRandomizer<T> : IComparer<T>
{
private static Random rand = new Random();
public int Compare(T x, T y)
{
return (x.Equals(y))?0:rand.Next(-1, 2);
}
}
Однако эта реализация предвзята и в некоторых случаях даже выдает исключение.Смещение можно продемонстрировать с помощью следующего кода:
void Test()
{
Console.WriteLine("NaiveRandomizer Test:");
var data = new List<int>() {1,2,3};
var sortCounts = new Dictionary<string, int>(6);
var randomly = new NaiveRandomizer<int>();
for (int i=0;i<10000;i++)
{ //always start with same list, in _the same order_.
var dataCopy = new List<int>(data);
dataCopy.Sort(randomly);
var key = WriteList(dataCopy);
if (sortCounts.ContainsKey(key))
sortCounts[key]++;
else
sortCounts.Add(key, 1);
}
foreach (KeyValuePair<string, int> item in sortCounts)
Console.WriteLine(item.Key + "\t" + item.Value);
}
string WriteList<T>(List<T> list)
{
string delim = "";
string result = "";
foreach(T item in list)
{
result += delim + item.ToString();
delim = ", ";
}
return result;
}
Так как же можно реализовать случайное IComparer<T> это решило эти проблемы?Допускается требовать каждый вызов .Sort() использовать отдельный экземпляр IComparer, поскольку я не вижу другого способа сделать это:предметы должен сравниваться с использованием какого-то другого, действительно случайного значения, но это значение должен также быть согласованным для элемента в рамках данной операции сортировки.
у меня есть начало здесь, но это было опубликовано в спешке, это очень сильно медленный и даже не возвращает все возможные варианты (тестирование показывает, что оно, по крайней мере, устраняет предвзятость, если не учитывать недостающие варианты).Я не ожидаю производительности O(n), как у Фишера-Йейтса, но мне нужно что-то разумное (n log n для небольшого n), и я ожидаю, что оно покажет все возможные виды.К сожалению, эта ссылка в настоящее время является общепринятым ответом на этот вопрос, поэтому я надеюсь заменить ее чем-то немного лучше.
По крайней мере, я хочу, чтобы это было магнитом для всех тех запросов Google, которые ищут решение IComparable - чтобы они оказались здесь, а не где-то еще, говоря им использовать неправильную версию.
Решение 2
Одно из предложений, которое я получил в другом месте, заключалось в создании отдельного интерфейса 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);
}
Другие советы
Я был несколько удивлен эта тема сколько неправильных ответов было опубликовано.Просто ради тех, кто предложит решение, подобное тому, которое опубликовал ОП, следующий код выглядит правильный:
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's 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 сравнивает три числа друг с другом и возвращает противоречивые результаты, например A > B, B > C и C > A (упс!).Независимо от того, используете ли вы Guid, GetHashCode или любой другой случайно сгенерированный ввод, решение, подобное показанному выше, все равно неверно.
С учетом вышесказанного, Fisher-Yates — это стандартный способ перетасовки массивов, поэтому нет никакой реальной причины использовать IComparer.Фишер-Йейтс - это O (n), тогда как любая реализация с использованием IComparer использует быструю сортировку за кулисами, имеющую временную сложность 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;
IComparer требующий нулевой доход в какой-то момент (для равных экземпляров T) делает его математически невозможно создать универсальный IComparer, который будет статистически имитировать перемешивание Фишера-Йейтса.Всегда будет предвзятость.Для настоящего перемешивания вам никогда не понадобится заставлять его возвращать какое-либо конкретное значение.
А как насчет сортировки по скрытому полю, которому заранее присвоено случайное значение?
Продолжая идею Джеймса Каррена:пусть IComparer поддерживает «отсортированные» значения в виде списка;если появляется новое значение, вставить его в список в случайном месте;сравнить по индексу списка.Оптимизируйте, сохраняя список в виде сбалансированного дерева или чего-то в этом роде.Каждый экземпляр такого IComparer будет поддерживать последовательный и случайный порядок сортировки, поэтому у вас есть возможность выбрать, чтобы ваша случайная сортировка каждый раз имела один и тот же случайный порядок или другой.Небольшая модификация даже позволит «сортировать» одинаковые элементы по разным позициям, если вы предпочитаете читать «случайно».
Интересное занятие.Скорее всего, неправильное использование IComparer.
Вы пытаетесь выполнить случайную взвешенную сортировку, используя механизм, который не был создан для этой цели.
Почему бы не реализовать собственную процедуру сортировки и собственный компаратор?У меня такое ощущение, что даже этого будет недостаточно.
Не делай этого.
Все предложенные до сих пор алгоритмы вносят в выходные данные некоторую погрешность (некоторые больше, чем другие).
@Princess и @Luke предлагают хранить вместе с данными случайное число.Однако поскольку существует вероятность того, что любые два из этих случайных чисел могут иметь то же значение, что и другое, порядок сортировки между этими двумя элементами будет детерминированно смещенным.
Худшим случаем для этого было бы, если бы процедура сортировки была «стабильной» (то есть объекты, которые считаются равными, всегда выводятся в том же порядке, в котором они были введены).Array.Sort не является стабильным (в нем используется QuickSort), но все же существует смещение, которое возникает, когда два элемента имеют одинаковое значение, которое зависит от того, где они находятся на входе (и, в частности, где они находятся относительно QuickSort's). вращаться).
По мере увеличения пространства ключей для этого случайного числа вероятность столкновения снижается (при хорошем источнике случайности), но имейте в виду, что по мере увеличения количества сортируемых значений парадокс дня рождения диктует, что вероятность хотя бы одна пара из них столкнулась очень быстро.
Для целочисленного ключа существует 2 ^ 32 уникальных значения ключа, и даже если предположить, что существует совершенно равномерное распределение случайных значений с 75 000 строк, существует 50% вероятность того, что произойдет столкновение. Википедия.
Предложенный вами подход к криптографическому хэшированию потенциально имеет достаточно большое пространство ключей (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);
