Самые популярные функции высшего порядка - это map, filter и reduce. Мы все используем их, так как думаем, что синтаксис намного лучше, и писать их даже быстрее, чем старый способ for-in loop. Но так ли это на самом деле? Задумывались ли вы когда-нибудь о производительности этих встроенных функций? Они встроенные, поэтому, естественно, они должны быть лучше, не правда ли? Давайте погрузимся в эти функции вместе, чтобы выяснить, так ли это на самом деле.

Предварительные условия

• Данные размером 10 000 000 элементов.

• Каждый тестовый пример был выполнен 30 раз.

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

Данные

Вот как выглядят данные: есть два массива. Один - массив fahrenheit, который представляет собой 1D массив равномерно распределенных случайных чисел из диапазона <32.0;113.0> и следующий массив, fahrenheits, который представляет собой 2D массив массивов равномерно распределенных случайных чисел из диапазона <32.0;113.0>.

let elementsCount = 10_000_000
let fahrenheit = Array(repeating: 0.0, count: elementsCount).map { _ -> Double in
    return Double.random(in: 32.0 ... 113.0)
}

var fahrenheits = [[Double]]()
for _ in 0 ..< totalElements {
    fahrenheits.append(Array(repeating: 0.0, count: 1).map { _ -> Double in
        return Double.random(in: 32.0 ... 113.0)
    })
}

Функция: Map

Давайте начнем с простого примера. У нас есть массив fahrenheit, и мы хотим преобразовать каждый его элемент в градусы Цельсия. Поэтому мы собираемся сравнить производительность функции map с циклом for-in.

// Swift
let celsius = fahrenheit.map { (degreesFahrenheit) -> Double in
	return (degreesFahrenheit - 32.0) / 1.8
}

// For-in loop
var celsius = [Double]()
for degreesFahrenheit in fahrenheit {
	celsius.append((degreesFahrenheit - 32.0) / 1.8)
}

Производительность

Как видно из рисунка, встроенная функция map намного быстрее чем цикл for-in. Если быть точным, то в 1,63 раза быстрее. Несомненно, нам следует использовать встроенную функцию map.

Статический и динамический массив.

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

Функция: Filter

Следующая функция - это filter. Итак, давайте отфильтруем «холодные градусы» (cold degrees).

Почему я называю их холодными? Я считаю температуру меньше или равную 20 градусам Цельсия (68 градусов по Фаренгейту) холодной, и это причина, по которой я назвал переменную colds.

// Swift
let colds = fahrenheit.filter { (degreesFahrenheit) -> Bool in
    return degreesFahrenheit <= 68.0
}

// For-in loop
var colds = [Double]()     
for degreesFahrenheit in fahrenheit {
    if degreesFahrenheit <= 68.0 {
        colds.append(degreesFahrenheit)
    }
}

Производительность

Разница между встроенной функцией фильтра и циклом for-in в данном случае не так очевидна. Встроенная функция немного быстрее (1.11x), чем цикл for-in. В любом случае, она все равно быстрее, поэтому имеет смысл использовать ее.

Функция: Reduce

Последняя функция - reduce. Для этого сложим все числа вместе. Например, мы можем использовать полученный результат для вычисления средней температуры.

// Swift
let sum = fahrenheit.reduce(0.0) { (result, degreesFahrenheit) -> Double in
    return result + degreesFahrenheit
}

// For-in loop
var sum: Double = 0.0
        
for degreesFahrenheit in fahrenheit {
    sum += degreesFahrenheit
}

Производительность

Результат немного удивляет. Встроенная функция reduce немного медленнее, чем цикл for-in. Встроенная функция reduce в цикле for-in быстрее в 1,05 раза.

Функция: FlatMap

Прежде чем мы рассмотрим цепочку функций, давайте сравним функцию flatMap с циклом for-in. У нас есть массив fahrenheits из массивов double и мы хотим сделать массив double.

// Swift
let fahrenheit = fahrenheits.flatMap({ (fahrenheit) -> [Double] in
    return fahrenheit
})

// For-in loop
var fahrenheit = [Double]()
        
for lFahrenheit in fahrenheits {
    fahrenheit.append(contentsOf: lFahrenheit)
}

Производительность

Результат очень похож на функцию reduce. Встроенная функция flatMap немного медленнее, чем цикл for-in. Встроенная функция flatMap в цикле for-in быстрее в 1,06 раза.

