Какова производительность Последнего () дополнительный метод для Списка <T>?
Глобальные переменные обычно плохи, особенно если другие люди работают над тем же кодом и не хотят проводить 20 минут, ища все места, на переменную ссылаются. И добавление потоков, которые изменяют переменные, вводит совершенно новый уровень головных болей.
Глобальные константы в анонимном пространстве имен, используемом в единственной единице перевода, прекрасны и повсеместны в профессиональных приложениях и библиотеках. Но если данные изменяемы, и/или они должны быть совместно использованы несколькими TUs, можно хотеть инкапсулировать их - если бы не польза дизайна, затем ради кого-либо отладка или работа с кодом.
5 ответов
Я только что использовал Справочный источник , чтобы изучить код для Last, и он сначала проверяет, является ли он IList первым и выполняет соответствующий вызов O (1):
public static TSource Last < TSource > (this IEnumerable < TSource > source) {
if (source == null) throw Error.ArgumentNull("source");
IList < TSource > list = source as IList < TSource > ;
if (list != null) {
int count = list.Count;
if (count > 0) return list[count - 1];
}
else {
using(IEnumerator < TSource > e = source.GetEnumerator()) {
if (e.MoveNext()) {
TSource result;
do {
result = e.Current;
} while ( e . MoveNext ());
return result;
}
}
}
throw Error.NoElements();
}
Таким образом, у вас есть небольшие накладные расходы на приведение, но не огромные накладные расходы на перечисление.
Для List это O (1), но для других перечислимых оно может быть O (N).
Краткий ответ :
O (1).
Объяснение :
Очевидно, что ] Last () для List использует метод расширения Count () .
Count () проверяет тип коллекции во время выполнения и использует Count , если оно доступно.
Свойство Count для списка имеет сложность O (1), как и метод расширения Last () .
Вы можете просто использовать Last с List , не беспокоясь :)
Enumerable. Последняя попытка понизить значение экземпляра IEnumerable до IList . Если это возможно, он использует индексатор и свойство Count.
Вот часть реализации, которую видит Reflector :
IList<TSource> list = source as IList<TSource>;
if (list != null)
{
int count = list.Count;
if (count > 0)
{
return list[count - 1];
}
}
Он содержит оптимизацию для всего, что реализует IList , и в этом случае он просто ищет элемент длиной -1.
Имейте в виду, что подавляющее большинство материалов, которые вы отправляете, будут реализовывать IList
List<int>
int[]
и так далее ... все реализуют IList
Для тех, кто может не смотрите на код для подтверждения, вы можете подтвердить это, используя наблюдение:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;
namespace ConsoleApplication4 {
class Program {
static void Profile(string description, int iterations, Action func) {
// clean up
GC.Collect();
GC.WaitForPendingFinalizers();
GC.Collect();
// warm up
func();
var watch = Stopwatch.StartNew();
for (int i = 0; i < iterations; i++) {
func();
}
watch.Stop();
Console.Write(description);
Console.WriteLine(" Time Elapsed {0} ms", watch.ElapsedMilliseconds);
}
static void Main(string[] args) {
int[] nums = Enumerable.Range(1, 1000000).ToArray();
int a;
Profile("Raw performance", 100000, () => { a = nums[nums.Length - 1]; });
Profile("With Last", 100000, () => { a = nums.Last(); });
Console.ReadKey();
}
}
}
Вывод:
Raw performance Time Elapsed 1 ms With Last Time Elapsed 31 ms
Таким образом, он всего в 30 раз медленнее и поддерживает этот профиль производительности с любым списком длины, который у вас есть, что ничто в большой схеме вещей .