[Перевод] Джон Скит. Реализация LINQ to Objects: Часть 7 – Count и LongCount

Это перевод седьмой части серии статей Джона Скита "Реализация LINQ to Objects". С оригинальной версией поста можно ознакомиться здесь.

---

Сегодняшний пост покрывает два оператора за один раз, потому что они невероятно похожи… настолько, что следует лишь скопировать реализацию, изменив только имя, возвращаемое значение и несколько переменных.

Кто они?

Count и LongCount имеют по две перегрузки каждый: одна с предикатом, а другая без. Вот все четыре сигнатуры:

public static int Count<TSource>(
    this IEnumerable<TSource> source)

public static int Count<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)

public static long LongCount<TSource>(
    this IEnumerable<TSource> source)

public static long LongCount<TSource>(
    this IEnumerable<TSource> source,
    Func<TSource, bool> predicate) 

Как вы можете видеть, сигнатура LongCount идентична Count, отличаясь лишь типом возвращаемого значения: long (Int64) вместо int (Int32).

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

Интересные аспекты поведения:

• Все они - методы расширения для IEnumerable<T>. Вы могли бы сказать, что для версий без предиката было бы лучше расширить необобщенный IEnumerable, потому что от типа элемента ничего не зависит.
• Там, где нет предиката, Count оптимизирован под ICollection<T> и (в .NET 4) ICollection – оба которые имеют свойство Count, которое предположительно быстрее, чем обход последовательности. LongCount не оптимизирован подобным образом в .NET – я расскажу об этом в разделе реализации.
• В перегрузках с предикатами не происходит никакой оптимизации, потому что не существует способа определить заранее, сколько элементов «пройдёт» предикат, не проверив их.
• Все методы выполняются немедленно – ничего не отложено. (Если подумать, то тут действительно ничего не может быть отложено, когда мы просто возвращаем int или long.)
• Все аргументы проверяются только на то, что они не null.
• Оба метода должны бросать OverflowException, если в исходной последовательности больше элементов, чем то, количество которых они могут возвратить… тем не менее очевидно, что в случае LongCount это гораздо большее число, чем в случае Count.

Что мы собираемся тестировать?

В некотором смысле, здесь затронуты только два «успешных» теста: с предикатом и без. С ними довольно легко справиться, но мы также хотим использовать оптимизированные случаи. Это несколько хитрее, чем могло бы показаться, поскольку мы можем проверить четыре ситуации:

• Источник, который реализует ICollection<T> и ICollection (просто: используйте List<T>)
• Источник, который реализует ICollection<T>, но не ICollection (довольно просто, после несложного поиска подходящего типа: используйте HashSet<T>)
• Источник, который реализует ICollection, но не ICollection<T>, но до сих пор реализует IEnumerable<T> (так, что мы можем наследовать их) – хитро…
• Источник, которые не реализует ни ICollection ни ICollection<T> (просто: используйте Enumerable.Range, который мы уже имплементировали)

Третий вариант довольно неприятный. Очевидно, существует множество реализаций интерфейса ICollection, но не ICollection<T> (например, ArrayList), но поскольку он не имплементирует IEnumerable<T>, мы не можем вызвать на нём метод расширения Count. В конце концов, я написал собственный класс SemiGenericCollection.

В тот момент, когда у нас будут источники для всех этих тестов, мы должны будем решить, что же конкретно мы собираемся тестировать. Вероятно, мы должны проверить то, что результат оптимизирован, например, проверяя, что никогда в действительности не проходим по последовательности. Это потребует написания собственных коллекций с методами GetEnumerator(), которые бросают исключения, но, тем не менее, возвращают количество в свойстве Count. Так далеко я не заходил, но это другой шаг, который мы могли бы совершить.

Для перегрузок, которые получают делегат, мы не должны беспокоиться о различных интерфейсах коллекций, поскольку мы ничего не оптимизируем.

Сбойные случаи для аргументов null очень просты, но существует другой случай, который следует взять во внимание: переполнение. Для Count я имплементировал прецедент для проверки поведения переполнения. К сожалению, мы пока что не можем запустить этот тест для реализации Edulinq, поскольку он требует Enumerable.Concat, но тут он представлен для справки:

[Test]
[Ignore("Занимает колоссальное количество времени!")]
public void Overflow()
{
    var largeSequence = Enumerable.Range(0, int.MaxValue)
        .Concat(Enumerable.Range(0, 1));
       Assert.Throws<OverflowException>(() => largeSequence.Count());
}

Это предохраняет от плохой имплементации, которая переполняется, просто оборачивая счетчик в Int32.MinValue, вместо вызова исключения.

Как вы видите, этот тест будет отключен даже если он будет раскомментирован после реализации Concat, поскольку он нуждается в счете до двух миллиардов – что нехорошо для быстрой подборки модульных тестов. Хотя это не очень плохо в сравнении с эквивалентом LongCount, который потребует подсчета 2^63 элементов. Генерация такой последовательности не является сложной, но её обход займет очень длительное время. Нам также нужен подобный тест для перегрузки с предикатом - кое-что, чем я пренебрег до написания этого поста, а также нахождение ошибки в реализации, как сделал я :)

