Как измерить сложность на практике в вашем большом программном проекте?

11

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

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

Есть ли способ сделать это? Или люди на практике просто полагаются на «локальное» использование быстрого алгоритма, чтобы сделать все приложение быстрее, вместо того, чтобы рассматривать приложение в целом как глобальное?

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

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

user7088941
источник
1) Это требует подхода тестирования, чтобы найти точки для улучшения. Тестирование производительности, тестирование на долговечность, динамическое тестирование (путем мониторинга показателей памяти / ЦП каждого компонента). 2) После нахождения точек для улучшения вы найдете основную причину для этих точек. 3) Найти решение для устранения первопричины, поддерживая правильность.
сверхобмена
вам нужны некоторые инструменты для этих тестов, упомянутых в пункте 1
overexchange
1
Анализ Big O не говорит вам, как будет работать алгоритм. Он говорит вам, как производительность будет масштабироваться , а также nувеличивается.
Джон Ву

Ответы:

5

Большие программные проекты состоят из множества различных компонентов, и не все они, как правило, являются узким местом. Скорее наоборот: для почти любой программы, которую я видел в моей жизни, где низкая производительность была проблемой, применялся принцип Парето : более 80% прироста производительности можно достичь путем оптимизации менее 20% кода (на самом деле, я думаю, что цифры часто были более 95% до 5%).

Поэтому лучше всего начинать с рассмотрения отдельных частей. Вот почему профилирование (как объяснено в ответе Дэвида Арно ) хорошо, так как оно помогает вам идентифицировать упомянутые 5% кода, где оптимизация даст вам «самый большой выигрыш за доллар». Оптимизация «всего приложения» несет определенный риск чрезмерного повышения производительности, и если вы оптимизируете эти 95% даже в 10 раз, это часто не даст ощутимого эффекта. Также обратите внимание, что профилирование говорит вам намного больше, чем любая гипотетическая оценка сложности алгоритма, поскольку простой алгоритм, который требует O (N ^ 3) шагов, может все же быть быстрее, чем сложный алгоритм, который требует O (N log (N)), пока N достаточно маленький.

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

Типичные методы оптимизации включают

  • улучшение использования алгоритмов и структур данных

  • подстройка бывшего

  • микрооптимизации в некоторых реальных горячих точках

  • перекодирование критических секций с использованием ассемблера или CUDA

Обратите внимание, что эти методы работают на разных уровнях абстракции, некоторые из них рассматривают компонент более «в целом», чем другие. Так что это зависит от того, что вы подразумеваете под «все, что мы делаем, это смотрим на отдельные части» - если вы имели в виду только микрооптимизацию, я не согласен с тем, что «мы» работаем только над этим. Но если вы имеете в виду применение этих полномасштабных оптимизаций к изолированным частям или компонентам, тогда «мы», вероятно, работаем над правильными частями, и вам следует поставить под сомнение ваши ожидания.

Док Браун
источник
13

Стандартный, проверенный и проверенный способ - профилировать код . Вы выполняете динамический анализ работающей системы для измерения времени, использования памяти и т. Д. Затем анализируете результаты, чтобы найти узкие места в производительности.

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

Дэвид Арно
источник
1
Это решает проблему производительности, поэтому мы делаем это, но не отвечаем на первоначальный вопрос. Я думаю, что в худшем случае временную или пространственную сложность лучше всего определить с помощью инструмента статического анализа программ, который может отсутствовать. Тесты производительности хороши для конкретных сценариев, но они не говорят вам много о худших возможных ситуациях.
Фрэнк Хилман
3
@FrankHileman Я думаю, суть в том, что производительность - это практическая проблема, и ее можно измерить только на практике. Вы не используете математику, чтобы найти узкое место в вашем программном обеспечении, даже если вы можете решить ее, найдя ее с помощью математики (алгоритмов).
Wildcard
Относительно примечания, в старом временном представлении слайд-шоу (стеклянные слайды) существовала целая выдуманная технология, состоящая в том, чтобы кропотливо вычислять математически среднюю плотность предметного стекла для определения яркости света для использования. Абсолютно бесполезно: если картинка не выглядит хорошо, вы получаете более яркий свет!
Wildcard
@Wildcard Хотя производительность можно измерить только во время выполнения, ее можно прогнозировать статически. Плохой выбор структуры данных может выглядеть хорошо, с точки зрения производительности, в тестах производительности, но с треском проваливается в крайних случаях, которые могут быть предсказаны при статическом анализе. По этой же причине мы смотрим на анализ сложности наихудшего случая для структур данных в целом.
Фрэнк Хилман
@Wildcard: вы правы, однако Фрэнк также очень прав, что этот пост не отвечает на вопрос.
Док Браун
3

Хотя другие ответы верны и дают некоторое руководство, я думаю, что они пропускают шаг. В сложной системе, с которой вы работаете сейчас, понимание различных компонентов, составляющих систему, является ключом к пониманию того, почему что-то идет медленно.

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

Также выясните, как компоненты взаимодействуют друг с другом. Это может иметь все значение.

Например, я видел код на C #, где интерфейс между двумя компонентами передавал IEnumerable, созданный первым компонентом, который затем перечислялся вторым компонентом. В C # это требует переключения контекста, что может быть дорогостоящим при определенных обстоятельствах. Решение этого не влияет на алгоритм. Простой .ToList () гарантирует, что результат будет собран, прежде чем следующий шаг решит эту проблему.

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

Джонатан ван де Вин
источник