Можно ли предсказать, сколько времени займет выполнение программы?

Question

Мне было интересно, возможно ли это сделать с произвольной программой?Я слышал, что с некоторой математикой вы можете оценить, как долго будет работать простой алгоритм, такой как алгоритм сортировки;но как насчет более сложных программ?

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

Итак, действительно ли существует такая программа?Если нет, то как я могу правильно оценить время выполнения моих программ?

Answer 1

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

Answer 2

Вы на самом деле задаете несколько связанных вопросов одновременно, а не один единственный вопрос.

Существует ли Программа A, которая, когда ей в качестве входных данных дана произвольная Программа B, дает оценку того, сколько времени потребуется для запуска Программы B? Абсолютно нет. Вы даже не можете разработать Программу А, которая сообщит вам, остановится ли произвольная Программа Б.

Эта вторая версия - будет ли Программа B когда-либо останавливаться - достаточно хитро называется проблемой остановки, и было доказано, что она просто не разрешима. В Википедии есть хорошая веб-страница, и книга Геделя, Эшера, Баха представляет собой очень длинное, но очень разговорное и читабельное изложение идей, связанных с теоремой Гёделя о неполноте, которая очень тесно связана.

http://en.wikipedia.org/wiki/Halting_problem

http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach

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

Как только они докажут, что какая-то программа остановится, один из основных математических инструментов называется нотацией Big O. На очень интуитивном уровне нотация Big O помогает разрабатывать законы масштабирования того, как время выполнения программы зависит от размера ввода. В очень тривиальном примере предположим, что ваша программа представляет собой цикл, и цикл занимает одну произвольную единицу времени. Если вы запустите цикл N раз, это займет N единиц времени. Но если этот цикл сам находится в другом цикле, который выполняется N раз, все это занимает N * N единиц времени. Эти две программы масштабируются очень по-разному. (Это тривиальный пример, но реальные примеры могут быть довольно сложными.)

http://en.wikipedia.org/wiki/Big_oh

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

Answer 3

Вы должны исследовать обозначение Big O.Хотя он не дает фиксированного числа, он говорит вам, как его производительность будет меняться для разных размеров.Есть несколько простых правил (если ваш код находится в цикле из n итераций, тогда запуск цикла займет n * времени).

Проблема в следующем:

В сложных программахНа него влияют несколько переменных.

Не учитывает взаимодействие с пользователем.

То же самое для задержки в сети и т. д.

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

Answer 4

Вы не можете на самом деле.

Для простого алгоритма вы знаете, является ли что-то O (n) или O (n ^ 2).Что вы можете угадать.

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

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

Если вы произвели радикальные изменения, найти ETA станет труднее: -]