Подтвердить что ты не робот

Как List <T>.IndexOf() реализован в С#?

Я думал о производительности вызова List<T>.Indexof(item). Я не уверен, будет ли это производительность O (n) для последовательного алгоритма или производительности O (log (n)) для двоичного дерева?

4b9b3361

ОТВЕТЫ

Ответ 1

Используя Reflector для .NET, мы можем видеть:

public int IndexOf(T item)
{
    return Array.IndexOf<T>(this._items, item, 0, this._size);
}

public static int IndexOf<T>(T[] array, T value, int startIndex, int count)
{
    return EqualityComparer<T>.Default.IndexOf(array, value, startIndex, count);
}

internal virtual int IndexOf(T[] array, T value, int startIndex, int count)
{
    int num = startIndex + count;
    for (int i = startIndex; i < num; i++)
    {
        if (this.Equals(array[i], value))
            return i;
    }
    return -1;
}

Ответ 2

Это O(n) в соответствии с MSDN.

Этот метод выполняет линейный поиск; поэтому этот метод является операцией O (n), где n является Count.

Ответ 3

List<T> поддерживается плоским массивом, поэтому list.IndexOf(item) - O (n).

Ответ 4

List<T>.IndexOf - O (n), который фактически является оптимальным для неупорядоченного множества из n элементов.

List<T>.BinarySearch - O (log n), но работает только корректно, если список сортируется.

Ответ 5

Если вам нужен более быстрый исполнитель, рассмотрите HashSet<T>. Это компромисс между скоростью и памятью, но это стоит того, если вы цените первое по сравнению с последним.

(Это не совсем то же самое, что и List<T>, он ведет себя как словарь с одним столбцом, но для случаев, когда у вас будет уникальный список, это один из способов сделать это.)

Ответ 6

Мой поздний ответ, но я думаю, стоит упомянуть, что в настоящее время вы можете напрямую обращаться к источникам MS: http://referencesource.microsoft.com/#mscorlib/system/collections/generic/list.cs

Больше не нужно отражать, так как код .NET BCL теперь доступен в Интернете.

Реализует список переменных размера, который использует массив объектов для хранения элементы. Список имеет емкость, которая является выделенной длиной внутренний массив. Поскольку элементы добавляются в список, емкость Список автоматически увеличивается в соответствии с необходимостью перераспределения внутренний массив.

Как реализовано как массив и выполняет линейный поиск, вы легко можете сделать вывод, что алгоритмическая сложность метода IndexOf O (n).. p >

Как уже упоминалось другими, информация доступна в msdn: https://msdn.microsoft.com/en-us/library/e4w08k17(v=vs.110).aspx

Этот метод выполняет линейный поиск; поэтому этот метод является O (n), где n - Count.

Опять же, вы можете проверить источники и в конечном итоге определить, что статический вспомогательный метод IndexOf класса Array фактически вызывается за кулисами:

http://referencesource.microsoft.com/#mscorlib/system/array.cs

Если список/массив уже отсортирован заранее, вы можете скорее использовать двоичный поиск: https://msdn.microsoft.com/en-us/library/w4e7fxsh(v=vs.110).aspx

Этот метод является операцией O (log n), где n - число элементов в диапазоне.

Ответ 7

За кулисами используется обычный array, infact метод IndexOf просто вызывает Array.IndexOf. Поскольку массивы не сортируют элементы, производительность равна O (n).