arrayMaxConsecutiveSum c#

作为学习C#的一部分,我从事代码信号挑战。到目前为止,一切都对我有利,除了标题中所述的测试。

问题是,当数组的长度为10 ^ 5且连续元素(k)的数量为1000时,我的代码不足以在3秒内运行。我的代码运行如下:

int arrayMaxConsecutiveSum(int[] inputArray,int k) {

    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        sum = inputArray.Skip(i).Take(k).Sum();

        if (sum > max)
            max = sum;
    }

    return max;
}

网站上的所有可见测试都可以正常运行,但是当涉及到隐藏测试时,在测试20中会出现错误,指出

  

19/20测试通过。测试20超出了执行时间限制:程序超出了执行时间限制。确保可以在几秒钟内完成任何可能输入的执行。

我也尝试了解锁解决方案,但是在C#上,代码与此相似,但是他没有使用LINQ。我还尝试将其与隐藏的测试一起运行,但是发生了相同的错误,这很奇怪,因为它甚至没有通过所有测试时就作为解决方案提交了。

有没有更快的方法来获取数组的和?

我还考虑过解锁隐藏的测试,但是我认为它不会给我任何具体的解决方案,因为问题仍然存在。

xdherosgl 回答:arrayMaxConsecutiveSum c#

似乎您正在为每个循环添加k个数字。此伪代码应该更有效:

  1. 取前k个元素的总和,并将其设置为最大值。

  2. 像以前一样循环,但是每次从现有的总和中减去i-1处的元素,然后将i + k处的元素相加。

  3. 像以前一样检查最大值并重复。


此处的区别在于每个循环中的加法数。在原始代码中,您为每个循环添加k个元素,在此代码中,在每个循环中,您减去一个元素并将一个元素添加到现有的总和中,因此这是2个操作与k个操作的比较。随着k对于大型数组变大,您的代码开始变慢。

,

对于这种特定情况,我建议您不要使用Skip方法,因为它每次都会对集合进行迭代。您可以在here处检查Skip的实现。复制代码以供参考。

    public static IEnumerable<TSource> Skip<TSource>(this IEnumerable<TSource> source,int count) {
        if (source == null) throw Error.ArgumentNull("source");
        return SkipIterator<TSource>(source,count);
    }

    static IEnumerable<TSource> SkipIterator<TSource>(IEnumerable<TSource> source,int count) {
        using (IEnumerator<TSource> e = source.GetEnumerator()) {
            while (count > 0 && e.MoveNext()) count--;
            if (count <= 0) {
                while (e.MoveNext()) yield return e.Current;
            }
        }
    }

您可以看到Skip每次都会对集合进行迭代,因此,如果您有一个庞大的集合,其中k是一个很高的数字,那么执行时间就会变慢。

代替使用Skip,您可以编写简单的for循环来迭代所需的项目:

public static int arrayMaxConsecutiveSum(int[] inputArray,int k) 
{

    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        sum = 0;
        for (int j = i; j < k + i; j++)
        {
            sum += inputArray[j];
        }

        if (sum > max)
            max = sum;
    }
    return max;
}

您可以检查此dotnet小提琴-https://dotnetfiddle.net/RrUmZX,在此处可以比较时差。对于基准测试,我建议您研究Benchmark.Net

,

使用LINQ并考虑性能时需要小心。并不是说它很慢,而是可以很容易地在一个单词后面隐藏一个大的操作。在这一行:

sum = inputArray.Skip(i).Take(k).Sum();

Skip(i)Take(k)都将花费大约for循环的时间,逐步遍历数千行,并且该行针对主循环。

没有比这更快的魔术命令,相反,您必须重新考虑您的方法以在循环内执行最少的步骤。在这种情况下,您可以记住每个步骤的总和,而只需添加或删除单个值,而不必每次都重新计算整个事情。

public static int arrayMaxConsecutiveSum(int[] inputArray,int k) 
{
    int sum = 0;
    int max = 0;

    for (int i = 0; i <= inputArray.Length-k; i++)
    {
        // Add the next item
        sum += inputArray[i];

        // Limit the sum to k items
        if (i > k) sum -= inputArray[i-k];

        // Is this the highest sum so far?
        if (sum > max)
            max = sum;
    }
    return max;
}
,

这是我的解决方法。

public int ArrayMaxConsecutiveSum(int[] inputArray,int k)
{
    int max = inputArray.Take(k).Sum();
    int sum = max;

    for (int i = 1; i <= inputArray.Length - k; i++)
    {
        sum = sum - inputArray[i- 1] + inputArray[i + k - 1];

        if (sum > max)
            max = sum;
    }
    return max;
}
,

是的,您永远不应该在大型列表上运行 take & skip,但这里是一个纯粹基于 LINQ 的解决方案,它既易于理解又可以在足够的时间内执行任务。是的,迭代代码仍然会胜过它,因此您必须为您的用例做出权衡。由于规模或易于理解的基准

int arrayMaxConsecutiveSum(int[] inputArray,int k)
{
    var sum = inputArray.Take(k).Sum();
    return Math.Max(sum,Enumerable.Range(k,inputArray.Length - k)
        .Max(i => sum += inputArray[i] - inputArray[i - k]));
}
本文链接:https://www.f2er.com/3168258.html

大家都在问