Реализован ли в .NET поиск по отсортированным массивам?

#c_sharp #net

Есть ли информация о работе C# с коллекциями массивами и тд в плане реализации? Ну,
то есть поиск по сортированному массиву примерно в 2 раза быстрее, чем по несортированному.
А как происходит поиск в Array, List, Dictionary и тд?

Для примера вот задачка. Есть класс аэропорт(название, координаты). Есть класс коллекция
аэропортов. В коллекции есть List<аэропорт>, как хранилище объектов аэропорт. В коллекции
не может быть 2 аэропорта с одинаковым названием или с одинаковыми координатами. Что
быстрее, использовать list.Find(predicate) или добавить к классу коллекции два словаря:

Dictionary<строка, аэропорт>

Dictionary<координаты, аэропорт> 

и искать совпадения по этим коллекциям? Если со словарями поиск будет быстрее, то
на сколько?
    

Ответы

Ответ 1

В .NET 4.5 и выше есть метод List(T).BinarySearch, который использует алгоритм двоичного
поиска. Двоичный поиск намного быстрее, чем простой итеративный поиск.

Вот пример:

var ints = new List { 1, 56, 112 };
ints.BinarySearch(1);   // 0
ints.BinarySearch(56);  // 1
ints.BinarySearch(112); // 2
ints.BinarySearch(0);   // -1
ints.BinarySearch(10);  // -2
ints.BinarySearch(100); // -3
ints.BinarySearch(200); // -4


Для List<аэропорт>, в принципе это тоже возможно, но надо создать IComparer для аэропортов.


  Что быстрее, использовать list.Find(predicate) или добавить к классу коллекции
два словаря?


Для больших коллекцией быстрее использовать словари. 

Согласно документации, временная сложность метода Dictionary.ContainsKey
приближается O(1). Временная сложность метода List.BinarySearch - O(log(n)), и временная
сложность метода List.Find - O(n).


Ответ 2

Описание поиска в отсортированном быстрее чем в неотсортированно обсуждается тут:
https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-an-unsorted-array
Поиск в Array и List происходит простым циклом и сравниванием членов массива\списка.
Поиск в Dictionary происходит через хэш таблицу.


У List есть метод BinarySearch, он ищет бинарным поиском но только в отсортированном
массиве, то что массив отсортирован вы должны гарантировать самостоятельно.

Для примера с аэропортами лучше использовать Dictionary. Но в данном случае не совсем
понятно какого вида координаты если это числа с плавающей точной то там есть округление,
например (1.0 / 3.0) не равно (1.1 / 3.3)

Поиск в Listе требует итерирования всего списка.
Поиск в Dictionary не требует итерирования коллекции и работает в среднем за 1 операцию.


Ответ 3

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

Существует особый класс алгоритмов и структур данных, осведомлённых о кэше. Смотрите
разделы Cache-Conscious Binary Search и Hot/Cold Data Splitting. Их применение на действительно
больших объёмах данных может быть существенно выгодней.


Ответ 4

В .NET поиск по неотсортированным структурам (те же List, Dictionary, T[]) происходит
простым перебором элементов в цикле (да, в Dictionary тоже происходит перебор ключей). 

Для списка это выглядит примерно так: 

// разумеется, реальный метод должен 
// быть несколько сложнее за счет проверок
// аргументов и прочей логики
public T Find(Predicate pred) 
{

    for(int i = 0 ; i < data.Length; i++) 
    {
        if(pred(data[i])) 
        {
            return data[i];
        }
    }
    return default(T);
}


для словарей это будет выглядеть похожим образом с тем отличием, что вместо метода
Find и предиката там используется индексатор с обращением по ключу, соответственно,
при поиске будет использоваться не вызов предиката, а сравнение хэш-кодов ключа и перебираемых
ключей. Скорее всего сравнение хэшкодов будет происходить быстрее, особенно если предикат
имеет какую-то сложную логику (не стоит также забывать, что лямбда-выражение предиката
разворачивается в анонимный класс, который также требует создание экземпляра и выделение
под него памяти). Но утверждать это на 146% я бы не стал. Если вам действительно важна
скорость поиска, то я бы на вашем месте вначале провел тесты для сравнения того и другого
вариантов. но, думаю, поиск по словарю будет все же побыстрее