Как <T>.IndexOf Списка () реализован в C#?
Я думал о выполнении вызова List<T>.Indexof(item). Я не уверен, будет ли это O (n) производительность для алгоритма последовательности или O (журнал (n)) производительность для двоичного дерева??
6 ответов
Используя 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;
}
Согласно MSDN , это O (n) .
Этот метод выполняет линейный поиск; следовательно, этот метод является операцией O (n), где n - Count.
List поддерживается плоским массивом, поэтому list.IndexOf (item) равно O (n).
Если вам нужен более быстрый исполнитель, рассмотрите вариант HashSet . Это компромисс между скоростью и памятью, но он того стоит, если вы цените первое выше второго.
(Это не совсем то же самое, что List , он ведет себя как словарь с одним столбцом, но для случаев, когда у вас будет уникальный список, это один из способов сделать это. )
List равен O (n), что фактически является оптимальным для неупорядоченного набора из n элементов.
List имеет значение O (log n), но работает правильно только в том случае, если список отсортирован.
За кулисами используется обычный массив , фактически метод IndexOf просто вызывает Array. IndexOf . Поскольку массивы не сортируют элементы, производительность равна O (n).