C# Étant donné un ordre souhaité besoin d'un réordonnancement de la liste efficace de l'espace ou de tri

Question

Mon objectif est: Compte tenu d'une liste d'entrées, et un ordre souhaité, réorganiser la liste des entrées en fonction de cette commande. La liste sera très grande, donc l'efficacité de l'espace est importante.

Ex:

List<Entry> data = ReadDataFromSomeWhere(); // data => [a, b, c]; 
List<int> ordering = RandomPermutation(data.Count); // ordering => [2, 1, 3]; 
data.ReOrderBy(ordering); // data => [b, a, c]; 

Je peux me tromper, mais il semble que la solution la plus simple et efficace de l'espace est de trier/orderby les données par la commande . ou plus généralement:

Étant donné deux listes: A, B existe-t-il un moyen de trier A par B? La fonctionnalité serait essentiellement la même que: Array.Sort<(Of <(TKey, TValue>)>)(array<TKey>[]()[], array<TValue>[]()[])

Une méthodologie qui vient à l'esprit est de créer un nouveau type de données qui est composé de A et B, ie. Paire, puis trier par les valeurs B:

List<T> A; 
List<T> B; 
Assert(A.Count == B.Count); 
var C = A.Select((a,idx) => new Pair<T,T>(B[idx],a)).OrderBy(c => c.First); 
A = C.Select(x => x.Second).ToList(); 

Cependant, je voudrais que ce soit aussi efficace de l'espace que possible (à la fois sélectionner son et la tolist() appelle Je devine que coûtent cher), donc un un tri largement en place est nécessaire. A cette fin, existe-t-il un moyen d'écrire un comparateur pour A.Sort(), qui fait référence à B?

Answer 1

Il existe deux manières d'interpréter le tableau d'ordre, l'une dans laquelle il répertorie l'index source de chaque élément et l'autre dans laquelle il répertorie l'index de destination pour chaque élément. Je ne suis pas sûr de savoir lequel tu veux dire.

Réorganiser une liste donnée une liste de destinations est assez facile:

// Sets list[destination[i]] = list[i] for all i. Clobbers destination list. 
void ReorderByDestination(List<T> list, List<int> destination) { 
    for (int i = 0; i < list.Count; i++) { 
    while (destination[i] != i) { 
     int d = destination[i]; 
     T t = list[d];   // save element in destination slot 
     int t_d = destination[d]; // and its own destination 
     list[d] = list[i];  // move element to destination 
     destination[d] = d;  // and mark it as moved 
     list[i] = t;    // store saved element in slot i 
     destination[i] = t_d;  // ... and its destination 
    } 
    } 
} 

ReOrdering une liste donné une liste des sources (ce qui est ce que je pense que vous avez l'intention) est un peu plus difficile, il vous suffit inverser la permutation en premier.

// Sets list[i] = list[source[i]] for all i. Clobbers source list. 
void ReorderBySource(List<T> list, List<int> source) { 
    InvertPermutation(source); 
    ReorderByDestination(list, source); 
} 

On connaît en place des routines d'inversion de permutation, le premier que j'ai trouvé dans perm_inv SUBSET.

Souvent, vous n'avez pas besoin d'inverser la permutation, mais plutôt de modifier tout ce qui a généré la liste source pour générer une liste de destinations à la place.

Answer 2

L'algorithme de réorganisation le plus efficace serait probablement une forme d'évaluation paresseuse. Plutôt que de recalculer réellement la séquence dans le nouvel ordre, vous pouvez créer une implémentation IList qui utilise la liste de données et la liste de commandes pour renvoyer dynamiquement des valeurs à partir d'une séquence "réorganisée". L'avantage du modèle paresseux est que l'exécution d'une double recherche est négligeable en termes de performance, et ne nécessite pas que la liste entière soit réorganisée afin de commencer à renvoyer des valeurs. Il peut également permettre que la même liste de valeurs soit présentée dans plusieurs ordres sans dupliquer la liste sous-jacente. Vous pouvez, bien sûr, modifier l'implémentation pour copier les listes si vous voulez vous assurer que les modifications apportées à la liste (ou aux commandes) d'origine n'affectent pas la liste ordonnée de manière dynamique.

Voici un exemple de code (non testé).

REMARQUE: J'ai légèrement modifié l'implémentation de votre exemple pour utiliser des index 0 (au lieu de 1) pour plus de simplicité. Mais il serait facile de convertir le code pour utiliser des index basés sur 1 si nécessaire.

public DynamicallyOrderedList<T> : IList<T> 
{ 
    private readonly IList<T> m_Values; 
    private readonly IList<int> m_Order; 

    public DynamicallyOrderedList(IList<T> valueList, IList<int> ordering) 
    { 
     if(valueList == null || ordering == null) 
      throw new ArgumentNullException(); 
     if(valueList.Count != ordering.Count) 
      throw new InvalidArgumentException("Lists are not of same size."); 
     // assumes ordering list has distinct values ranging from 0 to Count-1 

     m_Values = valueList; 
     m_Order = ordering;   
    } 

    // IList<T> Implementation 

    // for simplicity, don't allow addition, removal or clearing of items 
    // these could, however be implemented to add items to the end of the list 
    // and remove them by collapsing the ordering list. 
    // Left as an exercise for the reader :-) 
    public void Add(T item) { throw new NotSupportedException(); } 

    public void Insert(int index, T item) { throw new NotSupportedException(); } 

    public void Clear() { throw new NotSupportedException(); } 

    public void Remove(T item) { throw new NotSupportedException(); } 

    public void RemoveAt(int index) { throw new NotSupportedException(); } 

    public T this[int index] 
    { 
     get 
     { 
      if(index > m_Values.Count) 
       throw new ArgumentOutOfRangeException("index"); 
      return m_Values[m_Order[index]]; 
     } 
     set 
     { 
      if(index > m_Values.Count) 
       throw new ArgumentOutOfRangeException("index"); 
      m_Values[m_Order[index]] = value; 
     } 
    } 

    public int Count { get { return m_Values.Count; } } 

    public bool Contains(T item) { return m_Values.Contains(item); } 

    public bool IndexOf(T item) { return m_Order[m_Values.IndexOf(item)]; } 

    // Enumerator that returns items in the order defined by m_Order 
    public IEnumerator<T> GetEnumerator() 
    { 
     // use generator syntax to simplify enumerator implementation 
     foreach(var index in m_Order) 
      yield return m_Values[index]; 
    } 

    public void CopyTo(T[] array, int arrayIndex) 
    { 
     foreach(var item in this) 
      array[arrayIndex++] = item; 
    } 

}

Votre fonction ReorderBy() devient alors:

public static class ReorderByExt 
{ 
    public static IList<T> ReorderBy<T>(this IList<T> list, IList<int> order) 
    { 
     return new DynamicallyOrderedList(list, order); 
    } 
} 

Si vous alors besoin de matérialiser la liste ordonnée de façon dynamique dans une liste régulière, vous pouvez utiliser les éléments suivants (qui se déroulera en O (n) temps et ne produira pas de copies inutiles des données):

var staticallyOrderedList = originalList.ReorderBy(ordering).ToList();