Реализация алгоритма Рабина-Карпа на C++

Приветствую вас, друзья мои! Сейчас я расскажу о своей первой курсовой работе, которая была написана и сдана на далеком втором курсе. Суть заключается в реализации и тестировании алгоритма Рабина-Карпа поиска подстроки в строке, в качестве языка программирования мне был рекомендован C++. В принципе больше во вступлении добавить нечего, перейдем сразу к делу.

Суть алгоритма Рабина-Карпа

Алгоритм представляет из себя улучшенную версию последовательного поиска, улучшение заключается в использовании хэш-функции. Это объясняется тем, что сравнить два числа(два хэша) гораздо быстрее и дешевле, чем сравнивать подстроки посимвольно. Сравнивать подстроки придется только один раз, когда хэши совпали, сделать это придется для увеличения надежности и защиты от случая коллизии хэша.

читать далее «Реализация алгоритма Рабина-Карпа на C++»

Общение процессов в 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;