Python: Есть ли какой-нибудь оптимизированный способ проверить, что 2 списка увеличиваются вместе?

Question

Предположим, у нас есть 2 списка a = [1,2,4,3,5] и b = [103,122,800,500,1000]

Есть ли оптимизированный способ проверить, что они "растут вместе"?

Мое текущее решение, использует цикл:

for i in range(1,len(a)):
   if (a[i-1] < a[i] and b[i-1] > b[i]) or (a[i-1] > a[i] and b[i-1] < b[i]):
       print('wrong')

Есть ли лучший способ?

Примечания:

• Решение не должно быть специфичным для списка (на самом деле любая структура данных будет работать)
• Две итерации не должны увеличиваться на одно и то же количество единиц, они просто должны увеличиваться вместе.

Answer 1

Вот способ с пониманием списка:

c = [(a[x + 1] - a[x]) * (b[x + 1] - b[x]) for x in range(len(a) - 1)]
if any([x < 0 for x in c]):
    print('Wrong')

Сравнивая все предыдущие подходы (кроме numba), ответ tobias_k выглядит наиболее эффективным при работе с достаточно большими списками (примерно с 40 элементами списка).

Answer 2

Вы не можете получить немного быстрее, чем O (n), но вы можете сделать свой код немного короче и, возможно, более читабельным, используя numpy.diff и сравнив sign различий a и b * * 1005

>>> from numpy import diff, sign
>>> a, b = [1,2,4,3,5], [103,122,800,500,1000]
>>> sign(diff(a))
array([ 1,  1, -1,  1])
>>> all(sign(diff(a)) == sign(diff(b)))
True
>>> a, b = [1,2,4,3,5], [103,122,800,500,100]
>>> all(sign(diff(a)) == sign(diff(b)))
False

Недостатком этого решения является то, что оно не использует отложенную оценку, т. Е. Вычисляет и сравнивает весь массив sign(diff(...)), даже если "возрастание" a и b отличается в самой первой позиции. Если список очень длинный, вам следует рассмотреть возможность использования другого подхода.

Answer 3

Мы можем использовать отложенную оценку, предоставляемую итераторами Python, что означает, что нам не нужно продолжать обходить оба списка (структуры), если они не имеют одинаковый знак вариации

def compare_variation( a, b ):
    a_variations = ( a[ i - 1 ] < a[ i ] for i in range( 1, len( a ) ) )
    b_variations = ( b[ i - 1 ] < b[ i ] for i in range( 1, len( b ) ) )
    return all( x == y for x, y in zip( a_variations, b_variations  ) )

Answer 4

С точки зрения O (порядок записи), вы не можете получить лучше, чем линейный, при условии, что списки не имеют некоторого порядка.Но вы можете использовать некоторый компилятор Python, например, Cython, Numba, чтобы ускорить ваш код.Ваш код, используя numba :

import numpy as np
import numba as nb

@nb.njit()
def vary_together(a, b):
    for i in range(1,len(a)):
       if (a[i-1] < a[i] and b[i-1] > b[i]) or (a[i-1] > a[i] and b[i-1] < b[i]):
           return False
    return True 

Вы должны использовать большие списки, чтобы увидеть выигрыш в производительности.Например, если:

a = np.array([randint(0,100) for i in range(10000000)])

Тогда

vary_together(a, a)  # a as both arguments so as to make it complete the loop

имеет сравнение производительности с вашим решением как:

Ваше решение: 8,09 с
var_together: 0,2 (при втором запуске со скидкой на время компиляции).

Если вам нужно снова и снова запускать код в сценарии, выполните cache=True в декораторе nb.njit.