Самый быстрый способ вставить значение в int List, а затем отсортировать список

Question

Я работаю с динамическим int универсальным списком.Я пытаюсь добавить, а затем отсортировать список в порядке убывания.Эта операция происходит несколько раз.В настоящее время я использую Linq, чтобы сделать это как.

list.Add(b);
list = list.OrderByDescending(i => i).ToList();

Есть ли способ улучшить производительность этой операции в целом.

Answer 1

Ваш подход действительно имеет много накладных расходов, потому что новый List<T> создается при каждой вставке.

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

static void InsertSorted<T>(IList<T> list, T item) where T : IComparable<T> {
    list.Add(item);
    var i = list.Count-1;
    for ( ; i > 0 && list[i-1].CompareTo(item) < 0 ; i--) {
        list[i] = list[i-1];
    }
    list[i] = item;
}

Демо.

Answer 2

Ваш текущий подход неоптимальный , так как каждый раз, когда вы добавляете элемент, вы снова сортируете весь список, чего можно избежать, и вы создаете новый список каждый раз, когда добавляете целое число к List<int>, чего снова можно избежать.

Поскольку у вас уже есть List<int>, я бы использовал методы, принадлежащие этому классу, в отличие от использования LINQ, чтобы избежать накладных расходов.

ЧтоЯ предлагаю создать метод расширения следующим образом:

public static class Extensions {
        public static void InsertElementDescending(this List<int> source, 
                int element)
        {
            int index = source.FindLastIndex(e => e > element);
            if (index == 0 || index == -1)
            {
                source.Insert(0, element);
                return;
            }
            source.Insert(index + 1, element);
        }
}

Тогда сценарий использования будет:

List<int> list = new List<int>();

list.InsertElementDescending(1);
list.InsertElementDescending(2);
list.InsertElementDescending(233);
list.InsertElementDescending(0);
list.InsertElementDescending(-2);

Теперь список будет содержать элементы в порядке убывания.

В целом это имеет лучшую производительность, чем ваш текущий подход.