Это продолжение моей серии об алгоритмах - см. Предыдущий пост, чтобы наверстать упущенное, где мы рассмотрели яичницу и основы алгоритмов. Это краткое введение в алгоритмы, почему они полезны и как мы можем их анализировать. Повторяю заявление об отказе от ответственности: у меня нет образования в области компьютерных наук или какого-либо образования в области математики или естествознания за пределами школы, так что это будет бред абсолютно новичка.
Как веб-разработчик, я всегда считал алгоритмы в основном теоретическими и абстрактными. На базовом уровне я использую и пишу алгоритмы в своей повседневной работе, но правильные алгоритмы, которые перебирают миллионы веб-страниц и петабайты данных, не являются моей игрой. Они для ученых и инженеров. Поэтому, учитывая, что я использовал только очень простые, упрощенные алгоритмы, изучение и понимание их, вероятно, было пустой тратой времени, верно? Неправильный! Алгоритмы - даже на упрощенном уровне - могут быть полезны для развития в любой дисциплине. Мыслительный процесс, лежащий в основе разработки алгоритма, - это методология, которая может принести пользу инженеру, просматривающему миллиард веб-страниц, или даже веб-разработчику, просто выполняющему итерацию по массиву для извлечения определенного значения.
В этом посте мы рассмотрим пару очень распространенных простых проблем с кодированием и то, как решения могут сильно различаться по производительности в зависимости от того, как они спроектированы.
Наибольший общий делитель
Для простоты в этом посте мы сосредоточимся на одной конкретной проблеме. Давайте посмотрим на проблему наибольшего общего делителя и попробуем разработать простой алгоритм для ее решения.
Наибольший общий делитель - это обычная математическая головоломка. Что мы хотим сделать, так это передать нашему алгоритму два целых числа, а затем заставить наш алгоритм вернуть наибольшее целое число, которое делит оба ввода. Например, если мы передаем наш алгоритм 10 и 30, мы хотим, чтобы наш алгоритм возвращал 10 (поскольку это наибольшее число, которое входит в оба наших входа). Звучит знакомо? Возможно, вы помните это из математики в начальной школе - почти наверняка вы это сделали. Угадай что, теперь он снова преследует тебя!
Теперь, когда у вас есть вступление, давайте рассмотрим другой пример. Какой наибольший общий делитель 24 и 32? Вы можете понять это…? Это 8! Достаточно просто. Зачем для этого нужен алгоритм? Ну, а вы знаете наибольший общий делитель для 1245308024 и 118210400…? Нет? Ладно, я тоже, так что нам может понадобиться компьютер, чтобы помочь нам здесь.
Хорошо, тогда давайте посмотрим на создание алгоритма! Как уже упоминалось, и входные, и выходные будут только целыми числами, а не числами с плавающей запятой или десятичными числами. Кроме того, все отзывы будут положительными - здесь нет негатива, большое спасибо!
Итак, у нас есть рабочий алгоритм. Это довольно просто. У нас есть переменная gcd, в которой хранится наш наибольший общий делитель. gcd начинается как 1. Затем мы используем цикл for для перебора чисел 2 до минимума a и b (наибольший общий делитель должен быть меньше обоих входных значений). Нам досадно приходится использовать min(a, b) + 1 в python, потому что верхняя граница диапазона не включает. Для каждой итерации мы проверяем, входит ли i в оба a и b. Если это так, мы обновляем gcd на i. Цикл продолжается до тех пор, пока мы не дойдем до минимума a и b. Алгоритм возвращает значение gcd. Простой.
Давайте посмотрим на это с помощью реальных чисел, а не абстрактных букв. У нас есть два входа: 5 и 15. gcd изначально установлен на 1. Стандарт! Затем мы переходим от 2 к 5. 5, потому что это меньший из наших двух входов. Следовательно, i равно 2 на первой итерации, затем он равен 3, затем 4 и, наконец, 5. Для каждой итерации мы проверяем, входит ли i в оба 5 и 15. Если это так, мы обновляем значение на gcd. В результате gcd обновляется до 3 - поскольку 3 входит как в 5, так и в 15. И на последней итерации gcd обновляется до 5 - поскольку 5 входит как в 5, так и в 15. На выходе алгоритм возвращает 5.
Достаточно просто. В большинстве случаев это работает. Однако в нашем алгоритме есть некоторые недостатки. Наш первый пример с использованием 3 и 5 был довольно простым. Мелочь для этого алгоритма.
Давайте немного увеличим его и посмотрим, как работает наш алгоритм с некоторыми более крупными целыми числами. Давайте попробуем с 600 и 1280.
Это вывод консоли. В алгоритм я добавил несколько полезных мер, которые помогут нам оценить эффективность нашего алгоритма. Loops executed не требует пояснений - количество итераций, которые делает наш алгоритм перед возвратом наибольшего общего делителя. И Elapsed Time - время запуска функции в секундах. И, наконец, самое главное, output, наибольший общий делитель. В этом примере мы видели, используя 600 и 1280: наибольший общий делитель равен 60, алгоритм выполняет 599 циклов, а время, необходимое для выполнения, составляет 0.0002 секунд. Все идет нормально.
Давайте продвинем алгоритм немного дальше, используя входные параметры 28851538 и 1183019.
У нас есть та же информация, что и раньше: результат, количество циклов и прошедшее время. Мы видим, что количество петель равно 1183018, что является просто минимальным вводом минус один. В последнем примере у нас было 599 циклов, потому что наш минимальный ввод был 600. Это кое-что говорит нам о нашем вводе. Чем больше наш минимальный ввод, тем менее неэффективным будет наш алгоритм, потому что он должен будет пройти больше итераций цикла. Это серьезная проблема масштабирования нашего алгоритма. Мы видим, что это отображается в прошедшем времени, которое теперь составляет 0.25 секунд. Это может показаться небольшим, но для вычислений это довольно долгое время. Если вы считаете, что этот алгоритм может быть частью всего веб-приложения, которое выполняет целую кучу команд, извлекает данные и запускает задачи - потратить 0.25 секунд только на это немного анализа действительно неэффективно.
А теперь позвольте мне четко сформулировать суть - давайте воспользуемся вводом еще большего размера, 253102380 и 3402918274.
Два гораздо больших числа, которые действительно расширяют возможности нашего алгоритма. Как и ожидалось, большие целые числа резко снижают производительность. Прошло почти 55 секунд! Это слишком долго. Другой интересный момент в этом конкретном примере заключается в том, что наибольший общий делитель этих двух огромных входных данных равен 2! Несмотря на это, наш алгоритм по-прежнему проходит через 253 102 379 итераций - верно, более четверти миллиарда итераций цикла!
Одним из реальных недостатков нашего алгоритма было увеличение цикла на единицу каждый раз. Многие из этих итераций цикла бессмысленны. Например, если вы вычисляли наибольшее общее деление двух простых чисел, таких как 40 и 200. Вы, вероятно, не стали бы начинать с 1 и работать дальше. Вы ищете наибольший общий делитель, поэтому имеет смысл начать с 40 и постепенно уменьшаться. Чаще всего это будет меньше работы. В этом конкретном случае начало с 40 имеет смысл, поскольку 40 входит как в 40, так и в 200, так что вы получите свой наибольший общий делитель с первой попытки.
Проверка каждого числа кажется очень неэффективной, если бы только был более эффективный способ! Хммм…
Евклидов алгоритм
Алгоритм Евклида был разработан древнегреческим математиком Евклидом около 300 г. до н. Э. Алгоритм Евклида - чрезвычайно эффективный метод вычисления наибольшего общего делителя двух чисел - даже двух огромных чисел!
Утверждение алгоритма Евклида исходит из базового наблюдения того, что общего имеет наибольший общий делитель. Евклидов алгоритм работает на предпосылке, что если число делится как на a, так и на b, то это же число должно делить их сумму. А значит, по расширению, это число также должно делить их разницу. Давайте посмотрим на пример.
Это итеративный пример алгоритма Евклида - большинство реализаций, вероятно, будут использовать рекурсию, но это тема другого сообщения в блоге. Итеративное решение просто означает, что мы используем цикл. В нашем примере, если b истинно (т.е. ненулевое), мы вводим цикл while до b = 0. В этом цикле мы создаем переменную для запоминания значения b, устанавливаем b на остаток от a % b и устанавливаем a на значение b в начале итерации. Мы продолжаем этот процесс до тех пор, пока b не станет 0, что означает, что мы нашли значение, которое делится с остатком 0.
Давайте посмотрим на это с некоторыми цифрами. Если мы вводим 18 и 24, b назначается 24, а a назначается 18. Поскольку b это 24, а не 0, мы входим в цикл while. Нашей вспомогательной переменной b_store присваивается значение b, 24. b установлен на 18 % 24, то есть 6. Наконец, a устанавливается на исходное значение b в начале итерации цикла, которое в данном случае равно 24. Теперь (после первой итерации цикла) наши значения для a и b: 24 и 6 соответственно. Мы снова проходим цикл - store_b становится 6, b становится 0 (так как 6 переходит в 24 четыре раза), а a устанавливается на 6. Поскольку b now является ложным, поскольку он равен 0, мы выходим из цикла while, и наш алгоритм возвращает 6 - значение a - как наш наибольший общий делитель. Умно, верно!
Давайте посмотрим, как это работает.
Здесь мы сопоставляем два алгоритма друг другу для одного и того же набора входных данных, 100 и 100,000. Затраченное время обоих тривиально, хотя Евклид быстрее. Следует отметить количество выполненных циклов. Наш наивный алгоритм начинается с 1 и работает до 100. Следовательно, выполняется 99 циклов. Однако алгоритм Евклида выполняет только 2 цикла. Он начинается с 100 - и поэтому всего через пару шагов вы знаете, что 100 будет наибольшим общим делителем, поэтому дальнейшие итерации не принесут пользы.
Затем давайте попробуем это на некоторых числах. Давайте снова воспользуемся 288515380 и 3402918274. Это заняло около 123 секунд, когда мы использовали наш наивный алгоритм.
Результаты есть! Наш наивный алгоритм работает ужасно, как и ожидалось - на этот раз затраченное время составляет 68.5 секунд! Слишком медленно для любого приложения. И, как обсуждалось ранее, выполняет гигантские 288515379 циклы. С другой стороны, наш алгоритм Евклида работает намного лучше. Несмотря на эти два огромных индекса, наш евклидов алгоритм возвращает правильный результат 2 всего за 23 итераций цикла и за доли секунды, если быть точным, 0.000035 секунд! Довольно круто, да ?!
Заключение
В этом посте мы накапливаем наши знания об алгоритмах, рассматривая реальный алгоритм, алгоритм Евклида, и сравнивая его эффективность с наивным и гораздо менее эффективным алгоритмом, который решает ту же проблему. Этот пример показывает, что даже выполнение относительно простых вычислительных задач, таких как поиск наибольшего общего делителя двух входных данных с помощью неэффективных методов, может подтолкнуть ваш новый модный Macbook к краю и превзойти его возможности. А с введением алгоритма Евклида он подчеркнул огромные преимущества и экономию времени между наивным решением и более сложным решением проблемы. В реальном мире алгоритм Евклида широко используется для очень эффективного решения вычислительных задач - он может использоваться для сокращения больших дробей до их простейших мер и является ключевым компонентом метода шифрования RSA. Я включил несколько дополнительных ресурсов ниже (которые подходят для начинающих) по алгоритму Евклида для тех, кто заинтересован.
Спасибо за прочтение. Это вторая публикация в серии об алгоритмах, разработанных для новичков, в том числе и я, которая направлена на то, чтобы приоткрыть (хотя бы немного!) Крышку на алгоритмы, на то, что они из себя представляют и как они работают. Вы можете прочитать первый пост здесь.
Свяжитесь с нами в Твиттере или в комментариях, если у вас есть какие-либо мысли!
