CODEWITHSUNDEEP
pythonsequence
dozyaustin
dozyaustin

Reputation: 661

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

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:

Upvotes: 3

Views: 417

Answers (4)

Patol75
Patol75

Reputation: 4547

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

Upvotes: 0

Deepak Saini
Deepak Saini

Reputation: 2900

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.

Upvotes: 3

rachid
rachid

Reputation: 2486

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

Upvotes: 2

tobias_k
tobias_k

Reputation: 82899

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.

Upvotes: 3

Related Questions