Python-목록 단 조성을 확인하는 방법

Python-목록 단 조성을 확인하는 방법

---

목록 단 조성을 확인 하는 효율적이고 비단뱀적인 방법 은 무엇입니까 ?
즉, 단조롭게 증가하거나 감소하는 값이 있습니까?

예 :

[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

---

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)

---

숫자 목록이 많은 경우 numpy를 사용하는 것이 가장 좋을 수 있으며 다음과 같은 경우에는

import numpy as np

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

트릭을해야합니다.

---

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)

이 접근 방식은 O(N)목록의 길이에 있습니다.

---

@ 6502에는 목록에 대한 완벽한 코드가 있습니다. 모든 시퀀스에서 작동하는 일반 버전을 추가하고 싶습니다.

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

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

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

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

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

---

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:]))

---

다음은 reduce복잡성을 사용하는 기능적 솔루션 입니다 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

9999값의 상한선과 하한선으로 바꿉니다 -9999. 예를 들어 숫자 목록을 테스트하는 경우 10및 을 사용할 수 있습니다 -1.

---

@ 6502의 답변 과 그 속도 에 대해 성능을 테스트했습니다 .

사례 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

두 번째 요소의 경우 False :[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

---

L = [1,2,3]
L == sorted(L)

L == sorted(L, reverse=True)

---

이 질문의 모든 답변을 다른 조건에서 시간을 측정 한 결과 다음을 발견했습니다.

• 목록이 이미 단조롭게 증가하는 경우 정렬은 롱샷으로 가장 빠릅니다.
• 목록이 셔플 / 무작위이거나 순서가 잘못된 요소의 수가 ~ 1보다 큰 경우 정렬 속도가 가장 느 렸습니다. 물론 목록이 순서가 맞지 않을수록 결과가 느려집니다.
• 목록이 대부분 단조롭게 증가하거나 완전히 무작위 인 경우 Michael J. Barbers 방법이 가장 빠릅니다.

시도해 볼 수있는 코드는 다음과 같습니다.

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)

목록이 이미 단조롭게 증가하는 경우 ( list_method == 1), 가장 빠른 것에서 가장 느린 것 :

1. 분류
2. 스타 맵
3. 표준
4. 지퍼

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)

---

This is possible using Pandas which you can install via pip install pandas.

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

---

>>> l = [0,1,2,3,3,4]
>>> l == sorted(l) or l == sorted(l, reverse=True)

참고URL : https://stackoverflow.com/questions/4983258/python-how-to-check-list-monotonicity