Комментарии 44
Без Канторовича, Карацубы, RSA совсем список не смотрится.
Диффи-Хеллмана еще и Рида-Соломона- они гораздо чаще Карацубы и Канторовича используются, да и мультиполя или Монте-Карло тоже не такие чтоб прямо часто встречающиеся алгоритмы. И Диффи-Хеллмана наверное надо вперед РСА ставить. Канторович и Карацуба- это сильно нишевые какие-то алгоритмы (особенно Карацуба- хоть раз кто-то его использовал из здесь присутствующих?). хотя, если уж тут мультиполе включили в список- то наверно тогда Канторович тоже подходит.
Каждый раз при использовании openssl
Куда уж чаще))
Однако, не знал. С универа запомнилось, что Карацуба начинает заметно выигрывать перед обычным длинным умножением только на очень больших числах- в тысячи знаков, удивлен, что его засунули в SSL- там числа не такие жирные. Сравнение скоростей было на хабре, кстати: https://habr.com/ru/post/262705/
1024 бита - не такие жирные? Причём вроде же в степень возводятся, а не просто умножаются
GMP/gcc давно перешли на Schönhage–Strassen алгоритм (для чисел от 33000 цифр) для умножения и собственный алгоритм для деления, причем некоторые уже умудрились написать в коде еще более сложный алгоритм Фюрера, созданный в 2007. https://en.wikipedia.org/wiki/Fürer's_algorithm
Уж если упомянули openssl, то и NSS (Network Security Services)
Вот теперь будет совсем часто.
Это скорее протоколы и библиотеки, чем алгоритмы. С одной стороны да - это именно то, чего и ожидал увидеть в данной статье (а не математические правила). С другой - всё это всё основано на более фундаментальных алгоритмах, разработанных ранее.
И да, хоть формально это всё появилось в конце XX века - значимыми эти протоколы стали только в XXI веке
Вы не поверите, но я пользовался методом Карацубы. Времени правда утекло с тех пор порядочно, так что подробности надо поднимать из бэкапов. Кстати, до того момента о нём не знал.
Алгоритм Карацубы ещё важен тем, что показал, насколько глубока кроличья нора.
До него предполагали, что если за несколько сотен лет не нашли способ перемножать длинные числа эффективнее, чем столбиком, то такого способа не существует.
они гораздо чаще ... используются
Вы несколько подменяете понятия. В оригинале статья называется "The Best of the 20th Century: Editors Name Top 10 Algorithms". Можно сколько угодно дискутировать на тему, что значит "лучший", но это точно не "чаще", или не столько "чаще". Тем более, что дальше стоИт "по мнению редакции".
Статья переводная и всё же. Если речь идёт о Фортране, то применительно к Советскому Союзу можно вспомнить машинно-ориентированный язык и компиляторы Алмо:
Это была целая эпоха в советском программировании. Большие надежды связывались с Алмо.
Предлагайте свои варианты значимых алгоритмов. Начну с себя:
алгоритм сортировочной станции (преобразование инфиксной нотации в обратную польскую нотацию)
алгоритм Дейкстры (поиск кратчайшего пути в графах)
алгоритм Ахо-Корасик (поиск множества совпадений в строке за один проход)
Топологическая сортировка ;) (каждый запуск make).
Алгоритм MP3. Всунуть психоакустику в алгоритм это вообще гениально!
Так там же и есть FFT из статьи
FFT это не самая главная особенность MP3 алгоритма. Дело в том, что MP3 использует психоакустическую модель, в частности, эффект маскирования. Грубо говоря, алгоритм отсекает все частоты, которые слушатель не услышит по той причине, что соседняя частота имеет большую интенсивность.
Это опять же тонкий тюнинг FFT. Сложно назвать расчёт некоторого трешхолда для фреймов спектра каким-то отдельным алгоритмом, главным образом потому что это нечто не универсальное, в отличие от FFT или того же поиска пути Дийкстры. JPEG тоже использовал похожий подход, но уже для кодирования цветов, такой же тонкий тюнинг под восприятие глаза.
Как и использование апроксимации при низких битрейтах ДО самого FFT
Алгоритм Риша для нахождения первообразной в символьном виде. И все его расширения.
Алгорим Грунца для нахождения пределов любой сложности.
Первый вообще еще никто полностью не запилил в коде.
На фоне алгоритма QR-алгоритма разложения матриц не упомянули не менее именитое SVD-разложение (которое делается на QR-разложениях).
Я бы вспомнил <a href="https://en.wikipedia.org/wiki/Kalman_filter">фильтр Калмана</a> .
Масса областей применения.
Как минимум, каждый, пользующийся GPS, может радоваться тому, что алгоритм существует:)
SHA256, пожалуй, самый часто используемый алгоритм.
Marching cubes для создания полигональной сетки из произвольно заданного скалярного поля. Позволяет легко создавать 3D модели аналитических функций, в том числе заданных неявно (f(x,y,z) = 0).
Алгоритм Вагнера-Фишера для вычисления редакционного расстояния (расстояние Левенштейна), который часто ошибочно называют алгоритмом Левенштейна. Параллельно был изобретён Нидлманом и Вуншом, но уже применительно к биоинформатике.
Как так вышло, что в статье перемешаны и алгоритмы и язык программирования
Только ЯП Fortran затесался - ему действительно тут не место
В остальном - по большей части одна сплошная математика - да - понятно - что это всё автоматизируется на вычислительных системах - но то о чём идёт речь (более чем 60% "алгоритмов") приводится именно как описание математических методов - причём в виде очень бестолковых описаний, чисто для "тех кто в танке". Спорить не буду - что большинство математических методов ещё до нашей эры по сути можно считать алгоритмами, созданными для вычислительной биосистемы - человеческий мозг - алгоритм вообще понятие уж очень обобщённое, и да - спорить не буду - что приведённые здесь алгоритмы в XX веке по больше части были автоматизированы уже на вычислительных системах. Но всё таки - статья как-то не оправдала ожидания - ожидал увидеть именно алгоритмы в программном коде (хоть на псевдоязыке) именно из мира цифровых систем, а не для решения математических задач (что не спорю - тоже очень важно и применимо в цифровых системах)
Скажем ни одна сортировка не подходит: их есть куча «эффективных»: Хоара, слиянием, пирамидальная и т.д.
То же самое с хешированием. Adler-32, FNV-1, PJW-32, MD4, MD5, SHA-1 — их много.
Вот симплекс метод, матричные вычисления, быстрое преобразование Фурье, коды Рида-Соломона, обход в ширину + в глубину, Диффи-Хеллман — в рамках 20-го века (некоторые из них даже и в рамках 21-го) совершенно безальтернативны.
Ну, не соглашусь в некоторых моментах.
Безальтернативность - не показатель. Например, quicksort: да, ему есть альтернативы. Но сам по себе он гениален, и служит базой для многих. Изучая его и его вариации (introsort) программист понимает несколько вещей: алгоритм может и не иметь гарантированного времени работы, но оставаться хорошим в большинстве случаев; рандом и/или небольшой пред-анализ на каждом шаге может значительно увеличить стабильность времени выполнения; можно обнаружить «плохой случай» и переключиться на алгоритм с гарантией по времени; в вычислительной сложность алгоритма на маленьких объёмах уже нельзя игнорировать константу, и иногда выгоднее переключиться на квадратичный алгоритм с меньшей константой.
Вот сколько всего можно подчерпнуть, изучая историю quicksort.
А приведённые вами алгоритмы тоже не все безальтернативны. Например, код Рида-Соломона лишь один из многих кодов восстановления.
А почему без короткого описания этих алгоритмов? Я понимаю, что статья переводная, но дополнить её кратким описанием работы алгоритма - и ценность стала бы выше в разы. А так - это статья на создание холивара
Ни одного алгоритма на графах - уже смешно.
Для быстрой сортировки единственное применение реальное - это показать принципы динамического программирования. А в реальности это либо кучи хитрые, либо с хеширование, да я радикс видел в реальности чаще, чем быструю сортировку. Кстати хеширование - довольно мощная задача, которая имеет множество нетривиальных алгоритмов.
Обработка сигналов и изображений - там не только БПФ, свертка ничуть не хуже и т.д.
ГАН в ИИ совершили качественный скачок и дали множество новых направлений.
Ну и в будущем алгоритмы на квантовых принципах будут доминировать в перспективе.
Для быстрой сортировки единственное применение реальное — это показать принципы динамического программирования
Можно быструю сортировку рассматривать как динамическое программирование только с большой натяжкой. Это метод "разделяй и властвуй". Который иногда и в ДП применяется, но совсем ему не тождественен.
Хорошо, можете читать это как: "показать принципы 'разделяй и властвуй' программирования" %) Хоть по мне - это что в лоб, что по лбу. У задач есть оптимальные решения по асимптотики, хотя кому я вру, почти все "владельцы продукта" знать не знают, что такое big O. Главное, что бы это было сделано сегодня, а лучше вчера и не важно как. Т.к. завтра либо ты, либо "владелец продукта", либо продукт или сама компания будет уже не с нами ;D
10 лучших алгоритмов 20 века