2

На курсах получил задание: реализовать метод поиска максимума в массиве рекурсивно. Изначально попытался рекурсивно "повторить" итеративный вариант, т.е. передавать в метод индекс и обновленный максимум. Задание проверяется юнит тестами (написанные авторами курса). Описанный мною подход работал на всех тестах, кроме одного: перфоманс тест, который проверяет реализацию на время ([Timeout(5_000)]) на довольно большом массиве (длинной 10_000_000). Переписал метод и теперь код выглядит так:

public static int FindMaximum(int[] array)
{
    if (array is null)
    {
        throw new ArgumentNullException($"source cannot be null.");
    }

    if (array.Length == 0)
    {
        throw new ArgumentException($"source cannot be empty.");
    }

    return FindMax(array, 0, array.Length);
}

private static int FindMax(int[] array, int start, int length)
{
    if (start == length - 1)
    {
        return array[start];
    }

    int mid = (start + length) / 2;
    int left = FindMax(array, start, mid);
    int right = FindMax(array, mid, length);

    return (left > right) ? left : right;
}

Этот вариант проходит все тесты (в том числе и последний "злополучный"). Видимо этот тест как раз и преследовал цель указать обучающемуся (т.е. мне) на проблемы оптимизации и быстродействия. Впереди ряд задач на рекурсию. Может есть какой-нибудь гайдолайн по оптимизации рекурсивного подхода, в какую сторону смотреть? Заранее спасибо. P.S. Это мой первый вопрос и изначально я его сформулировал не верно. Спасибо сообществу, что указали мне на это и прошу прощения.

8
  • 1
    Максимум в одномерном массиве прекрасно ищется за O(N) и без рекурсии, к чему усложнять себе жизнь?
    – A K
    24 дек 2020 в 21:22
  • 1
    Этот вариант проходит все тесты (гораздо быстрее чем другие), но мне, как новичку, хотелось бы знать - почему? Перечислите, какие методы поиска максимума используют те самые "другие".
    – Akina
    25 дек 2020 в 4:37
  • 2
    @Andrew для того, чтобы научить оценивать глубину рекурсии при разных подходах и объяснить tail call оптимизацию.
    – user177221
    25 дек 2020 в 19:05
  • 1
    @AK а по моему - отличный вопрос, отличный тестовый пример, с подвохом, и в теле вопроса есть все, чтобы дать хороший ответ :)
    – user177221
    25 дек 2020 в 19:12
  • 1
    @PashaPash или её еще называют "хвостовая рекурсия".
    – aepot
    25 дек 2020 в 19:19

2 ответа 2

6

Оригинальный вариант у вас падал не по таймауту, а по переполнению стека с StackOverflowException.

И тест проверяет не производительность, а ваше понимание потенициальных проблем при использовании рекурсии.

Каждый рекурсивный вызов занимает место в стеке под локальные переменные и под переданные ему параметры. Так что каждый вызов стоит примерно 12 байт в стеке. При линейном рекурсивном вызове на массиве стек выглядит примерно так

FindMax(array, 10000000, ..)
FindMax(array, 9999999, ..)
.....
FindMax(array, 1, ..)
FindMax(array, 0, ..)
FindMaximum(array)

Размер стека фиксированный, порядка мегабайт, и на 10000000 вызовах он просто переполняется.

Разделение массива на резко уменьшило глубину рекурсии, с 10M до примерно 24.

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

Например:

private static int FindMax(int[] array, int index, int currentMax = 0)
{
    if (index == 0)
    {
        currentMax = array[0];
    }
    
    if (index == array.Length)
    {
        return currentMax;
    }
    else
    {
        currentMax = Math.Max(currentMax, array[index]);
        return FindMax(array, index + 1, currentMax);
    }
}

Вызов в стеке

FindMax(array, 0, ..)
FindMaximum(array)

заменится на вызов

FindMax(array, 1, ..)
FindMaximum(array)

и дальше, вплоть до

FindMax(array, 10000000, ..)
FindMaximum(array)

и результат вернется прямо в FindMaximum.

Отрабатывает за 28ms на 10000000 на моей машине :)

Проблема только в том, что компилятор C# не умеет явно требовать этой оптимизации от JIT (компилятор F#, например, умеет). И она срабатывает только в Release, и только в 64 bit (т.е. нужно или собирать или с явным указанием x64, или в AnyCPU со снятой Prefer 32 bit в свойствах проекта).

Если ваше тестовое окружение запускается под x86 (32 bit) - то оптимизация работать не будет, и тест будет падать. Тогда оставляйте вариант с разделением массива.

Полный код, для простоты проверки:

private static int FindMax(int[] array, int index, int currentMax = 0)
{
    if (index == 0)
    {
        currentMax = array[0];
    }
        
    if (index == array.Length)
    {
        return currentMax;
    }
    else
    {
        currentMax = Math.Max(currentMax, array[index]);
        return FindMax(array, index + 1, currentMax);
    }
}

public static int FindMaximum(int[] array)
{
    if (array is null)
    {
        throw new ArgumentNullException($"source cannot be null.");
    }

    if (array.Length == 0)
    {
        throw new ArgumentException($"source cannot be empty.");
    }

    return FindMax(array, 0);
}


