确定一个列表是否为降序

Question

我正在尝试编写一个函数，用于测试一个列表是否按降序排列。这是我目前的代码，但似乎并不适用于所有列表。

我使用了列表 [9,8,5,1,4,3,2] ，它返回了 'true' 。

我无法弄清楚我的错误在哪里。

def ordertest(A):
    n = len(A)
    for i in range(n):
        if A[i] >= A[i+1]:
            return 'true'
        else:
            return 'false'

- user1653420

---

list(reversed(sorted(lis)))==lis - Ashwini Chaudhary

Answer 1

你可以使用 生成器表达式 和 all() 内置函数 轻松完成此操作：

all(earlier >= later for earlier, later in zip(seq, seq[1:]))

例如：

>>> seq = [9, 8, 5, 1, 4, 3, 2] 
>>> all(earlier >= later for earlier, later in zip(seq, seq[1:]))
False
>>> seq = [9, 8, 5, 4, 3, 2] 
>>> all(earlier >= later for earlier, later in zip(seq, seq[1:]))
True

如果你使用itertools.izip()（对于2.x版本）, 这将非常快且避免了Python端的循环，并且在短路时表现良好。此外，这种实现清晰易懂而且可读性好（例如避免索引循环）。

需要注意的是，也可以提供适用于所有迭代器（而不仅限于序列）的通用解决方案：

first, second = itertools.tee(iterable)
next(second)
all(earlier >= later for earlier, later in zip(first, second))

- Gareth Latty

---

@Lattyware.. +1 我太喜欢你的逻辑了.. :) - Rohit Jain

你可能会对我的基准测试感兴趣 https://dev59.com/Z2cs5IYBdhLWcg3wk0-X#12734223 -- 看起来这可能相当慢。 - zigg

我使用izip再次运行它，现在是最快的解决方案。对此很抱歉 :-) - zigg

这非常聪明。谢谢！ - imiric

Answer 2

你应该进行反向检查（一旦你得到 A[i] < A[i+1]，就返回false）。

def ordertest(A):
    for i in range( len(A) - 1 ):
        if A[i] < A[i+1]:
            return False
        return True

- Rohit Jain

---

通过索引访问迭代感觉非常不符合Python风格（更别提可能会慢）. - phihag

@phihag，您可以取消您的反对意见。如果您曾经反对过，我已经编辑了代码。 - Rohit Jain

谢谢你的帮助。如果您不介意解释一下，为什么这个范围的更改修复了问题？ - user1653420

这似乎非常高效。我对其进行了基准测试：https://dev59.com/Z2cs5IYBdhLWcg3wk0-X#12734223 - zigg

原因是在Python 2.x中，“zip()”不是惰性的 - 它生成一个列表，这意味着整个列表都会被计算，无论是否使用它。我通常使用3.x，在那里“zip()”提供了一个生成器，并且确实建议在2.x下使用“izip()”。 - Gareth Latty

Answer 3

这里有一种简洁的方法来执行这个测试，它使用了all():

def ordertest(A):
    return all(A[i] >= A[i+1] for i in range(len(A)-1))

示例：

>>> ordertest([9,8,5,1,4,3,2])
False
>>> ordertest([9,8,5,4,3,2,1])
True

- Andrew Clark

---

循环索引不够Pythonic。 - Gareth Latty

通常是这样的，但是这种方法比你回答中的切片/压缩方法更有效率，而且仍然非常易读。 - Andrew Clark

我必须说，在可读性方面我不同意，而且我想效率提升微乎其微。 - Gareth Latty

我将这个程序插入到我的基准测试中，网址是https://dev59.com/Z2cs5IYBdhLWcg3wk0-X#12734223，它用了0.597107172012秒。虽然比步行要快，但仍然比使用`izip`慢 - 而zip确实相当慢。 - zigg

真的很好理解的一行代码。如果它快速且易于理解，谁会在意Pythonic呢？ - Salvador Dali

Answer 4

我最初建议使用sorted，但有人指出这可能不如迭代方式高效。

