Стоит ли кэшировать результат .Count (или .Count ()), когда операция имеет значение O (1)?

Question

Если .Count или .Count () используются несколько раз на объектах, которые реализуют ICollection (следовательно, с O (1) вычислительной сложностью, если, конечно, она не была переопределена), лучше ли это с точки зрения производительности (не памяти) даже для очень небольшой разницы, чтобы кэшировать значение во временной переменной, а не обращаться к значению свойства каждый раз, когда это необходимо?

Answer 1

Отвечая на вопрос напрямую, даже операция O (1) может занять много времени;просто это всегда занимает одно и то же время, независимо от размера коллекции.Кэширование результата и его чтение будут быстрыми, всегда, но не гарантированно быстрее, чем любая заданная операция O (1).Сначала нужно немного времени;)

Answer 2

Да, это может быть (очень немного) быстрее, поскольку накладные расходы на вызов метода, связанную проверку ошибок и (в случае Count ()) динамическую проверку типа для ICollection имеют некоторую дополнительную нагрузку.

Стоит ли оно того? Это полностью зависит от вас и вашего приложения. Если вы находитесь в очень узком внутреннем цикле, это может стоить того. С другой стороны, в более поздних версиях .NET это тривиальное свойство, вероятно, будет встроено в такие обстоятельства.

Как всегда, пусть ваш профилировщик скажет вам, где находятся горячие точки в вашем приложении.

Answer 3

Извините, ошибочно думать, что ICollection.Count - это O(1). Это должно быть морально, но нет гарантии, что это так:

public EvilCollection<T> : ICollection<T> {
    private readonly ICollection<T> collection;
    private readonly Func<int, int> slowGrowingFunction;
    public EvilCollection(
        ICollection<T> collection,
        Func<int, int> slowGrowingFunction) 
    {
        this.collection = collection;
        this.slowGrowingFunction = slowGrowingFunction;
    }

    public int Count {
        get {
            Thread.Sleep(1000 * this.slowGrowingFunction(this.collection.Count));
            return this.collection.Count;
        }
    }

    // other methods wrap methods on collection for ICollection<T>
}

ICollection<T> evilCollection = 
    new EvilCollection<T>(collection, n => Ackermann(4, n));

О, нет, evilCollection.Count - это O(Ackermann(4, n))!

Тем не менее, Я бы не стал беспокоиться об этом, если бы не знал, что могу попасть в злые коллекции, и обнаружил, что это является существенным узким местом производительности. Имейте в виду, код менее понятен , это может быть менее корректно (каков счетчик обновлений после того, как вы кэшировали результат?) и т. д.

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

Answer 4

Ответ - НЕТ , если вы уверены, что .Count() будет делать сейчас и в функции. Ответ ДА , если .Count() - это какая-то реализация, которая может измениться. Допустим, вы изменили реализацию с помощью некоторого LinkedList, который может не быть O (1).

Answer 5

Нет, в этом нет необходимости; нет никакой пользы от использования временной переменной. Кроме того, если вы кешируете свой счет, вы рискуете оказаться неверным, если набор сбора изменится.