Производительность встроенных функций высшего порядка в сравнении с циклом for-in в Swift

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

Примечание

Если вы найдёте статью интересной, то в этом канале я пишу об iOS-разработке.

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

• Данные размером 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-разработке.