Этот курс является продолжением курса "Основы разработки на 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++
Из урока
Принципы оптимизации кода, сложность алгоритмов и эффективное использование ввода/вывода
Познакомьтесь с преподавателями
Полднев Антон Вячеславович
Яндекс
Шишков Илья Ивановичкандидат технических наук
Яндекс
Здравствуйте.
Меня зовут Антон Полднев, и мы продолжаем разговор о написании эффективного кода.
Вы только что научились измерять, сколько работает ваш код,
в частности, сравнивать два алгоритма.
Один работает столько миллисекунд, другой работает столько миллисекунд.
И так понимать, какой из алгоритмов эффективнее,
какой из алгоритмов предпочесть для решения данной задачи.
Но у нас уже в предыдущих курсах возникали ситуации, когда мы точно знали,
что один алгоритм заведомо эффективнее другого.
Например, мы проходили контейнер deque.
Чем он был лучше, чем вектор?
Итак, вот давайте снова вспомним тот самый пример.
Во-первых, подключим сразу profile.h,
который вы уже написали в предыдущих видео.
Вот он.
Тут у нас есть класс LogDuration и макрос LogDuration,
который мы сейчас будем использовать.
Давайте сравним вектор и дек, а если точнее,
попробуем повставлять в начало вектора и в начало дека.
Вспомним, что вставлять в начало вектора гораздо менее эффективно,
чем вставлять в начало дека.
Итак, я подключаю модули дек, вектор, iostream, чтобы выводить.
И что я делаю?
Я измеряю сначала эффективность
вектора.
Создаю пустой вектор, скажем, целых чисел
и вставляю в его начало последовательно 10 в 5-й
чисел с помощью метода insert.
Вставляю в начало вектора очередное число.
И то же самое делаю для дека.
[БЕЗ_ЗВУКА]
[БЕЗ_ЗВУКА] Создаю
пустой дек и вставляю в его начало с помощью метода insert.
Как мы уже знаем из второго курса, вставка в начало дека будет эффективнее.
Давайте это проверим.
Запустим этот код и увидим,
что вставка в начало вектора 100 000 элементов заняла больше полутора секунд,
в то время как вставка в начало дека 100 000 элементов заняла всего 9 миллисекунд.
Итак, это первый пример, когда мы заранее уже знали, каков будет исход,
каков будет результат сравнения двух алгоритмов.
Хорошо, давайте рассмотрим еще один пример.
Я рассказывал,
что если у вас есть какой-то алгоритм, скажем, lower_bound,
есть глобальная функция lower_bound в модуле алгоритм, а еще бывают контейнеры,
у которых есть метод lower_bound, например, контейнер множества.
И я говорил, что если у вас есть такая ситуация, когда у вас есть одноименные
функция и метод, лучше использовать метод, он будет заведомо эффективней.
И некоторые слушатели уже с этим успели столкнуться.
Давайте я на примере множества продемонстрирую,
что действительно метод lower_bound эффективней,
чем глобальная функция lower_bound, если ее вызывать для множества.
Я вот здесь функцию main переименую, чтобы она нам не мешалась.
И перехожу вот сюда.
Подключаю сет, вектор нам здесь не нужен.
Оставляю profile.h и начинаю замерять.
Я создаю одно-единственное множество целых чисел,
назову его numbers и заполню его, скажем, тремя миллионами чисел.
Пишу цикл for от нуля до трех миллионов
и добавляю эти числа в множество.
Вот у меня есть множество из трех миллионов элементов,
давайте я попробую в нем поискать какое-нибудь число, например, миллион.
Я сохраню сразу это число, которое я буду искать,
в константную переменную, вот у меня число миллион, и теперь я буду мерить.
Как эффективнее найти lower_bound с этим числом?
Макрос LogDuration.
Сначала я попробую использовать глобальную функцию lower_bound.
Ну и давайте вызовем
lower_bound(begin), end.
И, собственно, найдем это самое число.
И выведем, каким это число получилось.
Это должно быть это самое число x.
Это первый вариант, как поискать число x.
И второй вариант — это использовать
метод lower_bound.
numbers.lowerbound(x).
И это будет уже метод lower_bound.
Посмотрим, что быстрее.
Запускаем.
И что-то не скомпилировалось,
а именно вот здесь, потому что я вызвал метод lower_bound.
Он вернул мне итератор, я попытался вывести итератор.
Итератор вывести нельзя, надо его перед этим разыменовать с помощью звездочки.
Попробую еще раз.
Компилируется.
Запускается.
И мы видим,
что глобальная функция lower_bound работала почти секунду, в то время
как с помощью метода lower_bound мы нашли искомое число меньше, чем за миллисекунду.
Ну и действительно вывелось то самое число миллион дважды.
Итак, метод lower_bound эффективней, чем функция lower_bound,
и это мы тоже знали изначально и без измерений.
Вам не надо было попытаться написать вызов глобальной функции lower_bound и вызов
метода и сравнивать их.
Вы заранее знали, что вызов метода эффективней.
Хорошо, мы чуть попозже поговорим подробнее, почему так происходит,
и пока что рассмотрим третий пример.
Третий пример еще более простой и понятный,
а именно сравнение функций lower_bound и функции find_if.
Давайте вспомним, что же делает функция lower_bound?
Она находит в отсортированном наборе чисел первое число, даже первый элемент,
необязательно число, первый элемент, который больше либо равен данному.
И в принципе то же самое мы могли бы сделать с помощью функции find_if.
Но мы уже заранее знаем, что функция lower_bound умная,
она делает бинарный поиск, в то время как find_if запускает цикл for.
Поэтому lower_bound заведомо эффективнее.
Давайте все-таки это на всякий случай еще раз проверим.
А именно давайте объявим вектор,
в котором будет миллион чисел.
Заведем константу NUMBER_COUNT со
значением миллион и заполним
вектор миллионом чисел.
[БЕЗ_ЗВУКА] Давайте,
скажем, добавим вектор, число и
умножить на 10.
Вот мы заполнили такой вектор, давайте поробуем в нем что-нибудь поискать.
Ну, например, будем искать число,
я занесу его в константу, ну, скажем, 7654321.
Вот так.
7 654 321.
Ну и давайте я это число поищу какое-то фиксированное количество раз,
например, 10 для начала.
Итак, я заполнил вектор вот такими числами, и теперь я пытаюсь в
нем поискать первое число, которое больше либо равно, чем number.
Снова используем макрос LogDuration.
В первом случае я поищу с помощью lower_bound.
[БЕЗ_ЗВУКА] Делаю в Query_Count поисков.
lower_bound (begin(v)),
end(v) и ищу число NUMBER.
Вот втором случае я поищу это самое число
с помощью find_if.
Как я это сделаю?
Я вызову функцию find_if.
Но здесь уже надо передать, конечно, не число, а λ-функцию,
которая будет описывать, какое число мы ищем.
Как эта λ-функция должна выглядеть?
Эта λ-функция принимает очередное число и для него должна сказать,
подходит оно нам или нет.
Оно нам подходит, если оно больше либо равно, чем x.
И поскольку я в теле этой функции использую еще x, его надо захватить,
то есть упомянуть в квадратных скобках λ-функции.
Итак, вот у меня два кода, давайте сравним, какой же из них быстрее.
Правда, здесь надо использовать не x, а NUMBER, конечно.
Eclipse мне об этом любезно напомнил.
Все, давайте запускать.
Итак, поиск с помощью lower_bound работал ноль миллисекунд, ну то есть очень мало.
А поиск с помощью find_if работал 123 миллисекунды.
То есть lower_bound заведомо быстрее, и мы об этом, конечно же, и так заранее знали.
Итак.
О чем же мы сейчас будем разговаривать?
О том, что необязательно, для того чтобы понять, какой алгоритм эффективнее,
для того чтобы понять, какой алгоритм предпочесть для решения вашей задачи,
необязательно для этого эти алгоритмы программировать и замерять.
Иногда можно заранее знать, какой алгоритм вам больше подходит.
Ровно об этом мы поговорим далее.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
