Общение процессов в MPI

Всех приветствую в третьей серии путешествия по миру параллельного программирования. В самом начале которого я писал о том, что MPI расшифровывается как «интерфейс обмена сообщениями». Пришло время разобраться, с помощью каких функций осуществляется обмен сообщениями между процессами и как его контролировать.

Набор статей про библиотеку MPI разрастается, поэтому я решил привести список предыдущих «серий». Итак, мы уже умеем:
устанавливать MPI в Linux Ubuntu
настраивать Eclipse для работы с MPI
писать простейшую программу с помощью базовых функций MPI

Интерфейс MPI предоставляет нам очень широкий набор различных функций для обмена сообщениями, но сейчас я затрону только самые базовые из них.

Функции отправки сообщения MPI_Send и MPI_Isend

В чем отличие блокирующих функций от неблокирующих? Первые сразу после отправки полностью останавливают выполнение программы до тех пор, пока отправленное сообщение не будет получено. Соответственно, вторые не останавливают исполнение программы. Наличие такого инструмента дает очень большой простор для творчества.

читать далее «Общение процессов в MPI»

Реализация парсера математических выражений на С++

Доброго времени суток, дорогие гости! Сегодня мы будем программировать одну очень интересную штуку. Алгоритм распознавания и вычисления математических выражений, проще говоря, парсер. Он очень активно использует постфиксную запись выражения, о ней мы тоже поговорим, и научимся программно ее получать.

Программа была написана мной на втором курсе, сразу после реализации стека, в качестве учебного задания. В принципе, к ней можно добавить графический интерфейс и получить полноценный калькулятор, вычисляющий целые арифметические выражения, но я не стал.

Итак, кто же такой парсер и чем он занимается? Давайте разбираться.

Задача

Наш парсер математических выражений должен уметь распознавать и вычислять такие операции:
— сложение, вычитание, умножение, деление;
— возведение в степень, остаток от деления(%);
— факториал;
— логическое И, логическое ИЛИ, логическое отрицание;
— синус, косинус, тангенс, арксинус, арккосинус, арктангенс;

читать далее «Реализация парсера математических выражений на С++»

Реализация стека на базе массива и на линейном списке

stack imageДоброго времени суток! Сегодня мы посмотрим на реализацию совсем простой вещи — собственного стека на базе массива и на базе линейного списка. Код был мной написан на втором курсе, достаточно давно, перед написанием статьи я сдул с него пыль и немного подкорректировал страшные названия переменных, навел марафет. Теперь его можно показывать, хоть и осторожно.

Кратко о том, что такое стек. Это такой тип данных, в котором они организованны по принципу LIFO(last in — first out). По русски говоря, последним пришел, первым вышел. Отличный пример для визуализации это книжная стопка, верхняя книга последняя пришла и, если вы не собираетесь пугать кошку грохотом, первая ушла.

Реализация простейших структур данных — это отличный способ их изучить. Можно прочитать сотню книг про стек, но пока вы его не напишите самостоятельно, вы не подружитесь. Я писал реализацию на языке программирования С++, используя классы. Два стека — два класса и при большом желании можно запаковать их в отдельный файл и подключать к другим проектам.

Дорогие читатели, давайте заводить дружбу со стеком, поехали!

читать далее «Реализация стека на базе массива и на линейном списке»

Измерить время исполнения кода на C/C++ с помощью функции clock()

Доброго времени суток! Представьте, вы написали очень крутую программу, она решает поставленную задачу, алгоритм отточен до мельчайших деталей, код отрефакторен так, что сам господь улыбнется при его чтении, все отлично! Вы пришли на работу(учебу, тусовку пограмистов) и всем его показали, и тут «Васек» спросит: «А быстро работает?». И тут вы понимаете свою ошибку! Не измерили скорость работы программы! Не потестировали с разной нагрузкой, и вообще, там может быть куча дыр связанных, которые покажутся только при стрессовой нагрузке.

Ладно, хватит. На самом деле, я просто хотел написать о том, как измерить скорость исполнения любого участка кода. Сделать это можно на любом языке программирования, каждый язык каким либо образом да сможет обратиться к системе и спросить текущее время в миллисекундах.

Я расскажу про C/C++ просто потому что именно на этих языках чаще всего измерял скорость работы кода, для самых разнообразных учебных задач. От сортировки пузырьком до топологической сортировки графов.

Специальный тип данных clock_t в C/C++

Это не что иное, как алиас(кличка, переименование) стандартного арифметического типа данных. В значение ставится количество процессорных тиков с момента его запуска. Получить это значение можно с помощью функции clock() из библиотеки <time.h>. Для того, чтобы перевести количество тиков в секунды используется константа из той же библиотеки CLOCKS_PER_SEC. Просто делим и получаем ответ.

Пример:

//Специальный тип данных из библиотеки time.h
clock_t currentTime;
//Берем текущее системное время
currentTime = clock();
//Участок кода, который нужно измерить
for(int i = 0; i < 9000; i++) {
    i *= i;
}
//Берем разницу
currentTime = clock() - currentTime;
//Переводим в секунды
currentTime = (double)currentTime / CLOCKS_PER_SEC;

Генерация случайных чисел на C/C++ с помощью rand()

Приветствую всех, кто заскочил. В это короткой заметке будет пара слов о генерации псевдослучайных чисел на C/C++. В частности о том, как работать с самой простой функцией генерации — rand().

Функция rand()

Находится в стандартной библиотеке С++(stdlib.h). Генерирует и возвращает псевдослучайное число в диапазоне от 0 до RAND_MAX. Эта константа может отличаться в зависимости от компилятора или архитектуры процессора, в основном, это максимальное значение типа данных unsigned int. Параметров не принимает и никогда не принимала.

Для того, чтобы генерация свершилась, нужно выставить семя(seed) с помощью вспомогательной функции из той же библиотеки — srand(). Она принимает число и ставит его в качестве отправной точки в генерации случайного числа. Если семя не выставить, то при каждом запуске программы, мы будет получать одинаковые случайные числа. Самым очевидным решением является отправить туда текущее системное время. Сделать это можно с помощью функции time(NULL). Эта функция находится в библиотеке time.h.

С теорией разобрались, нашли все функции для генерации случайных чисел, теперь давайте погенерируем.

Пример использования функции генерации случайных чисел rand()

#include <ctime>
#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
    srand(time(NULL));

    for(int i = 0; i < 10; i++) {
        cout << rand() << endl;
    }

    return 0;
}

Ранд нагенерировал нам 10 случайных чисел. В том, что они случайные вы можете убедиться, запуская программу вновь и вновь. Но этого недостаточно, поэтому нужно поговорить о диапазоне.

Выставить границы диапазона для rand()

Чтобы сгенерировать число в диапазоне от A до B включительно, нужно написать так:

A + rand() % ((B + 1) - A);

Значения границ могут быть в том числе и отрицательными, что позволяет генерировать отрицательное случайное число, посмотрим пример.

#include <ctime>
#include <iostream>
#include <cstdlib>

using namespace std;

int main() {
    srand(time(NULL));

    int A = -2;
    int B = 8;

    for(int i = 0; i < 100; i++) {
        cout << A + rand() % ((B + 1) - A) << endl;
    }

    return 0;
}