Python: Any optimized way to check that 2 lists increase together?

user_6907488 0
Viewed 219

Let's assume we have 2 lists a = [1,2,4,3,5] and b = [103,122,800,500,1000]

is there an optimized way that I can check that they are "increasing together"?

My current solution, employs a loop: 

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')

Is there a better way?

Notes:

  • The solution does not need to be list specific (really any data structure would work)
  • The two iterables do not need to increase by the same number of units, just have to increase together.
sequence python
4 Answers

In terms of O(order notation), you can't get better than linear, assuming lists don't have some order. But, you can use some python compiler like cython, numba to speed up your code. Your code using 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

You have to use large lists to see the performance benefit. For example, if:

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

Then,

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

Has has the performance comparison to your solution as :

Your solution: 8.09s
vary_together: 0.2 (on second run to discount for compile time).

If you need to run the code again and again in the script, do cache=True in the nb.njit decorator.

user_39245660

You can't really get any faster than O(n), but you could make your code a bit shorter and maybe more readable by using numpy.diff and comparing the sign of the diffs of a and b:

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

The downside of this solution is that it does not use lazy-evaluation, i.e. it calculates and compares the entire sign(diff(...)) array even if the "increasingness" of a and b differs in the very first position. If the list is very long, you should consider using another approach.

user_16396250

We can use the lazy evaluation provided by python iterators, meaning we don't need to continue traversing both lists ( structures ) once they don't have the same variation sign

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  ) )
user_74246340

Here is a way with list comprehension:

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')

Comparing all the previous approaches (except for the numba one), tobias_k's answer looks like most efficient when dealing with large enough lists (at list 40 elements roughly).

user_106405340
Related