Быстродействие для рекурсии и итерации. Почему они работают с одинаковой скоростью для разных «маленьких» чисел?

Question

Я пытаюсь оптимизировать код, который у меня есть.Чтобы сделать это, я написал этот код, чтобы увидеть эффект рекурсии и итерации.Код «рассчитывает» до 10-й степени.

public Form1()
{
    InitializeComponent();
    Stopwatch sw = new Stopwatch();
    sw.Start();
    recurse(4);
    //iterate(4);
    sw.Stop();
    Text = sw.Elapsed.TotalMilliseconds.ToString();
}

void recurse(int i)
{
    if (i < 1) return;
    for (int x = 0; x < 10; x++) recurse(i - 1);
}

void iterate(int i)
{
    i = (int)System.Math.Pow(10, i);
    for (int x = 0; x < i; x++) ;
}

Я получаю этот неожиданный результат: когда n от 1 до 4, скорость составляет около 0,5 мс для рекурсии и итерации.Вместо 4 я в 1000 раз медленнее, чем 1, что я и ожидал.Только для больших чисел он начинает иметь более интуитивную скорость, итерация также быстрее, чем рекурсия.

Почему такая же скорость в 10 раз, как в 10000 раз?

Answer 1

Даже если вы исправите код, чтобы вычислить одну и ту же вещь в обоих случаях, не проверяйте подобные вещи за один прогон. Вы не получите должного результата, если сам тест не займет хотя бы секунду. Запустите его миллион раз, а затем разделите общее время. Когда вы тестируете что-то, что займет всего одну или две миллисекунды, вы должны убедиться, что тест занимает достаточно много времени, чтобы игнорировать разницу между холодным кэшем, временем вызовов .Start () и .Stop (), небольшой задержкой GC в время и т. д. Также убедитесь, что фактическая работа занимает больше времени, чем пустой цикл подсчета (то есть for(many times) recurse(x) имеет достаточно высокий x, что само по себе for не имеет значения)

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

TL; DR - накладные расходы на другие вещи, происходящие вокруг вашей функции, превышают время, затрачиваемое на выполнение вашей функции.

Answer 2

Я думаю, что проблема в вашей реализации рекурса.Если я не читаю это неправильно, recurse выполняется только 4 раза и повторяет от 1 до 10 в каждом.В то время как итерация вычисляет 10 ^ 4 - 10000, а затем считает от 0 до 10000.

Таким образом, вы не проводите честное сравнение.

Редакция: Если вы действительно получаете ответы в диапазоне 0,5 мс, то, возможно, вы превысили точность задействованных функций.В этой статье MS http://msdn.microsoft.com/en-us/library/system.diagnostics.stopwatch.aspx есть пример с наносекундной синхронизацией, который может оказаться вам полезным.Это немного больше работы, но может дать понимание.