Этот курс является продолжением курса "Основы разработки на 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++
Из урока
Move-семантика и базовая многопоточность
Познакомьтесь с преподавателями
Полднев Антон Вячеславович
Яндекс
Шишков Илья Ивановичкандидат технических наук
Яндекс
[БЕЗ_ЗВУКА] В предыдущем видео мы с вами узнали,
как с помощью функции async запускать асинхронные операции.
Теперь же давайте посмотрим, как с их помощью
распараллеливать программы и ускорять их за счёт параллелизма.
И давайте рассмотрим пример, который, на самом деле,
достаточно близок к практике, но, конечно же, сильно упрощён.
Итак, смотрите.
У нас есть переменная matrix, являющаяся вектором векторов.
Это переменная, которая представлять будет собой матрицу,
причём, квадратную для простоты в нашей задаче.
Эта матрица каким-то образом генерируется с помощью функции GenerateSingleThreat и
впоследствии обрабатывается.
В данном случае это выполняется с помощью функции SumSingleThreat.
И из её названия вы можете догадаться,
что эта функция просто находит сумму всех элементов в этой матрице.
Вот она бежит по строкам матрицы, потом для каждой строки бежит по всем
элементам этой строки и всё это суммирует в переменную sum, которую возвращает.
Так у нас обрабатывается матрица.
Давайте посмотрим, как устроена функция Generate.
Вот как она устроена.
Она объявляет тоже переменную result, типа вектор векторов,
сразу же задаёт этому вектору размер требуемый.
Это, собственно, размер нашей квадратной матрицы, которую надо сгенерировать.
И вызывает другую функцию GenerateSingleThread,
которая у нас является шаблоном, принимает некий контейнер векторов.
И, собственно, что она делает?
Она идёт по строкам, для каждой строки вызывает reserve
и столько раз, сколько попросили,
вот column_size параметр, в зависимости от того, чему он равен,
столько раз она выполняет push_back и в качестве значения очередной
ячейки использует результат побитого операцией
xor для номера строки и номера столбца.
На самом деле, способ заполнения матрицы именно,
как мы рассчитываем её элементы, он в данном примере не важен.
Это просто какой-то способ, как-то она заполняется.
Вот так мы генерируем нашу матрицу.
У вас конечно может возникнуть вопрос, а зачем мы написали так сложно?
Зачем у нас функция GenerateSingleThread вызывает шаблон SingleThread?
Это сделано как бы с прицелом на дальнейшее развитие этого примера.
Всё это нам пригодится в ближайшем будущем.
Естественно, если нам бы просто надо было написать функцию GenerateSingleThread,
мы бы дополнительно шаблон писать не стали.
Зачем усложнять код?
Итак, мы рассмотрели эту программу.
Теперь давайте мы её скомпилируем и запустим.
И посмотрим на результат.
Смотрите, наша программа работала суммарно
чуть более полутора секунд.
При этом генерация матрицы выполнялась 1254 милисекунды, а суммирование — 375.
И мы смотрим на эти числа и думаем: нет,
для нашей задачи это медленно, надо бы ускорить.
Я в очередной раз напомню, что ускорять программу стоит,
только если вы померили, сколько она работает, и понимаете,
что для вас и вашей ситуации, вашей задачи это недостаточно быстро.
Вот мы померили и для себя решили: надо ускорять.
Что мы делаем?
Мы смотрим, что генерация занимает гораздо больше времени, чем суммирование.
Поэтому давайте попробуем ускорить генерацию.
Это должно нам дать больше пользы.
Хорошо, как мы будем ускорять генерацию матрицы?
Хотя, если так вот ещё раз посмотреть,
то в однопоточной версии у нас уже всё сделано куда уж лучше.
Мы и для каждой строки reserve вызываем, и вот здесь,
когда генерируем результирующую матрицу, сразу задаём ей нужный размер,
то есть лишних аллокаций у нас вообще не происходит.
И мы на каждый элемент матрицы тратим одну операцию,
то есть быстрее тут не придумаешь.
И вот поэтому нужно попробовать матрицу нашу генерировать многопоточно,
параллельно.
Давайте посмотрим, как матрица генерируется в один поток.
Вот так вот: мы заполняем сначала первую строку, потом вторую, потом третью,
и так далее до конца, ячейка за ячейкой последовательно.
Вот так выполняется однопоточная генерация матрицы.
Теперь представим, давайте, как мы могли бы заполнять эту матрицу,
например, в четыре потока.
Мы бы разделили матрицу на несколько частей,
каждому бы потоку выдали бы по одной части и
параллельно бы этим потоки заполнили бы каждый свою часть,
и за счёт этого мы бы сэкономили время и быстрее бы выполнили генерацию.
Давайте мы эту схему реализуем в коде.
Как мы это будем делать?
Мы с вами напишем функцию
GenerateMultiThread.
Она точно так же будет принимать размер матрицы желаемый, но, кроме этого,
она будет принимать ещё один параметр, это размер страницы page_size.
То есть вот мы сказали,
что разобъём матрицу на несколько частей и будем их передавать в потоки.
Вот это желаемый размер страницы.
Как наша функция будет устроена?
Смотрите, мы точно так же создадим
результирующий вектор, даже точно так же его вернём.
И, вы видете, мы сразу задали нашему вектору размер,
то есть у нас уже есть какой-то набор векторов.
И смотрите, мы хотим наш этот вектор result разбить на несколько частей,
даже на несколько страницу.
Что нам здесь может помочь?
На самом деле, здесь отлично подходит шаблон paginator,
который вы писали в задачах к блоку про шаблоны классов.
Давайте я воспользуюсь, он у меня уже заготовлен,
я его скопирую
и вставлю в наш код, вот в начало, например.
Вот он, вот у нас класс paginator,
он внутри себя хранит вектор поддиапазонов.
Вот шаблон Subrange.
Вы всё это уже знаете, вы эту задачу решали.
И вот функция Paginate, которая, собственно,
принимает контейнер и размер страницы и возвращает нам Paginator.
Давайте мы им и воспользуемся.
Делаем следующее.
Мы собираемся запускать асинхронные операции, значит,
нам нужен заголовочный файл future.
[БЕЗ_ЗВУКА] Мы
заводим вектор,
который будет хранить future на void, futures.
Дальше for auto page Paginate
result page_size.
То есть мы берём этот result наш и нарезаем на страницы размера page_size.
Здесь в вектор futures мы добавляем
результат вызова async
от лямбды.
Что наша лямбда будет делать?
Наша лямбда будет вызывать GenerateSingleThread.
Мы же запустили одну операцию для одного потока,
поэтому вызываем GenerateSingleThread.
Сюда передаём нашу страницу page.
Также у нас просят первый, вот у нас есть подсказка параметра,
здесь нужно передать ещё номер первой строки.
Мы же используем номер строки для формирования значения ячеек,
поэтому надо передать номер строки.
Поэтому мы заводим переменную first_row равно нулю.
Сюда её передаём.
И в конце после вызова async мы её увеличиваем на page_size,
потому что мы передали в поток страницу размера page_size,
первая строка в ней имеет номер ноль, последняя page_size минус один,
поэтому первая строка следующей страницы будет иметь номер page_size.
И последний параметр, который у нас тут остался, это column_size,
размер одной колонки, это size.
Ну и теперь вот эти все page first
row и size надо захватить в лямбду,
чтобы они работали.
Хорошо, нам надо скомпилировать, потом надо будет запустить.
Давайте мы вот это вот число, которое у нас тут в консоли болтается,
это сумма элементов нашей тестовой матрицы, давайте мы это число сохраним,
чтобы нам потом проверить, что после многопоточной генерации у нас
получилась точно такая же матрица с точно такой же суммой.
Вот теперь давайте мы пока скомпилируем.
Пока всё компилируется хорошо.
И теперь вот сюда давайте добавим вызов
нашей многопоточной
генерилки.
И в качестве размера страниц передадим, например, 2000.
Давайте скомпилируем ещё раз.
Компилируется, отлично!
Я специально сначала присваиваю в матрицу результат однопоточной генерации, а потом
многопоточной, чтобы нам запустить и то, и то, и сравнить, что работает быстрее.
Запускаем.
Во-первых, проверяем, что после генерации
сумма у нас оказалась правильная.
Если посмотреть, то да.
Матрица сгенерировалась правильно.
А теперь смотрим на самое интересное.
Самое интересное, что многопоточная генерация матрицы
оказалась в два раза быстрее, чем однопоточная.
То есть мы с вами с помощью асинхронных операций, с помощью
вызова функции async смогли реализовать схему с параллельной генерацией матрицы и
за счёт этого ускорили эту стадию нашей программы в два раза.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
