如何优化列表操作？（CodeFights）

Question

所以我有一个函数，在小列表上执行得很好。它的功能是检查从序列中删除一个元素是否会使该序列成为严格的递增序列：

def almostIncreasingSequence(sequence):
    length = len(sequence)
    for i in range(1, length):
        newSequence = sequence[:i-1] + sequence[i:]
        if checkIfSorted(newSequence, length):
            return True
    return checkIfSorted(sequence[:length-1], length)

def checkIfSorted(sequence, length):
    for i in range(1, length - 1):
        if sequence[i-1] >= sequence[i]:
            return False
    return True

但我需要它来处理长达10万个元素的列表。我可以做什么样的优化来更快地工作？现在，在10万个元素的列表中，它的速度非常慢，一秒钟要处理几千个元素。

Answer 1

我的解决方案：

def is_almost_increasing(x):
    lastx = x[0]  # value to use in the next comparison
    found_one = False
    for i in range(1, len(x)):
        if x[i] <= lastx:
            if found_one:
                return False
            found_one = True
            if i > 1 and x[i] <= x[i-2]:  # i > 1 in case the first comparison failed
                break
        lastx = x[i]
    return True


print('\nThese should be True.')
print(is_almost_increasing([1]))
print(is_almost_increasing([1, 2]))
print(is_almost_increasing([1, 2, 3]))
print(is_almost_increasing([1, 3, 2]))
print(is_almost_increasing([10, 1, 2, 3, 4, 5]))
print(is_almost_increasing([0, -2, 5, 6]))
print(is_almost_increasing([1, 1]))
print(is_almost_increasing([1, 2, 3, 4, 3, 6]))
print(is_almost_increasing([1, 2, 3, 4, 99, 5, 6]))
print(is_almost_increasing([1, 2, 2, 3]))

print('\nThese should be False.')
print(is_almost_increasing([1, 3, 2, 1]))
print(is_almost_increasing([3, 2, 1]))
print(is_almost_increasing([1, 1, 1]))

这与罗里·道顿的非常相似，但略短。我从他提供的链接中借用了他的测试代码，所以感谢他。重点是你不想建立很多次要列表，这样效率很低。为了在效率上得到真正大的提高，你几乎总是需要找到一个更好的算法。

这里的两个复杂问题是（1）当第一个元素测试失败时该怎么办？（2）当你发现一个元素没有顺序时，你是删除那个元素还是删除它之前的元素？评论解决了这一点。