В предыдущих видео мы
подробно познакомились с такими контейнерами как vector, deque и список.
Они выделяли память по-разному, каждый был чем-то по-своему хорош,
но и это еще не все, мы рассмотрели не все возможные стратегии выделения памяти,
и сейчас вы поймете, о чем я говорю.
Давайте, опять же, пойдем от примера.
Пример на самом деле основан на реальных событиях, но, конечно, сильно упрощен.
Представьте, что вам нужно довольно много раз вызывать функцию…
Давайте я сразу скажу, сколько раз я буду ее вызывать,
буду вызывать ее count раз, давайте миллион.
Мне нужно миллион раз повызывать функцию, которая возвращает всегда пять чисел.
Конечно, это не всегда одинаковые пять чисел, потому что иначе бессмысленно было
бы вызывать ее много раз, но чисел всегда пять.
Давайте считать, что это известно.
Давайте напишем какую-нибудь функцию, наверное,
логичнее всего попробовать использовать vector,
там и память аллоцироваться не будет, ничего такого.
Будем принимать, допустим, номер итерации и возвращать
вектор из чисел i, i + 1, i + 2, i + 3,
i + 4, всегда пять чисел.
Вот это можно сделать с помощью vector.
Давайте я повызываю эту функцию, как я и обещал,
ровно count раз, вызываю BuildVector (i),
давайте сохраню результат
в переменную numbers
и оберну это в макрос LOG_DURATION.
Сколько же будет работать этот код, мы сейчас узнаем.
Компилируем код,
код не компилируется, потому что я vector не подключил, давайте я исправлюсь.
Компилятор еще огорчает неиспользованная переменная numbers,
но все-таки мы хотим просто померить, поэтому давайте этому не огорчаться.
260 миллисекунд мы потратили на то,
чтобы миллион раз вызвать функцию, которая возвращает пять элементов.
То есть, грубо говоря, мы делаем пять миллионов операций и тратим на это 260
миллисекунд, то есть за секунду мы успели бы 20 миллионов операций.
Это кажется мало, на что же мы тратим наши ресурсы драгоценные?
Казалось бы, всего пять чисел.
Ну, конечно, мы миллион раз создаем вектор,
мы миллион раз просим в куче выделить память под пять интов.
Просить память в куче — не самое эффективное занятие.
Как же эту проблему решить?
Можно попробовать эти пять элементов возвращать через стек.
И как нам этого добиться?
Теперь нам vector не подходит, нам нужен какой-то тип данных,
который хранит данные на стеке.
Мы могли бы завести структуру с пятью полями, но не понятно, как их называть,
и вообще это что-то странное.
Давайте попробуем кортеж использовать.
Казалось бы, кортеж — это аналог структуры и хранит свои данные на стеке,
поэтому давайте я сразу подключу tuple и напишу
ту же самую функцию, но с помощью кортежа.
Она будет называться BuildTuple,
работать будет с помощью функции make_tuple и
возвращать будет кортеж из пяти интов.
То есть мне сейчас придется написать int, int, ну давайте
применим магию вима и вот так вот получим кортеж из пяти интов – отлично.
Вот мы вернули кортеж из пяти интов и давайте померим,
что же быстрее, не стало ли у нас работать быстрее от того,
что мы использовали кортеж, передавая данные через стек.
Запускаем, в
принципе должно стать быстрее.
Да, у нас стало быстрее практически в три раза.
Если с вектором работает порядка 300 миллисекунд,
то с кортежем работает 110 миллисекунд.
Ну хорошо, 110 миллисекунд на пять миллионов операций,
то есть за секунду мы успеем 50 миллионов.
Кажется, тоже не очень быстро, все-таки у нас простые операции,
мы просто числа складываем на стеках и со стека возвращаем функцию main.
Что может быть проще?
Почему работает так долго?
И это не единственная проблема с кортежем, потому что кортеж — это
очень универсальная штука, она позволяет сохранить элементы различных типов,
и в частности поэтому по нему нельзя нормально проитерироваться, например,
нельзя по-человечески с помощью квадратных скобок обратиться к конкретному элементу с
конкретным номером.
Поэтому кортеж и менее эффективен, и менее удобен.
Нам нужен какой-то аналог вектора, но на стеке.
Конечно, у нас не получиться сделать полный аналог вектора на стеке,
потому что на стеке каждой функции важно знать,
сколько будет занимать ее фрейм, важно понимать, сколько там будет байт.
Но вспомните, у нас было условие про то, что элементов всегда пять,
поэтому можем попросить выделить на стеке пять интов,
использовав тип array.
Мы можем подключить модуль
array и возвращать из функции массив.
Я сразу назову ее BuildArray, тело функции оставляю таким же,
а тип будет таким: array <int, 5>.
Еще раз, фрейм функции должен занимать
определенное количество байт, фиксированное.
Я не могу сказать: «Я захочу сколько-то интов на стеке, но не знаю сколько».
Поэтому я должен прямо в типе массива сказать, что у меня будет 5 интов.
Заметьте, вот эти 5 — это шаблонный параметр класса мы до этого сталкивались
только с классами, у которых шаблонный параметр это тип,
например тип объекта в контейнере.
Оказывается, если компилятору важно знать заранее какую-то числовую характеристику,
например, контейнера, ее тоже можно положить в шаблонные параметры.
Вот в данном случае у типа array два шаблонных параметра — это тип элементов,
которые там лежат, и количество этих элементов.
Хорошо, давайте проверим, не стало ли у нас быстрее.
[БЕЗ_ЗВУКА] Копируем наш бенчмарк,
называем его array и здесь вместо BuildTuple будем вызывать BuildArray.
Запускаем код.
И девять миллисекунд,
наконец-то наш код стал работать быстро,
по сути, он работает в 30 раз быстрее,
чем аналогичный код с вектором благодаря тому, что данные передаются через стек.
Однако может возникнуть вопрос у вас: почему массив
настолько эффективнее, чем кортеж?
Все-таки и там, и там данные передаются через стек, ну и что, что кортеж
очень универсальная штука, почему от этого должна страдать его эффективность?
На самом деле я сказал вам не всю правду, а дело все в том,
что я компилирую без оптимизации.
Давайте я это исправлю, зайду в настройки проекта Project Properties,
здесь перейду во вкладку
CC++ Build Settings,
перешел в настройки проекта CC++ Build Settings.
И здесь я перехожу во вкладку Optimization и вижу,
что у меня стоит Optimization Level (−O0), то есть оптимизация отключена.
И, в частности, поэтому кортеж был менее эффективен.
Давайте я исправлюсь и переключусь на −O2,
Optimaze more.
оптимизируй, пожалуйста, сохраняем настройки,
настройки сохраняются, и я заново компилирую код.
Все дело в том, что, когда компилятор
компилирует без оптимизации, код может быть очень неэффективен.
Если кортеж — это очень универсальная штука и позволяет хранить различные типы,
то и код у него будет под это приспособлен, то есть,
когда нет оптимизации, генерируемый компилятором код менее
эффективен и более универсальные типы могут работать менее эффективно.
А вот когда мы включили оптимизации, vector все еще работает долго,
чуть быстрее, но все еще долго, а кортеж и массив работают просто мгновенно,
и разница между ними незаметна.
И снова давайте вернемся к вопросу о сложности алгоритма.
Какую сложность имеет вот этот алгоритм во всех трех ипостасях?
Вот, например, вот здесь у нас у цикла count итераций, давайте, скажем,
C, и на каждые итерации мы создаем пять чисел, возвращаем их из функции.
Давайте, скажем, что это 5 = N, и тогда у нас сложиться
алгоритм просто C * N, где C — в данном случае миллион, а N = 5.
И такая же сложность у нас и у вектора, и у кортежа, и у массива,
но при этом разница, например, между вектором и массивом в разы, на порядки.
Что здесь можно заметить?
Опять же, константа при сложности важна,
и если вы не умеете выбирать конкретный контейнер,
то оценка сложности вам поможет не всегда, константа тоже важна.
Более того, давайте я сделаю странное и в варианте с массивом,
я отсортирую полученный массив.
Я подключаю модуль алгоритм
[БЕЗ_ЗВУКА] и вот здесь, получив
массив из функции BuildArray, давайте я его отсортирую, сейчас вы поймете зачем.
Во-первых, я показываю, что можно сортировать массив,
что у него есть итераторы, это довольно приятно, даже несмотря на то,
что данные на стеке, все равно есть итераторы.
Итак, я сортирую, проверяю,
сколько по времени это будет работать, 21 миллисекунда.
Стало, конечно, дольше чем с кортежем,
но по сравнению с вектором все равно быстрее в пять раз, почти в шесть.
И при этом сложность алгоритма теперь не C * N, а C * N * logN.
Данный пример демонстрирует, что даже имея два алгоритма,
у одного из которых сложность вроде больше, чем у другого,
а в данном случае у вот этого алгоритма с массивом сложность явно больше, чем
у алгоритма с вектором, даже в этом случае из-за того, что у вас большая константа,
большие накладные расходы на выделение памяти под вектор, вы все равно получаете,
что алгоритм, который вроде бы должен работать больше, работает быстрее.
