Python-如何检查列表的单调性

什么是 有效率的和蟒蛇般的检查列表单调性的方法? < br > 即它具有单调增加或减少的值？

例子:

[0, 1, 2, 3, 3, 4]   # This is a monotonically increasing list
[4.3, 4.2, 4.2, -2]  # This is a monotonically decreasing list
[2, 3, 1]            # This is neither
67440 次浏览
小开 
L = [1,2,3]
L == sorted(L)


L == sorted(L, reverse=True)
小开 
>>> seq = [0, 1, 2, 3, 3, 4]
>>> seq == sorted(seq) or seq == sorted(seq, reverse=True)
小开 
import itertools
import operator


def monotone_increasing(lst):
pairs = zip(lst, lst[1:])
return all(itertools.starmap(operator.le, pairs))


def monotone_decreasing(lst):
pairs = zip(lst, lst[1:])
return all(itertools.starmap(operator.ge, pairs))


def monotone(lst):
return monotone_increasing(lst) or monotone_decreasing(lst)

This approach is O(N) in the length of the list.

小开
最佳答案

It's better to avoid ambiguous terms like "increasing" or "decreasing" as it's not clear if equality is acceptable or not. You should always use either for example "non-increasing" (clearly equality is accepted) or "strictly decreasing" (clearly equality is NOT accepted).

def strictly_increasing(L):
return all(x<y for x, y in zip(L, L[1:]))


def strictly_decreasing(L):
return all(x>y for x, y in zip(L, L[1:]))


def non_increasing(L):
return all(x>=y for x, y in zip(L, L[1:]))


def non_decreasing(L):
return all(x<=y for x, y in zip(L, L[1:]))


def monotonic(L):
return non_increasing(L) or non_decreasing(L)
小开

If you have large lists of numbers it might be best to use numpy, and if you are:

import numpy as np


def monotonic(x):
dx = np.diff(x)
return np.all(dx <= 0) or np.all(dx >= 0)

should do the trick.

小开 
import operator, itertools


def is_monotone(lst):
op = operator.le            # pick 'op' based upon trend between
if not op(lst[0], lst[-1]): # first and last element in the 'lst'
op = operator.ge
return all(op(x,y) for x, y in itertools.izip(lst, lst[1:]))
小开

@6502 has an elegant code for sequences (iterables with __getitem__ and __len__ methods) and @chqrlie has an even better code which does not create temporary copies of sequences with slicing. I just want to add a general version that works for all iterables (objects with an __iter__ method):

def pairwise(iterable):
items = iter(iterable)
last = next(items)
for item in items:
yield last, item
last = item


def strictly_increasing(iterable):
return all(x<y for x, y in pairwise(iterable))


def strictly_decreasing(iterable):
return all(x>y for x, y in pairwise(iterable))


def non_increasing(iterable):
return all(x>=y for x, y in pairwise(iterable))


def non_decreasing(iterable):
return all(x<=y for x, y in pairwise(iterable))


def monotonic(iterable):
return non_increasing(iterable) or non_decreasing(iterable)
小开

Here is a functional solution using reduce of complexity O(n):

is_increasing = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999


is_decreasing = lambda L: reduce(lambda a,b: b if a > b else -9999 , L)!=-9999

Replace 9999 with the top limit of your values, and -9999 with the bottom limit. For example, if you are testing a list of digits, you can use 10 and -1.

I tested its performance against @6502's answer and its faster.

Case True: [1,2,3,4,5,6,7,8,9]

# my solution ..
$ python -m timeit "inc = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999; inc([1,2,3,4,5,6,7,8,9])"
1000000 loops, best of 3: 1.9 usec per loop


# while the other solution:
$ python -m timeit "inc = lambda L: all(x<y for x, y in zip(L, L[1:]));inc([1,2,3,4,5,6,7,8,9])"
100000 loops, best of 3: 2.77 usec per loop

Case False from the 2nd element: [4,2,3,4,5,6,7,8,7]:

# my solution ..
$ python -m timeit "inc = lambda L: reduce(lambda a,b: b if a < b else 9999 , L)!=9999; inc([4,2,3,4,5,6,7,8,7])"
1000000 loops, best of 3: 1.87 usec per loop