static void Main(string[] args)
{
    int[] array = new int[10000000];
    array[array.Length - 50] = 42;

    var sw = Stopwatch.StartNew();
    Console.WriteLine(FindMaximum(array));
    Console.WriteLine(sw.ElapsedMilliseconds);
}
3
  • порядка мегабайт - пропущено число.
    – aepot
    25 дек 2020 в 19:24
  • @aepot не пропущено, я просто не помню сколько именно там мб стек по умолчанию :)
    – user177221
    25 дек 2020 в 21:34
  • 1 мегабайт для x86 (32 бит)
    – aepot
    25 дек 2020 в 21:36
2

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

  1. классический линейный поиск максимума (FindMaxClassic)
  2. рекурсивный метод, предложенный автором (FindMaximumAuthor)
  3. рекурсивный метод, предлагаемый мной (FindMaxRecursive)

Итак, я написал три метода и поместил их в один класс IntArrayHelper:

public static class IntArrayHelper
{
    public static int FindMaxClassic(int[] array)
    {
        if (array == null)
        {
            throw new ArgumentNullException(nameof(array));
        }

        if (!array.Any())
        {
            throw new ArgumentException("Array is empty");
        }

        var max = array[0];
        for (var i = 1; i < array.Length; i++)
        {
            if (array[i] > max)
            {
                max = array[i];
            }
        }

        return max;
    }

    public static int FindMaxRecursive(int[] array)
    {
        if (array == null)
        {
            throw new ArgumentNullException(nameof(array));
        }

        if (!array.Any())
        {
            throw new ArgumentException("Array is empty");
        }

        var max = FindMaxRec(array, 0);
        return max;
    }

    private static int FindMaxRec(int[] array, int from)
    {
        // Дошли до крайнего правого элемента массива? заканчиваем рекурсию
        if (from == array.Length - 1)
        {
            return array[from];
        }

        var current = array[from];
        var max = FindMaxRec(array, from + 1);
        return max > current ? max : current;
    }

    public static int FindMaximumAuthor(int[] array)
    {
        if (array is null)
        {
            throw new ArgumentNullException($"source cannot be null.");
        }

        if (array.Length == 0)
        {
            throw new ArgumentException($"source cannot be empty.");
        }

        return FindMax(array, 0, array.Length);
    }

    private static int FindMax(int[] array, int start, int length)
    {
        if (start == length - 1)
        {
            return array[start];
        }

        int mid = (start + length) / 2;
        int left = FindMax(array, start, mid);
        int right = FindMax(array, mid, length);

        return (left > right) ? left : right;
    }
}

И сделал тест на 10000 запусков каждого метода на одинаковом наборе случайно сгенерированного списка массивов. Тестирующий код:

private static void Main(string[] args)
{
    WarmUp();

    var random = new Random();
    var testSrc = new List<int[]>();
    const int n = 10000;
    for (var i = 0; i < n; i++)
    {
        var arrayLength = random.Next(1, n);
        var array = new int[arrayLength];
        for (var j = 0; j < arrayLength; j++)
        {
            array[j] = random.Next(-n, n);
        }

        testSrc.Add(array);
    }

    var timeClassic = TestTimeExecution(IntArrayHelper.FindMaxClassic, testSrc);
    var timeRecursive = TestTimeExecution(IntArrayHelper.FindMaxRecursive, testSrc);
    var timeAuthor = TestTimeExecution(IntArrayHelper.FindMaximumAuthor, testSrc);

    Console.WriteLine($"Classic         : {timeClassic.TotalMilliseconds}");
    Console.WriteLine($"Recursive       : {timeRecursive.TotalMilliseconds}");
    Console.WriteLine($"Author recursive: {timeAuthor.TotalMilliseconds}");
}

private static void WarmUp()
{
    var warmUpTime = TimeSpan.FromSeconds(4);

    var watch = new Stopwatch();
    watch.Start();

    while (watch.Elapsed < warmUpTime)
    {
        var x = Math.Pow(12, 5) * Math.Cos(55.2);
        x /= 20;
    }
}

private static TimeSpan TestTimeExecution(Func<int[], int> method, List<int[]> testSrc)
{
    var watch = new Stopwatch();
    watch.Start();

    foreach (var input in testSrc)
    {
        method(input);
    }

    watch.Stop();
    return watch.Elapsed;
}

Результаты:

Classic : 112,5684

Recursive : 769,2986

Author recursive: 1475,7236

Выводы: Классический метод >10 раз быстрее предложенного вами рекурсивного метода поиска максимума и ~6-7 раз быстрее предложенного мною рекурсивного метода.

P.S. В измерении скорости выполнения методов не силен. Результаты имеют приближенный характер

1
  • Здравствуйте. Спасибо за ответ. Проверил ваш вариант рекурсии - не подошло. Проверяется массив длинной в 10млн. Мой дешманский ноут долго пыхтит, а потом пишет, что Test run aborted.
    – Д Ш
    25 дек 2020 в 18:17

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.