Shuffle utilizza IComparer
https://stackoverflow.com/questions/557911
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Prima di tutto, io so circa il riordino Fisher-Yates. Ma consente di dire per amor di argomenti che voglio per consentire all'utente di scegliere un'opzione di ordinamento da un elenco a discesa. La lista dovrebbe includere un'opzione "Random". Sulla base del risultato della loro selezione voglio solo sostituire in un'istanza IComparer per il mio tipo. Quale sarebbe l'IComparer simile?
Google porta in primo piano una pletora di risultati difettosi che tutti prendono questa 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);
}
}
Tuttavia, che l'attuazione è parziale e sarà anche un'eccezione in alcune circostanze. La polarizzazione può essere dimostrata con il seguente codice:
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;
}
Quindi, come si potrebbe implementare un IComparer<T> casuale che ha risolto questi problemi? E 'consentito richiedere ogni chiamata a .Sort() di utilizzare un'istanza IComparer separata, come io non vedo altro modo per fare questo: gli elementi deve essere confrontato con qualche altro, il valore realmente casuale, ma che valore di deve anche essere coerente per un elemento all'interno di una data operazione di ordinamento.
Ho un inizio qui , ma è stato pubblicato in fretta, è molto lento, e non ha nemmeno tornare tutti i possibili tipi (test mostra che lo fa almeno eliminare la discriminazione, se don 't contare le opzioni mancanti). Non mi aspetto O (n) le prestazioni come Fisher-Yates, ma io voglio qualcosa di ragionevole (n log n per una piccola-ish n), e non mi aspetto che mostra tutti i possibili tipi. Purtroppo, tale collegamento è l'attuale risposta accettata per la sua domanda e quindi spero di essere in grado di sostituirlo con qualcosa di un po 'meglio.
Se non altro, io voglio che questo sia una calamita per tutte quelle query di Google alla ricerca di una soluzione-IComparable che finiranno qui invece che da qualche altra parte dicendo loro di utilizzare la versione corretta.
Soluzione 2
Un suggerimento ho avuto altrove era quello di creare un'interfaccia IArranger separato che descrive una singola operazione a Disponi una collezione. Questo può funzionare dove IComparer / IComparable non può perché opera su un'intera collezione, invece di singoli elementi. Potrebbe sembrare qualcosa di simile:
public interface IArranger<T>
{
IEnumerable<T> Arrange(IEnumerable<T> items);
}
Poi ho potuto implementare un Shuffle dall'interfaccia IArranger utilizzando un apposito algoritmo di Fisher-Yates, e hanno anche implementazioni che avvolgono ogni varietà IEnumerable.Sort()/IComparable/IComparer aggiuntivi che mi preoccupo. Questo potrebbe essere simile a questa:
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);
}
}
o
//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);
}
}
o
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;
}
}
Per un ultimo passo, ho aggiungere il supporto per questo a qualsiasi IEnumerable tramite un metodo di estensione. Poi è ancora ottenere il semplice algoritmo scambio di run-time, si ha una migliore implementazione dell'algoritmo shuffle, e il codice per utilizzare ci si sente naturale:
public static IEnumerable<T> Arrange(this IEnumerable<T> items, IArranger<T> arranger)
{
return arranger.Arrange(items);
}
Altri suggerimenti
Sono rimasto un po 'sorpreso nel questa discussione quanti risposte errate sono state inviate. Solo per il bene degli altri che arrivano a una soluzione simile a quella pubblicata dal PO, il seguente codice guarda corretta:
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);
}
Tuttavia, il codice genererà un'eccezione di tanto in tanto, ma non sempre. Questo è ciò che rende divertente il debug :) Se lo si esegue abbastanza volte, o eseguire la procedura di sorta in un ciclo di 50 o giù di lì volte, si otterrà un errore che indica:
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: ''.
In altre parole, il quick sort confrontato qualche numero x a se stessa e ha ottenuto un risultato diverso da zero. La soluzione più ovvia per il codice sarebbe scrivere:
Array.Sort<int>(nums, (x, y) =>
{
if (x == y) return 0;
else return r.NextDouble() < 0.5 ? 1 : -1;
});
Ma anche questo non funziona, perché ci sono occasioni in cui .NET confronta 3 numeri uno contro l'altro che restituiscono risultati inconsistenti, come A> B, B> C, e C> A (oops!). Non importa se si utilizza un Guid, GetHashCode, o qualsiasi altro ingresso generato in modo casuale, una soluzione come quella mostrata qui sopra è ancora sbagliata.
Con questo detto, Fisher-Yates è il modo standard di mischiare array, quindi non c'è vera ragione per utilizzare IComparer in primo luogo. Fisher-Yates è O (n), mentre qualsiasi implementazione utilizzando IComparer utilizza un Quicksort sedere le scene che ha un tempo di complessità di O (n log n). Non c'è proprio nessuna buona ragione per non utilizzare il noto, efficiente, algoritmo standard per risolvere questo tipo di problema.
Tuttavia, se proprio insistete utilizzando un IComparer e un rand, quindi applicare i dati casuali prima si ordina. Ciò richiede una proiezione dei dati su un altro oggetto in modo da non perdere i vostri dati casuali:
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);
}
}
}
O ottenere LINQy con la vostra parte malvagia:
Random r = new Random();
var nums = from x in Enumerable.Range(0, 1000)
orderby r.NextDouble()
select x;
IComparer da un ritorno a zero ad un certo punto (a parità istanze di T), rende matematicamente impossibile creare un'IComparer generico che imitare una Fisher-Yates Shuffle statisticamente. Ci sarà sempre un bias. Per un vero e proprio riordino, che non avevo mai vuole forzare la restituzione di un valore particolare.
Come 'bout ordinamento in base a un campo nascosto, che è pre-assegnato un valore casuale?
Per seguire su un'idea di James Curran: lasciare che l'IComparer mantenere la "ordinato" valori come un elenco; se si verifica un nuovo valore, inserirlo nella lista in una posizione casuale; confrontare con indice di lista. Ottimizzare mantenendo l'elenco come un albero bilanciato o qualcosa del genere. Ogni istanza di un tale IComparer manterrà un ordinamento costante e casuale in modo da avere la scelta di lasciare il vostro ordinamenti causali essere costantemente lo stesso ordine casuale o uno diverso ogni volta. piccola modifica sarà anche permettere elementi uguali per essere "ordinati" in diverse posizioni di ordinazione, se si preferisce leggere "random" in questo modo.
Un tentativo interessante. Molto probabilmente un cattivo uso / abuso di IComparer.
Si sta tentando di fare una sorta ponderata casuale utilizzando un meccanismo che non è stato costruito per questo scopo.
Perché non implementare una propria routine di ordinamento e il proprio operatore di confronto? Ho la sensazione che anche questo sarebbe insufficiente.
Non farlo.
Tutti gli algoritmi proposti finora introdurre un certo grado di distorsione nell'uscita (alcuni grandi di altri).
@Princess e @Luke propongono memorizzare un numero casuale accanto ai dati. Tuttavia, poiché v'è la possibilità che due qualsiasi di questi numeri casuali potrebbero avere lo stesso valore di un altro, l'ordinamento tra questi due elementi saranno deterministico polarizzato
Il caso peggiore di questo sarebbe se la routine di ordinamento è "stabile" (cioè che gli oggetti che sono considerati uguali sono sempre uscita nello stesso ordine in cui sono stati immessi in). Array.Sort non accade a essere stabile (utilizza QuickSort internamente), ma v'è ancora una polarizzazione che si verifica quando due oggetti hanno lo stesso valore che dipende da dove sono in ingresso (e in particolare dove sono relativi al QuickSort di perno).
Per quanto lo spazio delle chiavi per questo casuali numero aumenta, la probabilità di una collisione va verso il basso (con una buona fonte di casualità), ma tenere a mente che, come il numero di valori che si sta Ordinamento sale, il paradosso del compleanno impone che il probabilita di almeno una coppia tra loro collisione va molto rapidamente.
Per una chiave intera, ci sono 2 ^ 32 valori univoci per la chiave e anche supponendo che vi sia una perfetta distribuzione di valori casuali, con 75.000 righe, v'è una probabilità del 50% che ci sarà una collisione. Wikipedia .
L'approccio hash crittografico che avete proposto potenzialmente ha un grande spazio delle chiavi abbastanza (160) bit per rendere la probabilità di una collisione trascurabile, ma l'algoritmo si decompone tutti che la casualità di nuovo verso il basso per un singolo int prima di poter realmente fare il confronto che nega il beneficio di tale spazio delle chiavi più grande.
Il tuo approccio migliore è quello di associare un valore distinto "sortOrder" con ciascuno dei vostri elementi di dati mischiare questi valori utilizzando un algoritmo collaudato, e poi ordinare i risultati per quel valore.
Se si utilizza Array.Sort, v'è un sovraccarico che prende una serie di "chiavi" e una serie di "valori". La matrice di chiavi è ordinato normalmente, ma ogni volta che un valore nella matrice di chiavi viene spostato, la voce corrispondente nella matrice valori è anche spostato.
Qualcosa di simile:
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);
