Как оценить стоимость алгоритма моделирования

Мне нужно проверить симуляцию цепи Маркова Монте-Карло. Размер системы n. Теперь я хочу знать, какова взаимосвязь между n и стоимостью. Другими словами, я хочу знать мощность / порядок n в стоимости, например, это n^2.5 или n^2.8?

Поскольку здесь задействовано множество факторов и шагов, я предпочитаю не анализировать сначала сложность. Я бы очень хотел запустить моделирование, чтобы получить машинное время. Итак, мой вопрос: как получить отношение затрат n^x, где x неизвестно, на основе машинного времени?

Например, когда n = 1000, для выполнения всей развертки требуется t_1, что составляет 1000 шагов Монте-Карло. Когда n = 666, для выполнения всей развертки требуется t_2, что на этот раз составляет 666 шагов Монте-Карло. Я мог бы получить t_1, t_2, t_3 для другого размера n, тогда как мне проверить порядок стоимости?

Кстати, имеет ли значение использование другого компьютера для получения машинного времени? Извините за мое незнание.


matlab montecarlo simulation time-complexity complexity-theory
person Appalachian Math    schedule 27.02.2014    source источник
comment
Используйте tic, toc, чтобы получить время для разных n (я думаю, вам придется усреднить, если есть распределение для данного времени), а затем используйте журнал, чтобы получить показатель степени (при условии, что он имеет экспоненциальную форму) и лучше всего подходят для различных значений n.   -  person Lazarus    schedule 27.02.2014
comment
@Lazarus Большое спасибо. Не могли бы вы ответить отдельно, чтобы я мог выбрать вариант ответа?   -  person Appalachian Math    schedule 27.02.2014
comment
@Lazarus Усредняя это, вы имели в виду, что мне нужно запустить k * n раз для системы из n и взять среднее время по k?   -  person Appalachian Math    schedule 27.02.2014
comment
да. Вы управляете Монте-Карло, поэтому я предполагаю, что будет некоторая разница. Если дисперсия действительно мала, просто игнорируйте среднюю часть.   -  person Lazarus    schedule 27.02.2014

Ответы (2)


arrow_upward
2
arrow_downward

Используйте tic, toc, чтобы получить время для разных n. Если у вас есть распределение времени для данного n, то получите среднее значение.

Тогда, если вы знаете, что он имеет экспоненциальную форму, вы можете получить

order = log(avgtime);

С разными значениями порядка для каждого из значений n вы получите наиболее подходящий вариант (возможно, polyfit).

person Lazarus    schedule 27.02.2014
comment
имеет значение, использую ли я другой компьютер для получения машинного времени? Извините за мое незнание. Я полагаю, что машинное время не должно иметь ничего общего с конкретным компьютером, верно? - person Appalachian Math; 27.02.2014
comment
Время будет зависеть от компьютера. Сложности не должно. Технически вы получите A * n ^ p, где p - сложность, а A - некоторая машинно-зависимая константа. - person Lazarus; 27.02.2014

arrow_upward
1
arrow_downward

В этой статье MathWorks есть некоторые общие рекомендации, в том числе timeit, _2 _ / _ 3_ и cputime.

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

X = [1 2; 3 4; 5 6; 7 8];
f = @() svd(X);
t = timeit(f, 3)

Причина, по которой он настолько удобен и точен по сравнению с _7 _ / _ 8_, в том, что:

timeit вызывает указанную функцию несколько раз и вычисляет медиану измерений.

Функция cputime интересна тем, что дает более высокие числа по сравнению с tic / toc и timeit на многопоточных машинах. Если вас интересует вычислительная нагрузка, возможно, это более подходящая метрика. Функция cputime против _14 _ / _ 15_ и timeit < / а>.

Раньше была команда flops для возврата количества операций с плавающей запятой, но это была удалено много лет назад. Если вы действительно хотите подсчитать количество флопов, используйте набор инструментов Lightspeed Есть функции для этого.

person chappjc    schedule 27.02.2014
comment
Большое спасибо за информативный ответ. Я изучаю то, что вы упомянули. - person Appalachian Math; 28.02.2014