Алгоритм — это конечная последовательность действий или шагов, направленных на решение конкретной проблемы или задачи.
Например, алгоритм для решения задачи нахождения факториалов может выглядеть примерно так:
Задача: Определить факториал числа n.
|
1 2 3 4 |
Инициализируем переменную fact = 1 Для каждого значения переменной i в диапазоне от 1 до n: Умножаем fact на i fact содержит факториал n |
Сейчас алгоритм написан в текстовой форме. Если бы он был написан на языке программирования, мы бы называли его кодом.
Напишем код для нахождения факториала числа на языке C++:
|
1 2 3 4 5 6 7 |
int factorial(int n) { int fact = 1; for (int i = 1; i <= n; v++) { fact = fact * i; } return fact; } |
Программирование — это про структуры данных и алгоритмы. Структуры данных используются для хранения данных, а алгоритмы используются для решения конкретных проблем с использованием этих данных.
Структуры данных и алгоритмы (сокр. «DSA», от англ. «Data Structures and Algorithms») подробно рассматривают решения стандартных проблем и дают представление о том, насколько эффективно использовать каждое из них. Они также дают возможность оценить эффективность алгоритма. Это позволяет выбрать наиболее оптимальный вариант из всех возможных.
Использование структур данных и алгоритмов для создания масштабируемого кода
Время — драгоценный ресурс
Предположим, что Вика и Коля пытаются решить простую задачу по нахождению суммы первых 1011 натуральных чисел. Пока Коля писал алгоритм, Вика уже его реализовала, доказав, что это так же просто, как дважды два четыре…
Алгоритм (Коли)
|
1 2 3 4 |
Инициализируем sum = 0 Для каждого натурального числа n в диапазоне от 1 до 1011 (включительно): Добавляем n к sum sum - это ответ |
Код (Вики)
|
1 2 3 4 5 6 7 |
int findSum() { int sum = 0; for (int i = 1; i <= 100000000000; i++) { sum += i; } return sum; } |
Вика и Коля чувствуют себя счастливыми, что они смогли создать что-то свое за совсем короткое время. Давайте проникнем на их рабочее место и подслушаем их разговор.
Вика: Давай запустим этот код и узнаем сумму.
Коля: Я запускал этот код несколько минут назад, но он все еще не показывает результат. Что с ним не так?
Ой, что-то пошло не так! Компьютер — это одна из наиболее предопределенных систем. Просто повторить запустить код еще раз — не поможет. Поэтому давайте проанализируем, что не так с этим простым кодом.
Время и память — одни из самых ценных ресурсов для компьютерной программы.
Время, затраченное компьютером на выполнение кода:
|
1 |
Время выполнения кода = количество инструкций * время выполнения каждой инструкции |
Количество инструкций зависит от используемого вами кода, а время выполнения каждой инструкции зависит от вашей компьютерной системы и компилятора.
В этом случае общее количество выполненных инструкций (скажем, x) составляет x = 1 + (1011 + 1) + (1011) + 1, что составляет x = 2 * 1011 + 3.
Допустим, компьютер может выполнить y = 108 инструкций за одну секунду (это может изменяться в зависимости от конфигурации вашей системы). Время выполнения вышеприведенного кода равно:
|
1 2 3 |
Время выполнения y инструкций = 1 секунда Время выполнения 1 инструкции = 1 / y секунд Время выполнения x инструкций = x * (1/y) секунд = x / y секунд |
Таким образом, время выполнения кода = x / y= (2 * 1011 + 3) / 108 (больше, чем 33 минуты).
Можно ли оптимизировать алгоритм, чтобы Вика и Коля не ждали 33 минуты каждый раз, когда запускают этот код? Я уверен, что вы уже догадались о правильном методе. Сумма первых N натуральных чисел выражается формулой:
|
1 |
Sum = N * (N + 1) / 2 |
Преобразование этой формулы в код будет выглядеть так:
|
1 2 3 |
int sum(int N) { return N * (N + 1) / 2; } |
Этот код выполняется всего в одной инструкции и решает задачу независимо от значения, будь оно даже больше общего числа атомов во вселенной. Результат будет найден мгновенно.
Время, затраченное на решение этой задачи в этом случае, составляет 1/y (что равно 10 наносекундам). Кстати, реакция синтеза водородной бомбы занимает 40-50 нс, что означает, что ваша программа успешно завершится, даже если кто-то сбросит на ваш компьютер водородную бомбу в то время, когда вы запустили свой код.
Примечание: Компьютеры требуют выполнения нескольких инструкций (а не одной) для выполнения операций умножения и деления. Я упомянул только 1 для упрощения.
Больше о масштабируемости
Масштабируемость — это масштаб плюс способность, что означает качество алгоритма/системы обработки задач большего размера.
Рассмотрим задачу обустройства класса на 50 студентов. Один из простейших вариантов решения — забронировать комнату, установить доску, несколько мелков и проблема решена.
Но что, если размер проблемы возрастет? Что, если количество студентов увеличится до 200?
Решение все еще существует, но для его реализации понадобится больше ресурсов. В данном случае, возможно, понадобится гораздо большее помещение (например, театр), проекторный экран и цифровая ручка.
Что, если число студентов возрастет до 1000?
Решение уже не работает или использует слишком много ресурсов, когда размер проблемы увеличивается. Это означает, что решение не масштабируемо.
Что же такое масштабируемое решение?
Если посмотреть на наше первоначальное решение для нахождения суммы первых N натуральных чисел, то оно не было масштабируемым. Это связано с тем, что оно требовало линейного роста времени при линейном росте размера проблемы. Такие алгоритмы также известны как линейно масштабируемые алгоритмы.
Наше второе решение было очень масштабируемым и не требовало дополнительного времени для решения задачи большего размера. Эти алгоритмы известны как алгоритмы постоянного времени.
Память — дорогостоящий ресурс
Память не всегда доступна в изобилии. При работе с кодом/системой, когда требуется сохранить или сгенерировать большое количество данных, критически важно, чтобы ваш алгоритм экономил использование памяти, где это возможно. Например, при хранении данных о людях вы можете сэкономить память, храня только их дату рождения, а не возраст. Вы всегда можете вычислить возраст «на лету», используя дату рождения и текущую дату.
Примеры эффективности алгоритма
Примеры того, что изучение алгоритмов и структур данных позволяют сделать:
Пример №1: Задача поиска возрастной группы
Проблемы, такие как поиск людей определенной возрастной группы, могут легко быть решены немного измененной версией алгоритма бинарного поиска (предполагая, что данные отсортированы).
Простейший алгоритм, который перебирает всех людей по одному и проверяет, попадает ли он в заданную возрастную группу, является линейно масштабируемым. В то время как бинарный поиск характеризует себя, как логарифмически масштабируемый алгоритм. Это означает, что если размер проблемы увеличивается в квадрате, время, затраченное на ее решение, только удваивается.
Предположим, что для поиска людей определенной возрастной группы на группу из 1000 человек требуется 1 секунда. Тогда для группы из 1 миллиона человек:
алгоритм бинарного поиска займет всего 2 секунды, чтобы решить задачу;
наивный алгоритм может занять 1 миллион секунд, что составляет около 12 дней.
Тот же самый алгоритм бинарного поиска используется для нахождения квадратного корня числа.
Пример №2: Задача кубика Рубика
Представьте, что вы пишете программу для решения задачи кубика Рубика.
Эта милая головоломка имеет ошеломляюще большое количество позиций — 43,252,003,274,489,856,000, а это только позиции! Представьте себе количество путей, которые можно пройти на пути к неправильным позициям.
К счастью, способ решения этой проблемы может быть представлен в виде графа. Существует алгоритм графа, известный как алгоритм Дейкстры, который позволяет решить эту проблему за линейное время. Да, вы правильно услышали. Это означает, что он позволяет добраться до решенной позиции в минимальном количестве ходов.
Пример №3: Задача ДНК
ДНК — это молекула, которая несет генетическую информацию. Она состоит из более мелких единиц, которые обозначаются римскими символами A, C, T и G.
Представьте себе, что вы работаете в области биоинформатики. Вам поручено найти вхождение определенного шаблона в цепочку ДНК.
Это известная проблема в академическом сообществе компьютерных наук. И самый простой алгоритм требует времени пропорционального (количество символов в цепочке ДНК) * (количество символов в шаблоне).
Типичная цепочка ДНК содержит миллионы таких единиц. Но не волнуйтесь раньше времени, КМП-алгоритм (сокр. от англ. «Knuth–Morris–Pratt») может выполнить эту задачу за время, пропорциональное (количество символов в цепочке ДНК) + (количество символов в шаблоне).
Оператор * замененный на оператор + приводит к значительным изменениям.
Учитывая, что шаблон состоял из 100 символов, ваш алгоритм стал в 100 раз быстрее. Если бы ваш шаблон состоял из 1000 символов, алгоритм КМП был бы почти в 1000 раз быстрее. То есть, если вы могли найти вхождение шаблона за 1 секунду, теперь вам потребуется всего 1 мс. Можно сказать, что вместо поиска в 1 цепочке, вы можете одновременно искать совпадения в 1000 цепочках подобной длины.
И таких историй бесчисленное множество…
Заключение
В целом, разработка программного обеспечения включает в себя ежедневное изучение новых технологий. Если вы плохо знакомы с алгоритмами, вы не сможете оптимизировать код, который пишете или используете на вашем проекте.
Мы специально говорили о масштабируемости алгоритмов. Программная система состоит из многих таких алгоритмов. Оптимизация любого из них приводит к уменьшению его вычислительной сложности.
Однако важно отметить, что это не единственный способ сделать систему масштабируемой. Например, техника, известная как распределенные вычисления, позволяет независимым частям программы работать на нескольких компьютерах вместе, что делает ее еще более масштабируемой.
Оценить статью:
(3 оценок, среднее: 5,00 из 5)
Загрузка...