Этот курс является продолжением курса "Основы разработки на C++: жёлтый пояс". Основная цель курса — научить писать на С++ эффективный код. Кроме того рассмотрены некоторые возможности С++, которые не попали в предыдущие курсы. В курсе рассмотрены: - макросы - шаблоны классов - принципы оптимизации кода - эффективное использование потоков ввода/вывода - оценки сложности алгоритмов - модель памяти в С++ - эффективное использование линейных контейнеров (vector, deque, list, string) - move-семантика - введение в многопоточное программирование Кроме того, в курсе продемонстрировано, как, пользуясь знаниями только "Белого", "Жёлтого" и "Красного" поясов, разработать свой собственный профайлер. Так же, как и в предыдущих курсах, в конце вас ждёт финальный проект. Было бы странно в курсе от Яндекса не попросить вас создать свою поисковую систему! Именно этим вам и предстоит заняться в финальной задаче. Курс разработан ведущими специалистами Яндекса и преподавателями Школы анализа данных. За их плечами – годы разработки сервисов поиска, рекламы и инфраструктуры. Кроме того в подготовке заданий участвовали 1. Сотрудники Яндекса: - Алексей Аверченко - Даниил Петров - Константин Меренков - Алексей Зобнин 2. Выпускники «Жёлтого пояса по С++»: - Борис Егоров - Ольга Марчевская 3. Сотрудник Института проблем информатики РАН Олег Яковлев В создании урока «Шаблоны классов» принимал участие преподаватель Белого и Жёлтого «поясов» Евгений Парамонов.
Амортизированная сложность
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Основы разработки на C++: красный пояс
16 оценки
Moscow Institute of Physics and Technology
16 оценки
Курс 3 из 5 — Specialization Искусство разработки на современном C++
Из урока
Принципы оптимизации кода, сложность алгоритмов и эффективное использование ввода/вывода
Познакомьтесь с преподавателями
Полднев Антон Вячеславович
Яндекс
Шишков Илья Ивановичкандидат технических наук
Яндекс
Последнее, что нам осталось
обсудить, в этой теме — это, что же такое амортизированная константа.
То понятие, которое мы видели,
когда подсмотрели в документации сложность метода push_back у вектора.
Про вектор и то, как у него реализован метод push_back и почему он работает
именно за амортизированную константу, мы поговорим позже в нашем курсе.
Но сейчас мы рассмотрим это понятие амортизированной константы на другом
примере.
Рассмотрим такую задачу.
Пусть к вам приходят события с какими-то временными метками.
Допустим, вы их получаете прямо во возрастанию этих временных меток.
Вам нужно уметь добавлять очередное событие с конкретной временной меткой и
находить в какой-то конкретный момент,
сколько событий случилось за последние пять минут.
Как нам решать такую задачу?
Мы напишем класс EventManager, который будет обрабатывать события.
У него будет метод Add, который будет добавлять событие.
Давайте хранить временные метки в типе unit64_t.
Для этого подключим модуль sctdint.
Итак, будем добавлять
события и узнавать, сколько событий случилось за последние пять минут.
Скажем, в типе int вернём количество событий.
Понимаем тоже временную метку.
И предполагая, что каждая очередная метка больше,
чем предыдущая, мы должны сказать, сколько за последние пять минут случилось событий.
Как такую задачу вообще можно решать?
Её можно решать с помощью очереди.
Давайте я сразу подключу заголовочный файл queue.
И что я буду хранить?
Я буду хранить очередь временных меток событий.
В этой очереди будут все события за последние пять минут.
То есть я буду не только добавлять в эту очередь с одного конца,
но и удалять из неё, когда нужно, старые события, которые старше, чем пять минут.
Соответственно, в методе Add то, что я должен сделать в любом случае,
это добавить в очередь эту самую временную метку.
А в методе Count, если я гарантирую, что у меня в очереди
нет старых событий, я могу просто вернуть размер этой очереди.
Но как же я это гарантирую?
Мне, конечно, понадобится удалять старые события.
Давайте я напишу отдельный приватный метод.
Назову его Adjut, который будет принимать временную метку и удалять события,
которые старше, чем пять минут, относительно этой метки.
Как мне это сделать?
Я должен удалять последнее событие из очереди, пока оно достаточно старое,
если говорить точнее, то пока в очереди вообще что-то есть.
while !events.empty — и пока
у меня самое старое событие в очереди,
которое я получаю с помощью метода front, пока оно слишком старое,
то есть пока это время меньше либо равно, чем time минус 300.
300 секунда — пять минут.
Пока оно достаточно старое, я должен его удалять с помощью метода pop.
И теперь мне нужно поудалять эти старые события, пожалуй,
и перед добавлением в очередь, и перед определением того,
сколько же там событий.
Итак, вот я написал какой-то код.
Давайте я проверю, что он компилируется.
Да, всё в порядке.
И давайте теперь попробуем оценить сложность каждого запроса.
Добавление одного числа в очередь стоит o от единицы,
прямо честное константное время.
Вычисление размера очереди — тоже o от единицы.
Удаление из очереди и обращение к её последнему элементу — тоже o от единицы.
Но есть интересный момент.
В запросе Add, в запросе Count мы вызываем метод Adjust.
Сколько работает этот метод?
А здесь какой-то цикл.
И в худшем случае сколько может работать этот цикл while.
Он в худшем случае будет удалять вам вообще все события из очереди.
В худшем случае все события в очереди,
которые там накопились за долгое-долгое время, они все старше, чем пять минут.
Скажем, вы долго-долго копили-копили события,
они приходили в маленьком-маленьком промежутке.
А потом — бац!
И пришло новое событие спустя час.
Вам нужно очистить всю очередь.
И поэтому количество итераций в этом цикле while в худшем случае
будет пропорционально количеству запросов, то есть o от Q.
И поэтому метод Adjust в худшем случае работает o от Q.
И в частности, как следствие, и метод Add,
и метод Count в худшем случае работают o от Q.
Что же получается?
Неужели суммарно все эти методы будут
обрабатывать запросы за квадратичное время, за Q умножить на Q?
Это же странно.
Я вроде бы делаю такие простые операции: добавил, удалил, проверил.
Почему квадратичное время получается?
Потому что мы слишком увлеклись верхними оценками.
Верхняя оценка в данном случае достигаться не будет.
Почему?
Давайте посмотрим на ту же ситуации с другой точки зрения.
Посмотрим на одно конкретное событие.
Что с ним будет происходить?
Мы его добавим сначала.
Потом оно будет просто лежать в очереди, никак не влияя на сложность.
И потом мы его, возможно, удалим.
То есть всё, что может произойти с одним событием за всё время жизни программы —
это одно добавление, одна проверка на время и одно удаление.
То есть с каждым событием у нас произойдёт константное количество операций,
o от единицы, то есть суммарно мы на обработку всех Q
событий потратим o от Q времени, а не o от Q квадрат,
в то время как верхняя оценка у нас получилась o от Q квадрат.
Где же мы, на самом деле, ошиблись?
Ну не ошиблись, а из-за чему мы получили такую слишком грубую, завышенную оценку?
Дело в том, что вот эти циклы while, конечно,
каждый конкретный вызов Adjust может работать долго за o от Q,
но суммарно все эти циклы while, суммарно все вызовы Adjust по сути нам в худшем
случае очистят всю очередь, все те события, которые мы добавляли.
Их всего Q,
поэтому и суммарное удаление всех этих событий суммарно будет работать за Q.
То есть с каким явлением мы сейчас столкнулись?
Каждый конкретный вызов Adjust может работать долго.
Каждый конкретный вызов Add или Count может работать долго,
если мы скопили много-много событий, а потом новое событие пришло спустя час.
Но суммарно все эти события будут работать за o от Q, а не за o от Q квадрат.
В этом случае говорят, что сложность одного запроса Add,
сложность одного запроса Count и сложность одного вызова метода Adjust не o от Q,
а амортизированное o от Q.
Amortized — то самое, что мы видели в документации — o от Q.
Здесь, здесь, здесь нет, а вот здесь да.
Что означает амортизированная сложность?
Точнее, простите, конечно.
Верхняя оценка была o от Q, но амортизированно получается o от единицы,
и поэтому суммарно мы получаем o от Q.
Чуть более формально.
Да, если мы выполним одну операцию,
один вызов одного из наших методов, у нас будет сложность o от Q.
Но если мы много-много раз на одних и тех же данных будем вызывать этот метод,
тогда суммарно получиться o от Q,
а каждый один вызов будет работать как будто бы за o от единицы.
То есть, грубо говоря, в среднем каждый метод работает за o от единицы,
вот такое понятие амортизированной сложности.
Мы его позже в нашем курсе обсудим на примере push_back у вектора.
Там ровно та же ситуация.
Один push_back может работать долго, но если вы много-много push_back'ов делаете,
тогда каждый из них будет работать быстро в среднем.
А пока просто знайте о таком понятие как амортизированная сложность,
в частности, амортизированная константа, и не увлекайтесь верхними оценками.
Будьте внимательны,
когда вы вычисляете суммарную сложность работы какого-то цикла.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
