C# Angesichts einer gewünschten Reihenfolge brauchen eine platzsparende Liste Neuordnung oder Sortierung

Question

Mein Ziel ist: Bei einer Liste von Einträgen und einer gewünschten Reihenfolge, ordnen Sie die Liste der Einträge entsprechend dieser Reihenfolge um. Die Liste wird sehr groß sein, daher ist Platzersparnis wichtig.

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];

Ich mag mich irren, aber es scheint die einfachste und platzsparend Lösung ist die Sortierung nach der Daten durch die Bestellung . oder allgemeiner ausgedrückt:

Gegeben zwei Listen: A,B gibt es eine Möglichkeit, A nach B zu sortieren? Die Funktionalität wäre im Wesentlichen dieselbe wie: Array.Sort<(Of <(TKey, TValue>)>)(array<TKey>[]()[], array<TValue>[]()[])

Eine Methode, die mir in den Sinn kommt, ist die Erstellung eines neuen Datentyps, der sich aus A und B zusammensetzt, z. B. Pair, und dann die Sortierung nach den B-Werten:

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();

Ich möchte jedoch, dass dies so platzsparend wie möglich ist ( beide select's und der tolist()-Aufruf sind vermutlich teuer ), so dass eine weitgehende In-Place-Sortierung erforderlich ist. Gibt es zu diesem Zweck eine Möglichkeit, einen Comparer für A.Sort() zu schreiben, der auf B verweist?

Answer 1

Es gibt zwei Möglichkeiten, das Order-Array zu interpretieren, eine, bei der es den Quellindex für jedes Element aufführt, und eine, bei der es den Zielindex für jedes Element aufführt. Ich bin nicht sicher, welche Sie meinen.

Die Neuordnung einer Liste mit Zielorten ist ziemlich einfach:

// 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
    }
  }
}

Eine Liste mit einer Liste von Quellen neu zu ordnen (ich denke, das ist es, was Sie beabsichtigen), ist etwas schwieriger, Sie müssen nur die Permutation zuerst umkehren.

// 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);
}

Es gibt bekannte In-Place-Permutationsinversionsroutinen, die erste, die ich fand, war perm_inv in SUBSET .

Oftmals ist es nicht nötig, die Permutation zu invertieren, sondern stattdessen die Quellliste so zu ändern, dass stattdessen eine Zielliste erzeugt wird.

Answer 2

Der effizienteste Algorithmus für die Neuordnung wäre wahrscheinlich eine Form von "Lazy Evaluation". Anstatt die Sequenz in der neuen Reihenfolge neu zu berechnen, könnten Sie eine IList-Implementierung erstellen, die die Datenliste und die Bestellliste verwendet, um dynamisch Werte aus einer "virtuell neu geordneten" Sequenz zurückzugeben.

Der Vorteil des Lazy-Modells besteht darin, dass die Durchführung einer doppelten Suche in Bezug auf die Leistung vernachlässigbar ist und es nicht erforderlich ist, dass die gesamte Liste neu geordnet wird, um mit der Rückgabe von Werten zu beginnen. Außerdem kann dieselbe Werteliste in mehreren Reihenfolgen dargestellt werden, ohne dass die zugrunde liegende Liste dupliziert wird. Sie könnten natürlich die Implementierung so ändern, dass die Listen kopiert werden, wenn Sie sicherstellen wollen, dass sich Änderungen an der ursprünglichen Liste (oder der Reihenfolge) nicht auf die dynamisch geordnete Liste auswirken.

Hier ist ein Codebeispiel dafür (nicht getestet).

NOTE : Ich habe die Implementierung leicht von Ihrem Beispiel geändert, um 0-basierte Indizes (anstelle von 1-basierten) der Einfachheit halber zu verwenden. Aber es wäre einfach, den Code zu konvertieren, um 1-basierte Indizes zu verwenden, wenn nötig.

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;
   }

}

Ihr ReorderBy() Funktion wird dann:

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

Wenn Sie dann die dynamisch geordnete Liste in eine reguläre Liste umwandeln wollen, können Sie Folgendes verwenden (das in O(n)-Zeit ausgeführt wird und keine unnötigen Kopien der Daten erstellt):

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