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

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

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

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

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

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

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

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

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

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

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

• Попадания в кэш - Ориентированный на данные дизайн
• Попадания в кэш - Сокращение ненужных ветвлений / переходов.
• Предсказание кэша -- Сокращение циклов, чтобы чтобы они помещались в кэш процессора.

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

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

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