Алгоритмы для современного оборудования?

Question

Еще раз, я нахожу себя с набором нарушенных предположений .Сама статья о 10-кратном увеличении производительности за счет изменения проверенного оптимального алгоритма для учета виртуальной памяти:

На современном многозадачном процессоре, работающем на тактовой частоте несколько гигагерц, в худшем случаепотеря составляет почти 10 миллионов инструкций на страницу ошибки VM.Если вы работаете с вращающимся диском, число больше похоже на 100 миллионов инструкций.

Что хорошего в алгоритме O (log2 (n)), если эти операции вызывают сбои страниц и медленные операции с диском?Для большинства релевантных наборов данных алгоритм O (n) или даже O (n ^ 2), который позволяет избежать сбоев страниц, будет обходить его.

Есть ли еще такие алгоритмы?Должны ли мы пересмотреть все эти фундаментальные строительные блоки нашего образования?На что еще нужно обращать внимание при написании своего собственного?

Пояснение:

Данный алгоритм не быстрее, чем проверенный оптимальный алгоритм, потому чтоНотация Big-O ошибочна или бессмысленна.Это быстрее, потому что проверенный оптимальный алгоритм опирается на предположение, которое не соответствует действительности в современных аппаратных средствах / ОС , а именно, что весь доступ к памяти равен и взаимозаменяем.

Answer 1

Вам нужно пересматривать свои алгоритмы только тогда, когда ваши клиенты жалуются на медлительность вашей программы или если она не соответствует критическим срокам. В противном случае сфокусируйтесь на правильности, надежности, удобочитаемости и простоте обслуживания. Пока эти элементы не достигнуты, любая оптимизация производительности является пустой тратой времени на разработку.

Ошибки страницы и операции на диске могут зависеть от платформы. Всегда профиль ваш код, чтобы увидеть, где узкие места. Проведение времени в этих областях принесет наибольшую пользу.

Если вам интересно, наряду с ошибками страниц и медленными операциями на диске, вы можете знать:

• Хиты кэша - ориентированный на данные дизайн
• Кэш попаданий - уменьшение ненужного ветви / прыжки.
• Кэширование прогноза - сжимаем циклы так они помещаются в кэш процессора.

Опять же, эти пункты только после того, как качество было достигнуто, жалобы клиентов и профилировщик проанализировали вашу программу.

Answer 2

Я более подробно остановлюсь на ответе Грегса: разница между эффективной сложностью и асимптотической сложностью.Асимптотическая сложность игнорирует постоянные факторы и действительна только для «достаточно больших» входных данных.Часто «достаточно большой» на самом деле может означать «больше, чем любой компьютер может иметь дело, сейчас и на несколько десятилетий»;это где теория (оправданно) получает плохую репутацию.Конечно, есть также случаи, когда «достаточно большой» означает n = 3!

Более сложный (и, следовательно, более точный) способ взглянуть на это - сначала спросить «что такоеРазмерный диапазон проблем, которые вас интересуют? »Затем вам нужно измерить эффективность различных алгоритмов в этом диапазоне размеров, чтобы почувствовать« скрытые константы ».Или вы можете использовать более точные методы алгоритмической асимптотики, которые фактически дают вам оценки констант.

Другая вещь, на которую стоит обратить внимание, это «точки перехода».Конечно, алгоритм, который выполняется за 2 n ² времени, будет быстрее, чем алгоритм, который выполняется за 10 ¹⁶ n log ( n ) раз для всех n <1,99 * 10 <sup>17 .Таким образом, будет выбран квадратичный алгоритм (если вы не имеете дело с размерами данных, которые беспокоит CERN).Даже субэкспоненциальные термины могут кусаться - 3 n ³ намного лучше, чем n ³ + 10 ¹⁶ n ² для n <5 * 10 <sup>15 (при условии, что это фактические сложности).

Answer 3

Одна важная вещь состоит в том, чтобы понять, что наиболее распространенное использование нотации big-O (чтобы говорить о сложности времени выполнения) - это только половина истории - есть другая половина, а именно пробел сложность (которая также может быть выражена с помощью big-O), которая также может быть весьма актуальной.

Как правило, в наши дни увеличение емкости памяти опережает увеличение скорости вычислений (для одного ядра - распараллеливание может обойти это), поэтому меньше внимания уделяется сложности пространства, но это все же следует учитывать, особенно на машинах с более ограниченной памятью или при работе с очень большими объемами данных.

Answer 4

O (n) - только часть истории - большая часть, и часто доминирующая часть, но не всегда доминирующая часть.Как только вы перейдете к оптимизации производительности (, которую не следует делать слишком рано в вашей разработке ), вам необходимо рассмотреть все ресурсы, которые вы используете.Вы можете обобщить Закон Амдала , чтобы обозначить, что время выполнения будет зависеть от самого ограниченного ресурса.Обратите внимание, что это также означает, что конкретное оборудование, на котором вы выполняете, также должно учитываться.Программа, которая высоко оптимизирована и чрезвычайно эффективна для массивно параллельного компьютера (например, CM или MassPar), вероятно, не будет хорошо работать с большим векторным блоком (например, Cray-2) или высокоскоростным микропроцессором.Эта программа может даже не работать на огромном массиве способных микропроцессоров (стиль отображения / уменьшения).Разные оптимизации для разных балансов кеша, связи с процессором, ввода-вывода, скорости процессора, доступа к памяти и т. Д. Означают разную производительность.

Когда я работал над оптимизацией производительности, мы стремились к этому »сбалансированная "производительность по всей системе.Супербыстрый процессор с медленной системой ввода / вывода редко имел смысл, и так далее.O () обычно учитывает только сложность процессора.Возможно, вам удастся обменять пространство памяти (развертывание циклов не имеет смысла в O (), но часто помогает реальной производительности);забота о попаданиях в кэш, т. е. линейные макеты памяти, ошибки в банках памяти; виртуальная против реальной памяти;лента против вращающегося диска против RAID и так далее.Если в вашей производительности преобладает нагрузка на процессор, а также ввод-вывод и расшатывание памяти, основной проблемой является big-O.Если ваш процессор на 5%, а сеть на 100%, возможно, вы можете уйти от big-O и работать над вводом-выводом, кэшированием и т. Д.

Многопоточность, особенно с многоядерными процессорами., делает весь этот анализ еще более сложным.Это приводит к очень обширному обсуждению.Если вы заинтересованы, Google может предоставить вам месяцы или годы ссылок.

Answer 5

Я не вижу нарушенных предположений.Нотация Big-O - это мера алгоритмической сложности на очень, очень упрощенной идеализированной вычислительной машине и игнорирование постоянных членов.Очевидно, это не последнее слово о реальных скоростях на реальных машинах.