Для LongCount, у меня есть только эквивалентный предыдущему тест, который проверяет, что такая-же последовательность может иметь длину, представленную значением long.

Давайте имплементируем их!

Сначала посмотрим на перегрузку, которая принимает предикат – она проще:

public static int Count<TSource>(this IEnumerable<TSource> source,
    Func<TSource, bool> predicate)
{
    if (source == null)
    {
        new ArgumentNullException("source");
    }
    if (predicate == null)
    {
        throw new ArgumentNullException("predicate");
    }

    // Нет способа оптимизировать это
    checked
    {
        int count = 0;
        foreach (TSource item in source)
        {
            if (predicate(item))
            {
                count++;
            }
        }
        return count;
    }
} 

Заметим, что в этот раз мы не используем блок итератора (мы не возвращаем последовательность), поэтому нам не нужно разделять реализацию на две разные части, чтобы выполнить мгновенную валидацию аргументов.

После валидации аргументов, главная часть метода относительно проста, но с одной уловкой: мы производим обход в контексте «checked». Это значит, что если count переполнится, то будет брошен OverflowException вместо переноса к отрицательному числу. Существуют еще несколько альтернатив:

• В checked мы бы могли производить только инкремент count вместо всей второй части метода.
• Мы бы могли явно протестировать count == int.MaxValue перед инкрементом, и бросить исключение.
• Мы могли бы построить всю сборку в контексте checked.

Я считаю, что эта секция должна быть явно checked – это делает очевидным, что это – основное требование к общей корректности. Вы можете предпочесть сделать checked только инкрементирующую часть – я лично считаю, что текущий подход привлекает больше внимания к checked, но это субъективно. Также возможно, что явная проверка может быть быстрее, хотя я сомневаюсь – я не сравнивал эти подходы.

Все, кроме относящихся к предикатам, части вышеизложенного кода также присутствуют в оптимизированной имплементации Count – поэтому я не буду обсуждать их еще раз. Вот полный метод:

public static int Count<TSource>(this IEnumerable<TSource> source)
{
    if (source == null)
    {
        throw new ArgumentNullException("source");
    }

    // Оптимизация для ICollection<T>
    ICollection<TSource> genericCollection = source as ICollection<TSource>;
    if (genericCollection != null)
    {
        return genericCollection.Count;
    }

    // Оптимизация для ICollection
    ICollection nonGenericCollection = source as ICollection;
    if (nonGenericCollection != null)
    {
        return nonGenericCollection.Count;
    }

    // Делаем это медленным способом, и убеждаемся, что переполнение 
    // обрабатывается должным образом
    checked
    {
        int count = 0;
        using (var iterator = source.GetEnumerator())
        {
            while (iterator.MoveNext())
            {
                count++;
            }
         }
         return count;
    }
}

Единственный «новый» код здесь - это оптимизация. Присутствуют два практически эквивалентных блока, которые проверяют только разные типы интерфейсов коллекций, и используется один, который найден первым (если найден). Я не знаю, что .NET проверяет первым: ICollection или ICollection<T> - я мог бы проверить это, имплементируя оба интерфейса, каждый из которых возвращает разные значения count, но это крайность. На самом деле для хорошо себя ведущих коллекций не важно легкое различие в производительности – мы хотим сначала проверить «более возможный» интерфейс, которым, как я считаю, является обобщенный.

Оптимизировать или не оптимизировать?

Реализация LongCount точно такая же, как и реализация Count, за исключением использования long вместо int.

Стоит заметить, что я до сих пор использую оптимизации для ICollection и ICollection<T> , но я не верю, что .NET имплементация так делает. (Это легко проверить, создав огромный список байтов и сравнив время, затраченное Count и LongCount.)

Существует аргумент для использования Array.GetLongLength, когда источник является массивом… но я не считаю, что текущая CLR поддерживает массивы с длиной более Int32.MaxValue, поэтому это скорее вопрос перспективы. Далее, я не уверен, почему .NET имплементация не оптимизирована. Если быть честным, то непонятно, что реализация ICollection/ICollection<T> должна возвращать из её свойства Count, если в ней находится более Int32.MaxValue элементов.

Предложения, что я должен был сделать, приветствуются, но я должен предупредить, что LongCount скорее может быть использован по отношению к Queryable чем к Enumerable – легко представить сервис, представляющий коллекцию (такую, как таблицу базы данных), которая может быстро вернуть вам количество элементов даже если она очень большая. Я предполагаю, что существует относительно мало случаев, когда у вас была бы коллекция, которую вы действительно хотели бы обойти, чтобы только определить количество элементов.

Заключение

Это наши первые операторы LINQ, которые возвращают скалярные значения вместо последовательностей – из чего естественно следует, что их легче понять в смыслах управляющей логики и времени выполнения. Методы просто выполняются – возможно, с оптимизацией – и возвращают свои результаты. Просто и красиво. Тем не менее, мы увидели, что может существовать несколько интересных аспектов для рассмотрения, включая вопросы оптимизации, на которые не всегда существует хороший ответ.

Я думаю, что в следующий раз имплементирую Concat: скорее всего я раскомментирую тесты переполнения для Count. Это вернет нас к операторам, которые возвращают последовательности, но этот - действительно простой.