Решение для Delta Generators не укладывается в лимит времени

Question

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

Условие

Delta Generators

In mathematics, the symbols Δ and d are often used to denote the difference between two values. Similarly, differentiation takes the ratio of changes (ie. dy/dx) for a linear relationship. This method can be applied multiple times to create multiple 'levels' of rates of change. (A common example is x (position) -> v (velocity) -> a (acceleration)).

Today we will be creating a similar concept. Our function delta will take a sequence of values and a positive integer level, and return a sequence with the 'differences' of the original values. (Differences here means strictly b - a, eg. [1, 3, 2] => [2, -1]) The argument level is the 'level' of difference, for example acceleration is the 2nd 'level' of difference from position. The specific encoding of input and output lists is specified below.

The example below shows three different 'levels' of the same input.

int[] input = new [] {1, 2, 4, 7, 11, 16, 22};
Delta(input, 1);  // new [] {1, 2, 3, 4, 5, 6}
Delta(input, 2);  // new [] {1, 1, 1, 1, 1}
Delta(input, 3);  // new [] {0, 0, 0, 0}

We do not assume any 'starting value' for the input, so the output for each subsequent level will be one item shorter than the previous (as shown above). If an infinite input is provided, then the output must also be infinite. Input/Output encoding

Input and output lists can be any, possibly infinite, IEnumerable. Possibilities include finite lists and possibly infinite generator objects, but any Enumerable must be accepted as input and is acceptable as output. Difference implementation

Delta must work for lists of any int instance.

Additional Requirements/Notes:

delta must work for inputs which are infinite
values will always be valid, and will always produce consistent classes/types of object
level will always be valid, and 1 <= level <= 400

Additional examples:

IEnumerable<int> Up() {
  int a=0, b=1; while (true) { yield return a; (a, b) = (a + b, b + 3); } 
}
Delta(Up(), 1).Take(10);  // new[] {1,4,7,10,13,16,19,22,25,28}

Вот мой код:

public static IEnumerable<int> Delta(IEnumerable<int> enumerable, int n) 
 {
     List<int> res = enumerable.ToList();
     List<int> temp = new List<int>();
     for (int i = 0; i < n; i++)
     {
         for (int j = 0; j < res.Count - 1; j++)
         {
             temp.Add(res[j + 1] - res[j]);
         }
             res = temp.ToList();
             temp.Clear();
     }
     return res;
 }

Прошу помочь в оптимизации.

Answer 1

Очевидно, легко подойдет рекурсивный алгоритм. Избавиться от рекурсии наверное можно, но я оставлю это вам. Так как n <= 400, для стека это детские шалости, и рекурсия должна быть довольно эффективным решением.
Вам следует познакомиться с ключевыми словами yield return и yield break паттерна "Итератор", ну и соответственно с интерфейсом IEnumerator.
Здесь не требуется создавать каких-либо списков или массивов.

public static IEnumerable<int> Delta(IEnumerable<int> enumerable, int n)
{
    IEnumerable<int> data = n > 1 ? Delta(enumerable, n - 1) : enumerable;
    using var enumerator = data.GetEnumerator();
    if (enumerator.MoveNext())
    {
        int prev = enumerator.Current;
        while (enumerator.MoveNext())
        {
            int num = enumerator.Current;
            yield return num - prev;
            prev = num;
        }
    }
}

Вот еще одно, возможно менее эффективное, но более понятное решение

public static IEnumerable<int> Delta(IEnumerable<int> enumerable, int n)
{
    IEnumerable<int> data = n > 1 ? Delta(enumerable, n - 1) : enumerable;
    int prev = 0;
    bool isFirst = true;
    foreach (int num in data)
    {
        if (isFirst)
        {
            prev = num;
            isFirst = false;
            continue;
        }

        yield return num - prev;
        prev = num;
    }
}

БЛОГ НА HUSL

Решение для Delta Generators не укладывается в лимит времени

Ответы (1 шт):