C # При желаемом порядке требуется переупорядочение или сортировка списка с эффективным использованием пространства. - PullRequest
2 голосов
/ 23 декабря 2009

Моя цель: учитывая список записей и желаемый порядок, переставить список записей в соответствии с этим порядком. Список будет очень большим, поэтому эффективность использования пространства важна.

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

Возможно, я ошибаюсь, но, похоже, самое простое и экономичное решение - это отсортировать / упорядочить данные по порядку . или, в более общем случае:

Учитывая два списка: A, B, есть ли способ отсортировать A по B? Функциональность будет по существу такой же, как: Array.Sort<(Of <(TKey, TValue>)>)(array<TKey>[]()[], array<TValue>[]()[])

Одна методология, которая приходит на ум, - это создание нового типа данных, который состоит из A и B, т.е. Сопряжение, затем сортировка по значениям 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();

Однако я хотел бы, чтобы это было как можно более эффективным с точки зрения пространства ( оба вызова select и tolist (), я полагаю, стоят дорого ), поэтому необходима в значительной степени сортировка на месте. Для этого есть ли способ написать компаратор для A.Sort (), который ссылается на B?

Ответы [ 2 ]

2 голосов
/ 23 декабря 2009

Существует два способа интерпретации массива порядка: один, в котором он перечисляет исходный индекс для каждого элемента, и один, в котором он перечисляет целевой индекс для каждого элемента. Я не уверен, какой ты имеешь в виду.

Упорядочить список по списку направлений довольно просто:

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

Переупорядочить список с учетом списка источников (что, я думаю, вы собираетесь) немного сложнее, вам просто нужно сначала инвертировать перестановку.

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

Существуют известные процедуры инверсии перестановки на месте, первой я обнаружил perm_inv в SUBSET .

Зачастую вам не нужно инвертировать перестановку, вместо этого измените любой сгенерированный исходный список, чтобы сгенерировать список адресатов.

1 голос
/ 23 декабря 2009

Наиболее эффективным алгоритмом переупорядочения, вероятно, будет некоторая форма отложенной оценки. Вместо того, чтобы фактически пересчитывать последовательность в новом порядке, вы могли бы создать реализацию IList, которая использует список данных и список упорядочивания для динамического возврата значений из «виртуально переупорядоченной» последовательности.

Преимущество ленивой модели заключается в том, что выполнение двойного поиска незначительно с точки зрения производительности и не требует переупорядочения всего списка, чтобы начать возвращать значения. Это также может потенциально позволить одному и тому же списку значений быть представленным в нескольких порядке, не дублируя базовый список. Конечно, вы можете изменить реализацию, чтобы копировать списки, если вы хотите, чтобы изменения в исходном списке (или упорядочении) не влияли на динамически упорядоченный список.

Вот пример кода (не проверено).

ПРИМЕЧАНИЕ: Я немного изменил реализацию из вашего примера, чтобы для простоты использовать индексы, основанные на 0 (вместо 1). Но при необходимости было бы легко преобразовать код в индексы, основанные на 1.

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

}

Ваша ReorderBy() функция становится:

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

Если вам затем нужно материализовать динамически упорядоченный список в обычный список, вы можете использовать следующее (которое будет выполняться за O (n) раз и не будет создавать ненужные копии данных):

var staticallyOrderedList = originalList.ReorderBy( ordering ).ToList();
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...