Почему нет сортировки по IList <T>?!?! (Изм) - PullRequest
Новая
       20

Почему нет сортировки по IList <T>?!?! (Изм)

10 голосов
/ 20 июля 2009

Я был очень удивлен, когда обнаружил, что нет прямого способа сортировки или выполнения бинарного поиска по IList . Так же, как есть статические методы для сортировки и выполнения бинарного поиска в массиве, я думаю, что было бы очень полезно иметь аналогичные статические методы, которые принимают IList .

В настоящее время: 

class Array
{
    static Sort<T>(T[] array);
    static int BinarySearch<T>(T[] array, T item);
}

Хотелось бы, чтобы они добавили: 

class List
{
    static Sort<T>(IList<T> list);
    static int BinarySearch<T>(IList<T> list, T item);
}

Я посмотрел на .NET Framework 4.0 Beta SDK, и там все еще , похоже, не является решением этой проблемы.

Я знаю, что мог бы обойти эту проблему, создав метод расширения, который проверяет, является ли он списком , а затем сортирует / ищет, используя экземпляр List ; однако, если это не экземпляр List , тогда я должен выполнить копию (которая воняет для очень больших списков). Я знаю, что могу сделать все это, но почему? Есть ли какая-то причина, по которой они намеренно пропустили эту функцию?

Чтобы попытаться получить это в .NET 4.0 Framework, я создал предложение через программу Microsoft Connect. Если вы, как и я, разочарованы этой проблемой, проголосуйте за нее, и, возможно, она будет добавлена.

https://connect.microsoft.com/VisualStudio/feedback/ViewFeedback.aspx?FeedbackID=474201

Ответы [ 5 ]

17 голосов
/ 20 июля 2009

LINQ имеет метод OrderBy, который работает на всех IEnumerable , включая IList . Вы можете сделать то же самое, используя OrderBy. 

// Order a list of addresses:
IList<string> list = ...
var orderedList = list.OrderBy(input => input);
10 голосов
/ 20 июля 2009

Я думаю, что есть хороший пример, чтобы не включать метод сортировки для IList<T>. Во-первых, это создаст дополнительную сложность для тех, кто хочет внедрить IList, а во-вторых, будет затруднительно для интерфейса IList соответствовать Принципу разделения интерфейса .

Обычно, если мне нужно выполнить сортировку IList<T>, я создаю новый List<T> и передаю IList<T> в качестве параметра

так например: 

        public IList<Address> SortAddresses(IList<Address> addresses)
        {
            var sortedAddresses = new List<Address>(addresses);
            sortedAddresses.Sort();
            return sortedAddresses;
        }
4 голосов
/ 20 июля 2009

Хорошая новость заключается в том, что вы можете написать таких методов довольно легко; и благодаря методам расширения C # 3.0, вы можете сделать это на интерфейсе: 

public static class ListExt
{
    public static void AddRange<T>(this IList<T> list, IEnumerable<T> items) {
        foreach(T item in items) list.Add(item);
    }
    public static void Sort<T>(this IList<T> list) {
        Sort<T>(list,Comparer<T>.Default); // ordinal sort by default
    }
    public static void Sort<T>(this IList<T> list, IComparer<T> comparer)
    { // very poor implementation!
        List<T> concreteList = new List<T>(list);
        concreteList.Sort(comparer); // cheat!
        list.Clear();
        list.AddRange(concreteList);
    }
    public static int BinarySearch<T>(this IList<T> list, T item) {
        return BinarySearch<T>(list, item, Comparer<T>.Default);
    }
    public static int BinarySearch<T>(this IList<T> list, T item,
        IComparer<T> comparer)
    {...} // TODO
}

Теперь остается только сам код TODO (и, вероятно, переписать Sort ;-p); но после этого: 

IList<T> list = ...
list.Sort();
T huntFor = ...
int i = list.BinarySearch(huntFor);

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

2 голосов
/ 20 июля 2009

У вас есть ArrayList.Adapter, который позволяет использовать подпрограммы сортировки ArrayList, но это может оказать огромное влияние на производительность для общих списков типов распакованных значений, а также накладных расходов на виртуальный вызов и на передачу интерфейса.

Как для ссылочных, так и для значений типов отправка интерфейса может быть дорогой, что означает, что вызов ICollection<T>.CopyTo массива T[] с последующей отдельной сортировкой может быть самым быстрым вариантом общего назначения, включая настраиваемое расширение для прямой сортировки на IList<T> объект.

List<T> имеет метод Sort, поскольку он может очень эффективно работать с базовым массивом типа T[]. Просто нет способа сделать это для произвольного IList<T>.

0 голосов
/ 20 июля 2009

Я не эксперт по C #, но очень немногие реализации List поддерживают сортировку, бинарный поиск или даже индексированный поиск. Списки обычно основаны на связанных списках , которые обычно не предлагают O(1) способ получения элемента по его индексу. Если вы хотите быстро найти элемент, то используйте что-то, что поддерживает элементы в отсортированном порядке, например дерево или массив, как предложено другими.

Я нахожу интересным тот факт, что IList включает индексированный метод поиска . Возможно, вы захотите использовать SortedList вместо List, поскольку похоже, что он должен поддерживать поиск по индексу или ключу во O(1) времени. В общем, если вам нужно что-то, что поддерживает быстрый поиск, тогда ищите структуру данных, которая хранит свои элементы в порядке, а не сортирует их явно. Если уж на то пошло, в C # уже есть множество структур данных.

...