Какие алгоритмы используются чаще всего?
Пожалуйста, напишите один алгоритм для каждого ответа, постарайтесь, чтобы ваш ответ был коротким (одна или две строки).
ds.algorithms
big-list
Kaveh
источник
источник
Ответы:
Является ли быстрое преобразование Фурье алгоритмической задачей, решаемой большинством раз в день с помощью реальных компьютерных систем? Это должно быть близко. Поэтому я бы назначил алгоритм БПФ Кули-Тьюки .
источник
Умножение.
Возможно, один из старейших не совсем тривиальных алгоритмов, и проблема, которая решается чаще, чем FFT.
источник
Алгоритмы кратчайшего пути Дейкстры и Беллмана-Форда . По состоянию на 2010 год в Интернете было активно не менее 35 000 автономных систем (AS). Каждая AS работает либо по протоколу маршрутизации на уровне канала (Dijkstra), либо по протоколу маршрутизации с вектором расстояния (Bellman-Ford). Маршрутизаторы в одной AS обычно обновляют свои таблицы каждые несколько минут, скажем, 10.
Таким образом, число казней Dijkstra & Bellman-Ford в день составляет не менее 5 миллионов. И это только от роутеров.
Мы не посчитали вычисления кратчайшего пути из Google Maps и лайков, которые должны легко составлять в 10 раз больше. Полмиллиарда казней в день - не надумано.
источник
Quicksort
источник
Бинарный поиск
источник
Я думаю, что наиболее используемый алгоритм - это проверка четности (или, может быть, CRC или какой-то код с исправлением ошибок), потому что они появляются при каждом доступе к ОЗУ.
источник
Симплексный алгоритм - не конкурирует ли он с лучшими методами внутренней точки? Если так, то это должно быть использовано много.
источник
В более общем плане, вы должны взглянуть на лауреатов премии Канеллакиса за идеи, которые имеют теоретическую и практическую значимость.
источник
Сопоставление регулярных выражений путем преобразования в конечные автоматы - я полагаю, что grep работает в этом направлении.
источник
Поиск в глубину (DFS)
источник
Трудно придумать более широко используемые алгоритмы, чем в современных реализациях TCP : то есть предотвращение перегрузок , быстрая повторная передача . Хотя это зависит от того, как определить, что соответствует критериям для алгоритма ...
источник
Устранение Гаусса Это все еще используется на практике, верно? Если не заменить то, что чаще всего используется для решения линейных систем ...
источник
SHA-1 (и хеш-функции в целом). Вероятно, побеждает большинство других алгоритмов с точки зрения количества выполнений.
источник
Алгоритмы, связанные с деревом B +, используются для баз данных
источник
Алгоритмы планирования. Они используются каждым пользовательским устройством и сервером по всему миру. Используется множество вариантов, я нашел много ссылок на «многоуровневую очередь обратной связи»
источник
Этот ответ интерпретирует «наиболее часто» в терминах фактических циклов ЦП.
Когда я изучал вычисления в 70-х, я вспомнил, что читал, что подавляющее большинство компьютерных циклов (читай: мэйнфреймы) были посвящены сортировке. Бизнес-приложения требуют обширной сортировки для анализа и отчетности. Я не думаю, что это сильно изменилось, но, конечно, рост других приложений - электронная почта, обработка текстов и т. Д. - должен был изменить смесь. Эти сортировки обычно являются стабильными (не быстрой сортировкой) из-за необходимости сортировки последовательностей полей для создания подсортов.
Строго говоря, однако, наиболее часто используемый алгоритм - это, без сомнения, все, что выполняется системным процессом ожидания Windows, когда больше ничего не происходит ;-).
источник
Матрица векторов Sprase умножается
... является вычислительной рабочей лошадкой для решения почти всех линейных систем. В результате он запускается всякий раз, когда
Большая часть FLOP на любом суперкомпьютере или кластере проводится внутри разреженного mat-vec.
источник
Метод Ньютона. Он используется для вычисления квадратных корней, для вычислительного деления. Это может быть использовано для линейного программирования. В более общем смысле это рабочая лошадка (выпуклой) оптимизации. Он может быть использован для решения дифференциальных уравнений в физике путем минимизации действия / энергии.
источник
Хеширование и красно-черные деревья.
Они уже реализованы в STL (hash_map, map), и каждый программист знает, что такой контейнер невероятно удобен, когда вы хотите сохранить некоторую информацию, проиндексированную произвольным типом данных.
источник
Алгоритмы исправления ошибок, такие как Рид-Соломон.
http://en.wikipedia.org/wiki/Error-correcting_code#List_of_error-correcting_codes http://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction
источник
Динамическое программирование .
Я думаю, что DP используется «чаще», чем другие алгоритмы, приведенные в обзоре. Я делаю вывод «чаще» в том смысле, как часто в реальной жизни программист реализовывал концепцию нетривиального алгоритма , а не сколько раз вызывалась конкретная реализация алгоритма.
DP универсален и многолик. Иногда я использовал это несколько подсознательно, а потом понял, что я делаю DP.
Конечно, есть вещи, которые даже более распространены, чем Dynamic Program, но в основном это структура данных (массив, связанный список, хэш).
источник
String Matching, все время используется в прикладном программном обеспечении и на уровне базы данных.
В точном случае, есть несколько довольно сложных алгоритмов (KMP, Boyer-Moore), некоторые из которых достигают сублинейного ожидаемого времени выполнения. Их также интересно изучать с точки зрения CS.
Приближенное сопоставление строк, то есть выравнивания, возможно, еще более интересно. Вы знаете особенности "автозамены"? Кроме того, поиск в зашумленных строковых данных (например, ДНК) выполняется с использованием выравниваний.
источник