Цепочка (map+filter+reduce)

Пришло время для большего веселья. Как мы видели до сих пор, встроенные функции работают быстрее или чуть медленнее, чем пользовательский цикл for-in. Допустим, мы хотим преобразовать градусы Фаренгейта в градусы Цельсия, затем отфильтровать температуру простуды, затем сложить все отфильтрованные числа.

Это означает, что в начале у нас есть массив чисел fahrenheit, затем вызывается функция map, затем вызывается функция filter, затем вызывается функция reduce.

// Swift
let sum = fahrenheit.map({ (degreesFahrenheit) -> Double in
    return (degreesFahrenheit - 32.0) / 1.8
}).filter({ (degreesCelsius) -> Bool in
    return degreesCelsius <= 20.0
}).reduce(0.0) { (result, degreesCelsius) -> Double in
    return result + degreesCelsius
}

// For-in loop
var sum: Double = 0.0
        
for degreesFahrenheit in fahrenheit {
    let degreesCelsius = (degreesFahrenheit - 32.0) / 1.8
    if degreesCelsius <= 20.0 {
        sum += degreesCelsius
    }
}

Производительность

Упс, как мы видим на фотографии, есть проблема.

Пользовательский цикл for-in в 2,37 раза быстрее. Когда мы используем цепочку, мы должны избегать встроенных функций и писать пользовательское решение с помощью цикла for-in.

Мы можем спросить: «Почему это происходит?», «Что не так с цепочкой функций?».

Я думаю, что очевидно, что происходит. Когда мы используем цепочку функций, нам приходится выполнять итерации над каждым результатом предыдущей функции. В теории информатики существует временная сложность (time complexity), которая описывает количество времени, необходимое для выполнения алгоритма.

В нашем случае, в начале у нас есть массив fahrenheit, и мы вызываем функцию map. В этот момент сложность равна O(n), линейное время, где n - размер массива fahrenheit. Затем мы применяем результат функции map к функции filter. Сложность функции filter также равна O(n). На данный момент общая временная сложность составляет O(2n). Последним шагом является функция reduce. Мы применяем результат функции фильтра к функции reduce. Сложность функции reduce снова равна O(n), потому что обозначение O является верхней границей скорости роста функции. Другими словами, в худшем случае результат функции filter может быть O(n), что означает, что ничего не было отфильтровано, и этот результат используется в качестве входа функции reduce. В итоге, временная сложность составляет O(3n).

Однако если мы используем цикл for-in, то все необходимые действия (map. filter, reduce) мы можем выполнить в одном цикле for-in. Благодаря этому факту, в конечном итоге сложность цикла for-in составляет O(n).

Map, Filter и Reduce в RxSwift

Для сравнения рассмотрим тот же пример в RxSwift. Мы будем использовать функции map, filter и reduce, как и в предыдущем примере.

Observable.from(fahrenheit)
    .map({ (degreesFahrenheit) -> Double in
        return (degreesFahrenheit - 32.0) / 1.8
    })
    .filter({ (degreesCelsius) -> Bool in
        return degreesCelsius <= 20.0
    })
    .reduce(0.0, accumulator: ({ (result, degreesCelsius) -> Double in
        return result + degreesCelsius
    }))
    .subscribe(onNext: { sum in
        print(sum)
    })
    .disposed(by: disposeBag)

Перформанс

О, это совсем не хорошо!

Как видно из рисунка, RxSwift намного медленнее, чем встроенные функции и цикл for-in. Решение встроенных функций в 5,14 раз быстрее, чем RxSwift, а решение цикла for-in - в 12,21 раз быстрее, чем RxSwift.

Пожалуйста, не используйте RxSwift, если вам нужно работать с огромным количеством данных!

Заключение

Согласно тестовым примерам, нет ничего плохого в использовании функций высокого порядка, если нам НЕ нужно выстраивать их в цепочку. Производительность намного выше (1,63x быстрее) при использовании встроенной функции map или немного лучше/хуже при использовании встроенного filter/reduce.

Если нам нужны цепочки функций высокого порядка, мы должны подумать о том, чтобы не использовать их и реализовать их как решение для цикла for-in. Производительность намного выше, в 2,37 раза (в примерах этой статьи), чем у встроенных функций.

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

Больше историй, подходов к реализации и инструментов для iOS-разработчика можно найти в авторском канале об iOS-разработке.