Этот курс является продолжением курса "Основы разработки на C++: жёлтый пояс". Основная цель курса — научить писать на С++ эффективный код. Кроме того рассмотрены некоторые возможности С++, которые не попали в предыдущие курсы. В курсе рассмотрены: - макросы - шаблоны классов - принципы оптимизации кода - эффективное использование потоков ввода/вывода - оценки сложности алгоритмов - модель памяти в С++ - эффективное использование линейных контейнеров (vector, deque, list, string) - move-семантика - введение в многопоточное программирование Кроме того, в курсе продемонстрировано, как, пользуясь знаниями только "Белого", "Жёлтого" и "Красного" поясов, разработать свой собственный профайлер. Так же, как и в предыдущих курсах, в конце вас ждёт финальный проект. Было бы странно в курсе от Яндекса не попросить вас создать свою поисковую систему! Именно этим вам и предстоит заняться в финальной задаче. Курс разработан ведущими специалистами Яндекса и преподавателями Школы анализа данных. За их плечами – годы разработки сервисов поиска, рекламы и инфраструктуры. Кроме того в подготовке заданий участвовали 1. Сотрудники Яндекса: - Алексей Аверченко - Даниил Петров - Константин Меренков - Алексей Зобнин 2. Выпускники «Жёлтого пояса по С++»: - Борис Егоров - Ольга Марчевская 3. Сотрудник Института проблем информатики РАН Олег Яковлев В создании урока «Шаблоны классов» принимал участие преподаватель Белого и Жёлтого «поясов» Евгений Парамонов.
Амортизированная сложность
Loading...
Из курса от партнера Moscow Institute of Physics and Technology
Основы разработки на C++: красный пояс
66 оценки
Explore Related Videos
At Coursera, you will find the best lectures in the world. Here are some of our personalized recommendations for you
Moscow Institute of Physics and Technology
66 оценки
Курс 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., 2019 Все права защищены.
