c# – 检查整数序列是否在增加

它需要使用Skip()和Take()并没有帮助,它们本身增加了处理原始序列的开销.

一种不同的方法是扫描序列一次,但是跟踪是否已经尝试删除以及何时找到无序元素,a)如果已经找到删除则立即返回false,并且b)don’ t在确定序列时包括删除的元素.

你尝试的代码几乎完成了这一点.这是一个有效的版本：

static bool almostIncreasingSequence(int[] sequence)
{
    bool foundOne = false;

    for (int i = -1,j = 0,k = 1; k < sequence.Length; k++)
    {
        bool deleteCurrent = false;

        if (sequence[j] >= sequence[k])
        {
            if (foundOne)
            {
                return false;
            }
            foundOne = true;

            if (k > 1 && sequence[i] >= sequence[k])
            {
                deleteCurrent = true;
            }
        }

        if (!foundOne)
        {
            i = j;
        }

        if (!deleteCurrent)
        {
            j = k;
        }
    }

    return true;
}

注意：我原本以为你的尝试可以修改一下.但最终,事实证明它必须与我写的通用实现基本相同(特别是一旦我修复了那个……见下文).唯一的实质差异实际上只是一个人使用数组还是一般的IEnumerable< T>.

对于笑话,我写了另一种方法,它基于LINQ的解决方案,因为它适用于任何序列,而不仅仅是数组.我也使它成为通用的(尽管有类型实现IComparable< T>的约束).看起来像这样：

static bool almostIncreasingSequence<T>(IEnumerable<T> sequence) where T : IComparable<T>
{
    bool foundOne = false;
    int i = 0;
    T previous = default(T),previousPrevious = default(T);

    foreach (T t in sequence)
    {
        bool deleteCurrent = false;

        if (i > 0)
        {
            if (previous.CompareTo(t) >= 0)
            {
                if (foundOne)
                {
                    return false;
                }

                // So,which one do we delete? If the element before the previous
                // one is in sequence with the current element,delete the previous
                // element. If it's out of sequence with the current element,delete
                // the current element. If we don't have a previous previous element,// delete the previous one.

                if (i > 1 && previousPrevious.CompareTo(t) >= 0)
                {
                    deleteCurrent = true;
                }

                foundOne = true;
            }
        }

        if (!foundOne)
        {
            previousPrevious = previous;
        }

        if (!deleteCurrent)
        {
            previous = t;
        }
        i++;
    }

    return true;
}

当然,如果您愿意将原始序列复制到临时数组中,如果它不是一个,那么您可以轻松地使基于数组的版本通用,这将使代码更简单但仍然通用.这取决于您的优先事项.

附录：

LINQ方法和线性方法(例如我的上面)之间的基本性能差异是显而易见的,但我很好奇并希望量化这种差异.所以我使用随机生成的序列进行了一些测试,以大致了解差异.

我执行了两个版本的测试：第一个,我运行了1000个试验的循环,其中序列可以是10到100个元素之间的任何长度;第二次,有10,000次试验,序列长度在100到1000之间.我执行了第二个版本,因为在我的笔记本电脑上,1000个试验中的较短序列的完整测试在不到1/20秒的时间内完成,这对于我对结果的有效性有信心的时间太短.

对于第一个版本,代码花了大约1ms来调用检查的线性方法,大约30ms调用LINQ方法,速度差为30倍.将试验次数增加到10,000次证实了结果;对于每种方法,时间几乎完全缩放10倍,保持相差30倍.

在第二个版本中,差异接近400倍.线性版本花了大约0.07秒,而LINQ版本需要30秒.

正如所料,序列越长,差异越大.对于非常短的序列,不仅代码不太可能在序列检查逻辑中花费太多时间,线性和LINQ方法之间的差异将相对较小.但随着序列变得越来越长,LINQ版本的差异将导致性能非常差,而线性版本仍然表现出色.

LINQ版本非常易读且简洁.因此,在输入总是相对较短的情况下(最多只有十几个元素),我会使用LINQ版本.但是如果我希望用比这更长的数据定期执行这个测试,我会避免使用LINQ并坚持使用更高效的线性方法.

关于随机生成的序列的注释：我编写了代码以生成一个单调递增的非负数序列,具有所需长度,然后在0和2(包括)之间插入具有int.MinValue值的新元素或int.MaxValue(也为每次插入随机选择).通过这种方式,三分之一的测试涉及非常有效的序列,第三部分涉及需要找到正确的单个元素去除的序列,第三部分无效(即不符合可以单调增加的要求)删除最多一个元素).