Cosa c'è di sbagliato nel mio ordinamento?

Question

Prima di tutto devo specificare che sto lavorando in Unity 5.3 e che il nuovo MonoDevelop non mi permette di eseguire il debug. Unità appena si blocca :(

quindi ho una lista di "obiettivi" che ho bisogno di ordinare in base a 3 criteri:

1. primo dovrebbe essere elencato gli obiettivi di "attivi"
2. poi ordinato da difficoltà livello
3. finalmente in modo casuale per gli obiettivi dello stesso livello

ecco un mio codice:

public class Goal { 
    public int ID; 
    public int Level; 
    public bool Active; 
} 

... 

List<Goal> goals; 

goals.Sort((a, b) => { 
    // first chooses the Active ones (if any) 
    var sort = b.Active.CompareTo(a.Active); 
    if (sort == 0) { 
     // then sort by level 
     sort = (a.Level).CompareTo(b.Level); 
     // if same level, randomize. Returns -1, 0 or 1 
     return sort == 0 ? UnityEngine.Random.Range(-1, 2) : sort; 
    } else { 
     return sort; 
    } 
}); 

Quando eseguo questo codice a volte ottengo uno o più obiettivi attivi dopo quelli inattivi, ma non capisco perché.

Answer 1

Per funzionare correttamente, un algoritmo di ordinamento non deve dipendere dallo stato muting. Spiegazione del motivo per cui l'utilizzo di un generatore casuale durante il confronto dei valori non è una buona idea is given here.

Il problema può essere risolto in due modi:

Opzione 1: pre-elaborazione numeri casuali

var tmp = goals.Select(g=> new {goal = g, weight = rnd.NextDouble()}) 
     .OrderByDescending(t=>t.goal.Active) // Active first 
     .ThenBy(t=>t.goal.Level) 
     .ThenBy(t=>t.weight) 
     .Select(t=>t.goal) 
     .ToList(); 



    goals.Clear(); 
    goals.AddRange(tmp); 

Working sample

Opzione 2: Ordinamento poi rimescola legami

Random rnd = new Random(); 

Comparison<Goal> comparison = (a, b) => { 
// first chooses the Active ones (if any) 
var sort = b.Active.CompareTo(a.Active); 

if (sort == 0) { 
// then sort by level 
    return sort = (a.Level).CompareTo(b.Level); 
    } else 
{ 
    return sort; 
} 
}; 



int startIndex = 0; 
int endIndex = 0; 

goals.Sort(comparison); 

while (startIndex < goals.Count) 
{ 
    for (endIndex = startIndex + 1; endIndex < goals.Count; ++endIndex) 
    { 
     if (comparison(goals[startIndex], goals[endIndex]) != 0) 
     { 
      //End of tie 
      break; 
     } 
    } 

    if (endIndex - startIndex > 1) 
    { 
     // Shuffle goals of the same level 
     ShuffleRange(goals, startIndex, endIndex - startIndex, rnd); 
    } 

    startIndex = endIndex; 
} 

static void ShuffleRange<T>(List<T> list, int startIndex, int count, Random rnd) 
{ 
    int n = startIndex + count; 
    while (n > startIndex + 1) 
    { 
     int k = rnd.Next(startIndex, n--); 
     T value = list[k]; 
     list[k] = list[n]; 
     list[n] = value; 
    } 
}   

Working sample

algoritmo Shuffle è preso in prestito da here

Answer 2

Prova questa lambda:

(a, b) => ((b.Active ? 1000 : 0) + b.Level) - ((a.Active ? 1000 : 0) + a.Level) 

Active è 1000 volte più importante di una differenza di livello di 1. Questo funziona fino a 1000 livelli. Quando Active è lo stesso, il livello diventa rilevante. Infine, se è ancora lo stesso, sarà ordinato in modo deterministico, ma non pertinente, che è lo stesso del caso.

Non è necessario utilizzare un numero casuale reale. L'ordine sarà sempre lo stesso durante una corsa, ma potrebbe differire tra una corsa e l'altra. Se si ha realmente bisogno di un ordine casuale è possibile utilizzare questo:

(a, b) => 
    ((b.Active ? 10000 : 0) + b.Level * 10) - 
    ((a.Active ? 10000 : 0) + a.Level * 10) + UnityEngine.Random.Range(-1, 2) 

Answer 3

non riesco a riprodurre il problema di ottenere "uno o più principi attivi gol dopo quelli inattivi". Sembra che le tue istanze Goal siano state mutate dopo l'ordinamento. Suggerirei di provare a creare oggetti di sola lettura laddove possibile.

Il mio altro suggerimento è quello di semplificare il codice di ordinamento per renderlo più chiaro e più facile da ragionare - anche se probabilmente questo non aiuterà direttamente in questo caso.

solo fare questo tipo:

var sorted = 
(
    from g in goals 
    orderby g.Active descending, g.Level, UnityEngine.Random.Range(-1, 2) 
    select g 
.ToList(); 

...o in alternativa e in modo equivalente a questo:

var sorted = 
    goals 
     .OrderByDescending(g => g.Active) 
     .ThenBy(g => g.Level) 
     .ThenBy(g => rnd.Next()) 
     .ToList(); 

Gli ordinamenti LINQ funzionano bene con una fonte casuale. Ho fatto l'analisi della distribuzione su di esso e funziona altrettanto bene come i pescatori.