确定列表是否按降序排列

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'

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

这应该是好的和快速的,因为它避免了python端循环,很好地短路(如果你itertools.izip()在2.x中使用),并且很好,清晰和可读(例如,避免循环索引).

请注意,所有迭代器(不仅仅是序列)的通用解决方案也是可行的:

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

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

Answer 3

我最初建议使用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节拍.

Answer 4

您可以迭代输入,而不是使用索引:

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的内置布尔值.

Answer 5

以下是执行此测试的简明方法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