>>> l = [3, 1, 2]
>>> l == sorted(l, reverse=True)
False
>>> l = [3, 2, 1]
>>> l == sorted(l, reverse=True)
True

我对被接受的答案、我的答案、Lattyware的生成器解决方案以及使用itertools.izip的相同情况进行了基准测试。我故意选择了一种我认为会有利于我的sorted解决方案的情况：一个仅在末尾乱序的列表。这些基准测试是在一个旧的OpenBSD机器上的Python 2.7.1上执行的。 sorted.py

import time
l = list(reversed(range(99998) + [99999, 99998]))
start = time.time()
for count in range(100):
    l == sorted(l)
end = time.time()
print('elapsed: {}'.format(end - start))

walk.py

import time
def ordertest(l):
    for i in range(len(l) - 1):
        if l[i] < l[i+1]:
            return False
    return True
l = list(reversed(range(99998) + [99999, 99998]))
start = time.time()
for count in range(100):
    ordertest(l)
end = time.time()
print('elapsed: {}'.format(end - start))

generator.py

import time
l = list(reversed(range(99998) + [99999, 99998]))
start = time.time()
for count in range(100):
    all(earlier >= later for earlier, later in zip(l, l[1:]))
end = time.time()
print('elapsed: {}'.format(end - start))

izip.py

import itertools
import time
l = list(reversed(range(99998) + [99999, 99998]))
start = time.time()
for count in range(100):
    all(earlier >= later for earlier, later in itertools.izip(l, l[1:]))
end = time.time()
print('elapsed: {}'.format(end - start))

结果如下：

$ python sorted.py
elapsed: 1.0896859169
$ python walk.py
elapsed: 0.641126155853
$ python generator.py
elapsed: 4.79061508179
$ python izip.py
elapsed: 0.363445997238

正如在这个答案的评论中指出的那样，生成器表达式很可能因为zip复制列表而变慢。 使用izip是最好的选择。

- zigg

---

这会浪费很多 CPU 时间，而且没有特别的原因——尤其是在列表很长的情况下。 - Benjamin Pollack

它这样做吗？我会期望 sorted 的实现比使用 for 循环迭代、比较项目顺序更有效率。 - zigg

for循环可以在任何元素大于其前一个元素时立即退出。即使sorted使用堆（实际上它没有），你仍需要O(N*log(N))的时间复杂度，而简单的for循环只需要O(N)，因此在常见情况下更慢。 - Benjamin Pollack

@BenjaminPollack，你的反馈促使我进行了一些基准测试，并将其编辑到我的答案中。你是对的，即使在我预期会给我优势的情况下也是如此！ - zigg

zip 创建一个副本列表，而 izip 则不会。我想这会有很大的影响。 - moooeeeep

Answer 5

不必使用索引，可以对输入进行迭代：

def ordertest(iterable):
    it = iter(iterable)
    prev = next(it)
    for e in it:
        if e > prev:
            return False
        prev = e
    return True

请注意，返回字符串'true'和'false'是一个不好的做法。相反，您可以使用Python内置的布尔值。

- phihag

Answer 6

你想做的是：

n=len(A)
for i in range(n - 1):
    if A[i]<=A[i+1]:
        return 'false'
return 'true

试着在你的脑海中执行代码。在第一次迭代中，如果A[i]大于A[i + 1]，则返回true，否则返回false。你永远不会继续遍历列表。

一个好的解决方案是测试你的条件，如果任何时候为false，则返回false。但如果它正确，这并不意味着列表的其余部分也是正确的，你想测试每个值。

当你测试A[i + 1]时，你不想遍历到列表的末尾，而是到它的第n - 1项。

- tomahh

Answer 7

n=len(l)
c=0
for i in range(n - 1):
    if l[i]<l[i+1]:
        c+=1
    if c==1:
        break
if(c==1):
    return False
return True

为了检查是否有错误并且正确地进行检查，使用计数器的函数是最好的。一旦循环运行并且迭代变成1，它就会停止搜索。如果没有错误，它将返回false，否则返回true。 谢谢！

- Suryapratim Ray