# while the other solution:
$ python -m timeit "inc = lambda L: all(x<y for x, y in zip(L, L[1:]));inc([4,2,3,4,5,6,7,8,7])"
100000 loops, best of 3: 2.15 usec per loop
小开

I timed all of the answers in this question under different conditions, and found that:

  • Sorting was the fastest by a long shot IF the list was already monotonically increasing
  • Sorting was the slowest by a long shot IF the list was shuffled/random or if the number of elements out of order was greater than ~1. The more out of order the list of course corresponds to a slower result.
  • Michael J. Barbers method was the fastest IF the list was mostly monotonically increasing, or completely random.

Here is the code to try it out:

import timeit


setup = '''
import random
from itertools import izip, starmap, islice
import operator


def is_increasing_normal(lst):
for i in range(0, len(lst) - 1):
if lst[i] >= lst[i + 1]:
return False
return True


def is_increasing_zip(lst):
return all(x < y for x, y in izip(lst, islice(lst, 1, None)))


def is_increasing_sorted(lst):
return lst == sorted(lst)


def is_increasing_starmap(lst):
pairs = izip(lst, islice(lst, 1, None))
return all(starmap(operator.le, pairs))


if {list_method} in (1, 2):
lst = list(range({n}))
if {list_method} == 2:
for _ in range(int({n} * 0.0001)):
lst.insert(random.randrange(0, len(lst)), -random.randrange(1,100))
if {list_method} == 3:
lst = [int(1000*random.random()) for i in xrange({n})]
'''


n = 100000
iterations = 10000
list_method = 1


