Embaralhar usando IComparer
https://stackoverflow.com/questions/557911
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Primeiro de tudo, eu sei sobre o shuffle Fisher-Yates. Mas vamos dizer por causa de argumentos que eu quero permitir que o usuário escolha uma opção de ordenação de uma lista suspensa. Esta lista incluiria uma opção de "Random". Com base no resultado da sua selecção Eu só quero substituto em uma instância IComparer para o meu tipo. Qual seria a aparência IComparer como?
O Google traz uma infinidade de resultados falhos que todos têm esta forma:
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);
}
}
No entanto, que a implementação é tendenciosa e ainda vai lançar uma exceção em algumas circunstâncias. A polarização pode ser demonstrada com o código seguinte:
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;
}
Então, como você poderia implementar um IComparer<T> aleatório que resolveu esses problemas? É permitida a exigir que cada chamada para .Sort() para usar uma instância IComparer separado, como eu não vejo outra maneira de fazer isso: itens deve ser comparados usando algum outro valor, verdadeiramente aleatório, mas que valor deve também ser consistente para um item dentro de uma dada operação de classificação.
Eu tenho um início aqui , mas foi publicada em pressa, é extremamente lento, e nem sequer voltar todos os tipos possíveis (teste mostra que ele, pelo menos, eliminar o preconceito, se você don 't contar as opções ausentes). Eu não espero que O (n) o desempenho como Fisher-Yates, mas eu quero algo razoável (n log n para um pequeno-ish n), e eu espere que ele para mostrar todos os tipos possíveis. Infelizmente, essa ligação é a resposta aceito atual para a sua pergunta e por isso estou esperando para ser capaz de substituí-lo por algo um pouco melhor.
Se nada mais, eu quero que este seja um ímã para todas essas consultas do Google à procura de uma solução-IComparable que eles vão acabar aqui em vez de em outro lugar dizendo-lhes para usar a versão incorreta.
Solução 2
Uma sugestão que eu tenho em outros lugares era criar uma interface IArranger separado que descreve uma única operação para Organizar uma coleção. Isso pode funcionar onde IComparer / IComparable não pode porque opera em uma coleção inteira, em vez de itens individuais. Pode parecer algo como isto:
public interface IArranger<T>
{
IEnumerable<T> Arrange(IEnumerable<T> items);
}
Então eu poderia implementar uma Shuffle do IArranger interface usando um algoritmo de Fisher-Yates adequada, e também ter implementações que envolva cada variedades IEnumerable.Sort()/IComparable/IComparer adicionais que me interessa. Isso poderia ser algo como isto:
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);
}
}
ou
//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);
}
}
ou
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;
}
}
Para a etapa final, eu adicionar suporte para isso a qualquer IEnumerable através de um método de extensão. Então você ainda obter o simples algoritmo de troca de tempo de execução, você terá uma melhor implementação do algoritmo shuffle, eo código para usá-lo se sente natural:
public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
return arranger.Arrange(items);
}
Outras dicas
Eu estava um pouco surpreso em esta discussão quantas respostas erradas foram postados. Apenas para o bem dos outros que vêm com uma solução semelhante ao publicado pela OP, o seguinte código aparência correta:
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);
}
No entanto, o código irá lançar uma exceção ocasionalmente, mas nem sempre. É isso que faz com que seja divertido para depurar :) Se você executá-lo várias vezes, ou executar o procedimento de ordenação em um loop de 50 ou mais vezes, você receberá um erro informando:
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: ''.
Em outras palavras, a rápida tipo comparado algum número x a si mesmo e tem um resultado diferente de zero. A solução óbvia para o código seria escreve:
Array.Sort<int>(nums, (x, y) =>
{
if (x == y) return 0;
else return r.NextDouble() < 0.5 ? 1 : -1;
});
Mas mesmo isso não funciona, porque há ocasiões em .NET compara 3 números uns contra os outros que retornam resultados inconsistentes, tais como A> B, B> C e C> A (oops!). Não importa se você usar um Guid, GetHashCode, ou qualquer outra entrada gerada aleatoriamente, uma solução como a mostrada acima ainda está errado.
Com isso dito, Fisher-Yates é a maneira padrão de baralhar matrizes, então não há nenhuma razão real para usar IComparer em primeiro lugar. Fisher-Yates é O (n) enquanto que qualquer aplicação usando IComparer utiliza um quick Behinds as cenas que tem um tempo-complexidade de O (N log N). Simplesmente não há uma boa razão para não usar o bem conhecido, eficiente algoritmo, padrão para resolver este tipo de problema.
No entanto, se você realmente insistir em usar um IComparer e uma margem, em seguida, aplicar os seus dados aleatórios antes você classificar. Isto requer uma projeção dos dados em outro objeto para que você não perca seus dados aleatórios:
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);
}
}
}
ou obter LINQy com seu auto mau:
Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
orderby r.NextDouble()
select x;
IComparer exigindo uma remuneração zero em algum ponto (para casos iguais de T), torna matematicamente impossível criar um IComparer genérico que vai imitar a Fisher-Yates shuffle estatisticamente. Haverá sempre um viés. Para uma reprodução aleatória real, você nunca quer forçá-lo a retornar qualquer valor particular.
Como 'bout a classificação com base em um campo oculto, que é pré-atribuído um valor aleatório?
Para dar seguimento a ideia de James Curran: deixar o IComparer manter o "ordenado" valores como uma lista; Se um novo valor ocorre, insira-o na lista em uma posição aleatória; comparar pelo índice de lista. Optimize, mantendo a lista como uma árvore equilibrada ou algo assim. Cada instância de tal IComparer manterá uma ordem de classificação consistente e aleatório assim que você tem a opção de deixar o seu aleatória classificando ser consistentemente a mesma ordem aleatória ou um diferente a cada vez. pequena modificação vai mesmo permitir que elementos iguais para ser "classificado" em diferentes posições de ordenação, se você preferir ler "aleatório" dessa forma.
Um esforço interessante. O mais provável é um mau uso / abuso de IComparer.
Você está tentando fazer uma espécie ponderada aleatória usando um mecanismo que não foi construído para o efeito.
Por que não implementar sua própria rotina de classificação e seu próprio comparador? Tenho a sensação de que, mesmo que seria insuficiente.
Não fazê-lo.
Todos os algoritmos propostos até agora introduzir algum tipo de viés para a saída (alguns maiores do que outros).
@Princess e @Luke propõem armazenar um número aleatório ao lado dos dados. No entanto, porque há uma possibilidade de que quaisquer dois destes números aleatórios poderia ter o mesmo valor que outro, a ordem de classificação entre esses dois itens serão deterministically tendenciosa
O pior caso para isso seria se a rotina de classificação é "estável" (que é que os objetos que são considerados iguais são sempre de saída na mesma ordem em que foram digitados in). não Array.Sort não acontecer de ser estável (ele usa QuickSort internamente), mas ainda há um viés que ocorre sempre que dois itens têm o mesmo valor que depende de onde eles estão na entrada (e, especificamente, onde eles estão em relação ao QuickSort de pivô).
Como o keyspace para este números aleatórios aumenta, a probabilidade de uma colisão vai para baixo (com uma boa fonte de aleatoriedade), mas tenha em mente que, como o número de valores que estão classificando sobe, os ditames aniversário paradoxo que o likelyhood de pelo menos um par entre eles colidir sobe muito rapidamente.
para uma chave de número inteiro, existem 2 ^ 32 valores únicos para a chave e ainda supondo que existe uma distribuição perfeitamente uniforme de valores aleatórios, com 75.000 linhas, existe uma probabilidade de 50% que não haverá uma colisão. Wikipedia .
A abordagem hash criptográfico que você propôs potencialmente tem um keyspace grande o suficiente (160) bits para fazer a chance de um insignificante colisão, mas o seu algoritmo decompõe tudo isso aleatoriedade de volta para baixo a um único int antes de realmente fazer as que nega comparar o benefício dessa maior keyspace.
Seu melhor abordagem é associar um valor distinto "sortOrder" com cada um dos seus itens de dados embaralhar esses valores usando um algoritmo comprovado, e, em seguida, ordenar os resultados por esse valor.
Se você estiver usando Array.Sort, há uma sobrecarga que leva um conjunto de "chaves" e um conjunto de "valores". A matriz de teclas é ordenada normalmente, mas sempre que um valor na matriz de teclas é movida, a entrada correspondente na matriz de valores também é movido.
Algo como:
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);
