Могу ли я искать отсортированный список <T>быстрее, когда он сортируется по полям, по которым я ищу? - PullRequest
3 голосов
/ 07 февраля 2011

Думаю, что сортировка List<T> по полям, по которым я ищу, ускорит поиск.Предположим, у меня есть List<Person> 10.000 и List<Car> 10.000 в объектной модели.Я зацикливаю список «Персоны» в модели и хочу найти автомобиль со свойством c.Owner == person.Name.

public static Car Car(Model model, Person person)
        {
            return model.Cars.Find(
                 delegate(Car c)
                 {
                     return c.Owner.Equals(person.Name);
                 });
        }

Сортировка списка автомобилей по владельцу не делает цикл быстрее?

Я подумал, что, возможно, мне следует использовать BinarySearch, но перегрузки BinarySearch не позволяют делегатам.Что такое überhaupt для использования BinarySearch, когда вам нужно указать автомобиль, который вы хотите найти в качестве параметра?

1 Ответ

5 голосов
/ 07 февраля 2011

List<T>.BinarySearch не принимает делегата, но имеет перегрузку , которая принимает IComparer<T>.Используйте эту перегрузку с соответствующим пользовательским компаратором (CarByOwnerComparer : IComparer<Car>), чтобы заставить его искать, как вы хотите.Конечно, имейте в виду, что список должен быть уже отсортирован с помощью этого компаратора, чтобы позволить двоичному поиску работать.Если вы предпочитаете написание делегата (например, через лямбду) реализации интерфейса, рассмотрите возможность использования преобразователя, который может переводить между ними, например, ProjectionComparer, предоставленного здесь.

ОднакоЯ бы посоветовал вам использовать более подходящий класс коллекции, который обеспечивает быстрый поиск по ключу.Например, SortedList<,> и SortedDictionary<,> будут выполнять работу в O(logn).Если заказ не является истинным требованием, возможно, будет гораздо проще просто набрать Dictionary<,>.

...