timeit.timeit('is_increasing_normal(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)


timeit.timeit('is_increasing_zip(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)


timeit.timeit('is_increasing_sorted(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)


timeit.timeit('is_increasing_starmap(lst)', setup=setup.format(n=n, list_method=list_method), number=iterations)

If the list was already monotonically increasing (list_method == 1), the fastest to slowest was:

  1. sorted
  2. starmap
  3. normal
  4. zip

If the list was mostly monotonically increasing (list_method == 2), the fastest to slowest was:

  1. starmap
  2. zip
  3. normal
  4. sorted

(Whether or not the starmap or zip was fastest depended on the execution and I couldn't identify a pattern. Starmap appeared to be usually faster)

If the list was completely random (list_method == 3), the fastest to slowest was:

  1. starmap
  2. zip
  3. normal
  4. sorted (extremely bad)
小开

The pandas package makes this convenient.

import pandas as pd

The following commands work with a list of integers or floats.

Monotonically increasing (≥):

pd.Series(mylist).is_monotonic_increasing

Strictly monotonically increasing (>):

myseries = pd.Series(mylist)
myseries.is_unique and myseries.is_monotonic_increasing

Alternative using an undocumented private method:

pd.Index(mylist)._is_strictly_monotonic_increasing

Monotonically decreasing (≤):

pd.Series(mylist).is_monotonic_decreasing

Strictly monotonically decreasing (<):

myseries = pd.Series(mylist)
myseries.is_unique and myseries.is_monotonic_decreasing

Alternative using an undocumented private method:

pd.Index(mylist)._is_strictly_monotonic_decreasing
小开

Here's a variant that accepts both materialized and non-materialized sequences. It automatically determines whether or not it's monotonic, and if so, its direction (i.e. increasing or decreasing) and strictness. Inline comments are provided to help the reader. Similarly for test-cases provided at the end.

    def isMonotonic(seq):
"""
seq.............: - A Python sequence, materialized or not.
Returns.........:
(True,0,True):   - Mono Const, Strict: Seq empty or 1-item.
(True,0,False):  - Mono Const, Not-Strict: All 2+ Seq items same.
(True,+1,True):  - Mono Incr, Strict.
(True,+1,False): - Mono Incr, Not-Strict.
(True,-1,True):  - Mono Decr, Strict.
(True,-1,False): - Mono Decr, Not-Strict.
(False,None,None) - Not Monotonic.
"""
items = iter(seq) # Ensure iterator (i.e. that next(...) works).
prev_value = next(items, None) # Fetch 1st item, or None if empty.
if prev_value == None: return (True,0,True) # seq was empty.


# ============================================================
# The next for/loop scans until it finds first value-change.
# ============================================================
# Ex: [3,3,3,78,...] --or- [-5,-5,-5,-102,...]
# ============================================================
# -- If that 'change-value' represents an Increase or Decrease,
#    then we know to look for Monotonically Increasing or
#    Decreasing, respectively.
# -- If no value-change is found end-to-end (e.g. [3,3,3,...3]),
#    then it's Monotonically Constant, Non-Strict.
# -- Finally, if the sequence was exhausted above, which means
#    it had exactly one-element, then it Monotonically Constant,
#    Strict.
# ============================================================
isSequenceExhausted = True
curr_value = prev_value
for item in items:
isSequenceExhausted = False # Tiny inefficiency.
if item == prev_value: continue
curr_value = item
break
else:
return (True,0,True) if isSequenceExhausted else (True,0,False)
# ============================================================


# ============================================================
# If we tricked down to here, then none of the above
# checked-cases applied (i.e. didn't short-circuit and
# 'return'); so we continue with the final step of
# iterating through the remaining sequence items to
# determine Monotonicity, direction and strictness.
# ============================================================
strict = True
if curr_value > prev_value: # Scan for Increasing Monotonicity.
for item in items:
if item < curr_value: return (False,None,None)
if item == curr_value: strict = False # Tiny inefficiency.
curr_value = item
return (True,+1,strict)
else:                       # Scan for Decreasing Monotonicity.
for item in items:
if item > curr_value: return (False,None,None)
if item == curr_value: strict = False # Tiny inefficiency.
curr_value = item
return (True,-1,strict)
# ============================================================




# Test cases ...
assert isMonotonic([1,2,3,4])     == (True,+1,True)
assert isMonotonic([4,3,2,1])     == (True,-1,True)
assert isMonotonic([-1,-2,-3,-4]) == (True,-1,True)
assert isMonotonic([])            == (True,0,True)
assert isMonotonic([20])          == (True,0,True)
assert isMonotonic([-20])         == (True,0,True)
assert isMonotonic([1,1])         == (True,0,False)
assert isMonotonic([1,-1])        == (True,-1,True)
assert isMonotonic([1,-1,-1])     == (True,-1,False)
assert isMonotonic([1,3,3])       == (True,+1,False)
assert isMonotonic([1,2,1])       == (False,None,None)
assert isMonotonic([0,0,0,0])     == (True,0,False)

I suppose this could be more Pythonic, but it's tricky because it avoids creating intermediate collections (e.g. list, genexps, etc); as well as employs a fall/trickle-through and short-circuit approach to filter through the various cases: E.g. Edge-sequences (like empty or one-item sequences; or sequences with all identical items); Identifying increasing or decreasing monotonicity, strictness, and so on. I hope it helps.

小开

@6502 has elegant python code for this. Here is an alternative solution with simpler iterators and no potentially expensive temporary slices:

def strictly_increasing(L):
return all(L[i] < L[i+1] for i in range(len(L)-1))


def strictly_decreasing(L):
return all(L[i] > L[i+1] for i in range(len(L)-1))


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


def non_decreasing(L):
return all(L[i] <= L[i+1] for i in range(len(L)-1))


def monotonic(L):
return non_increasing(L) or non_decreasing(L)
小开 
def IsMonotonic(data):
''' Returns true if data is monotonic.'''
data = np.array(data)
# Greater-Equal
if (data[-1] > data[0]):
return np.all(data[1:] >= data[:-1])
# Less-Equal
else:
return np.all(data[1:] <= data[:-1])

My proposition (with numpy) as a summary of few ideas here. Uses

  • casting to np.array for creation of bool values for each lists comparision,
  • np.all for checking if all results are True
  • checking diffrence between first and last element for choosing comparison operator,
  • using direct comparison >=, <= instead of calculatin np.diff,
小开

Here are two ways of determining if a list if monotonically increasing or decreasing using just range or list comprehensions. Using range is slightly more efficient because it can short-circuit, whereas the list comprehension must iterate over the entire list. Enjoy.

a = [1,2,3,4,5]
b = [0,1,6,1,0]
c = [9,8,7,6,5]


def monotonic_increase(x):
if len(x) <= 1: return False


for i in range(1, len(x)):
if x[i-1] >= x[i]:
return False
return True


def monotonic_decrease(x):
if len(x) <= 1: return False


for i in range(1, len(x)):
if x[i-1] <= x[i]:
return False


return True


monotonic_increase = lambda x: len(x) > 1 and all(x[i-1] < x[i] for i in range(1, len(x)))
monotonic_decrease = lambda x: len(x) > 1 and all(x[i-1] > x[i] for i in range(1, len(x)))


print(monotonic_increase(a))
print(monotonic_decrease(c))
print(monotonic_decrease([]))
print(monotonic_increase(c))
print(monotonic_decrease(a))
print(monotonic_increase(b))
print(monotonic_decrease(b))
小开 
def solution1(a):
up, down = True, True
for i in range(1, len(a)):
if a[i] < a[i-1]: up = False
if a[i] > a[i-1]: down = False
return up or down
    

def solution2(a):
return a == sorted(a[::-1])

Solution1 is O(n) and the shorter solution2 is O(n log n)

小开

summary: Yes, setting a single variable from another variable is thread safe. This provides a high-speed way to transfer a single value bewteen tasks.

this link has a clear explanation:Grok the GIL: How to write fast and thread-safe Python

My simplified explanation:

All computers, way down at the machine code, provide some (not all) instructions that are non-interruptable. These are reffered to as "atomic".

For example, storing a 16 bit-constant into a 16-bit memory location. way-back the 8-bit computers were a mix of features and implimentations. For example, the 8-bit processors 6502, 6800 both had non-interruptable (atomic) instructions to move 16-bits from one memory location to another. The Z80 did not. The PDP-11 machine code had an atomic increment/decrement instructions (var++; v--) which is how K&R came to add that to the early C compilers. At least from what I remember.

Why does this matter?

Today a lot of computer programming languages are written to a custom-designed "virtual machine". These virtual machines, like all computer processors, support a mix of features and implimentations.

Python's virtual machine is written with it's custom GIL ("global interpreter lock")

what this means is that some (but not all) python's operations are "thread-safe" in that some (but not all) execute in a single "GIL" cycle.

There are some surprises. For example "sort" is atomic and therefor thread-safe. Since this is a relatively long process, that's a surprise (read the link for a much better explanation)

Python has a function that will display the "virtual machine codes" a function is "compiled" into:

## ref: https://opensource.com/article/17/4/grok-gil
import dis


vara= 33
varb= 55


def foo():
global vara
vara= 33
varb= 55
varb= vara
return


dis.dis(foo)

which gives the output:

415           0 LOAD_CONST               1 (33)
2 STORE_GLOBAL             0 (vara)


416           4 LOAD_CONST               2 (55)
6 STORE_FAST               0 (varb)


417           8 LOAD_GLOBAL              0 (vara)
10 STORE_FAST               0 (varb)


418          12 LOAD_CONST               0 (None)
14 RETURN_VALUE

Care must be taken when using this (well, all multithreaded programs should be carefully designed and coded) since ONLY A SINGLE value is safe! The good news is that this SINGLE VALUE can point to an entire data structure. Of course the entired data structure isn't atomic so any changes to it should be wrapped in mutlithread "stalls" (another name for semaphores, locks, etc- since they basically "stall" the code, until the semaphores/locks are released by other threads. I read this somewhere from one of the co-developers of multithreading...in hindsight he thought "stalls" were a better, more discription term. Perhaps dijkstra??)

小开

Here is an implementation that is both efficient (the space required is constant, no slicing performing a temporary shallow copy of the input) and general (any iterables are supported as input, not just sequences):

def is_weakly_increasing(iterable):
iterator = iter(iterable)
next(iterator)
return all(x <= y for x, y in zip(iterable, iterator))




def is_weakly_decreasing(iterable):
iterator = iter(iterable)
next(iterator)
return all(x >= y for x, y in zip(iterable, iterator))




def is_weakly_monotonic(iterable):
return is_weakly_increasing(iterable) or is_weakly_decreasing(iterable)




def is_strictly_increasing(iterable):
iterator = iter(iterable)
next(iterator)
return all(x < y for x, y in zip(iterable, iterator))




def is_stricly_decreasing(iterable):
iterator = iter(iterable)
next(iterator)
return all(x > y for x, y in zip(iterable, iterator))




def is_strictly_monotonic(iterable):
return is_strictly_increasing(iterable) or is_strictly_decreasing(iterable)

提交答案