Calculate difference between adjacent items in a python list

Question

I have a list of millions of numbers. I want to find out if the difference between each number in the ordered list is the same for the entire list.

list_example = [ 0, 5, 10, 15, 20, 25, 30, 35, 40, ..etc etc etc]

What's the best way to do this?

My try:

import collections

list_example = [ 0, 5, 10, 15, 20, 25, 30, 35, 40 ]

count = collections.Counter()

for x,y in zip(list_example[0::],list_example[1::]):
    print x,y,y-x
    count[y-x] +=1

if len( count ) == 1:
    print 'Differences all the same'

Result:

0 5 5
5 10 5
10 15 5
15 20 5
20 25 5
25 30 5
30 35 5
35 40 5
Differences all the same

see http://stackoverflow.com/questions/3428769/finding-the-largest-delta-between-two-integers-in-a-list-in-python — jtbandes, Aug 24 '11 at 09:06
possible duplicate of [Python - Differences between elements of a list](http://stackoverflow.com/questions/2400840/python-differences-between-elements-of-a-list) — Charles Brunet, Mar 20 '13 at 15:19

score 27 · Answer 1 · answered Aug 24 '11 at 09:08

Using pure Python:

>>> x = [0,5,10,15,20]
>>> xdiff = [x[n]-x[n-1] for n in range(1,len(x))]
>>> xdiff
[5, 5, 5, 5]
>>> all([xdiff[0] == xdiff[n] for n in range(1,len(xdiff))])
True

It's a little easier, and probably faster, if you use NumPy:

>>> import numpy as np
>>> xdiff = np.diff(x)
>>> np.all(xdiff[0] == xdiff)
True

But both of these create two extra lists (or arrays, in the case of NumPy) which may gobble up your available memory if you have millions of numbers.

score 10 · Accepted Answer · answered Aug 24 '11 at 09:13

10

The straight approach here is the best:

x = s[1] - s[0]
for i in range(2, len(s)):
    if s[i] - s[i-1] != x: break
else:
    #do some work here...

answered Aug 24 '11 at 09:13

Mariy

5,746
4
40
57

I like this answer because it's simple and allows short cutting if a different difference is found. – Martlark Aug 25 '11 at 07:45

score 9 · Answer 3 · answered Aug 24 '11 at 09:35

9

Need notice that the list may have millions of numbers. So ideally, we shouldn't iterate over the entire list unless it's necessary. Also we need avoid construct new list, which may have significant memory consumption. Using all and a generator will solve the problem

 >>> x = [5, 10, 15, 20, 25]
 >>> all(x[i] - x[i-1] == x[i+1] - x[i] for i in xrange(1, len(x) - 1))
 True

answered Aug 24 '11 at 09:35

Ryan Ye

3,159
1
22
26

A more succinct and better documented solution than my second attempt.. +1 – Tim Aug 24 '11 at 09:50
3

you compute twice the diff between 2 elements, for i = 2, n-2. maybe you should extract the diff into a variable, and compare against it. – Nicolae Dascalu Aug 24 '11 at 20:11

score 7 · Answer 4 · answered Sep 04 '15 at 07:57

7

itertools.izip is great for this kind of thing:

>>> lst = [1,1,2,3,5,8]
>>> [y-x for x, y in itertools.izip (lst, lst[1:])]
[0, 1, 1, 2, 3]

answered Sep 04 '15 at 07:57

cdyson37

7,828
3
24
16

1

You can also use `itertools.starmap` to make it more efficient: `itertools.starmap(operator.sub, itertools.izip(lst[1:], lst))` – blhsing Jun 24 '18 at 17:30

score 3 · Answer 5 · edited Apr 21 '18 at 21:57

I came to this while playing around:

>>> exm = [0,5,10,15,20,25,30,35]
>>> len(set(exm[a + 1] - exm[a] for a in range(0, len(exm) - 1))) == 1

What I do is for each pair of consecutive items determine their difference in a generator. I then add all those differences to a set to only keep the unique values. If the length of this set is 1 all the differences are the same.

Edit: Looking at cldy's answer you can halt execution early when any item is found not the be the same as your initial difference:

>>> exm = [0,5,10,15,20,25,30,35]
>>> initial_diff = exm[1] - exm[0]
>>> difference_found = any((exm[a + 1] - exm[a]) != initial_diff 
                                for a in range(1, len(exm) - 1))

score 2 · Answer 6 · answered Aug 24 '11 at 10:30

2

>>> x=[10,15,20,25]
>>> diff=(x[-1]-x[0])/(len(x)-1)
>>> diff
5
>>> all(x[i]+diff==x[i+1] for i in range(len(x)-1))
True

answered Aug 24 '11 at 10:30

Rusty Rob

16,489
8
100
116

score 1 · Answer 7 · answered Aug 24 '11 at 09:49

1

Here's an example using the diff function in numpy.

e.g.

import numpy
numpy_array = numpy.zeros(10**6)
for i in xrange(10**6):
    numpy_array[i] = i
print numpy.any(numpy.diff(a) == 1)

True

answered Aug 24 '11 at 09:49

Stephen Emslie

10,539
9
32
28

score 0 · Answer 8 · edited Feb 27 '22 at 22:53

0

I had a similar problem and I used the following method:

foo = map(lambda x: lst[x+1]-lst[x],range(len(lst)-1))

edited Feb 27 '22 at 22:53

Martlark

14,208
13
83
99

answered Feb 24 '22 at 13:12

Harp

1

Use `\`\`\`python` before and `\`\`\`` after the code (at the beginning of the line) so the keywords, variables will be highlighted. – Arpad Horvath -- Слава Україні Feb 24 '22 at 18:26

score 0 · Answer 9 · answered Aug 24 '11 at 09:33

Here's a solution using iterators just for comparison.. and possibly an advantage of not needing to know the length of your input data; you might be able to avoid having the millions of list items loaded into memory in the first place...

from itertools import tee, izip

# From itertools recipes: http://docs.python.org/library/itertools.html
def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

class DifferenceError(Exception):
  pass

def difference_check(data):
  idata = pairwise(data)
  (a,b) = idata.next()
  delta = b - a
  for (a,b) in idata:
    if b - a != delta:
      raise DifferenceError("%s -> %s != %s" % (a,b,delta))
  return True

but for speed up, you should use generator list instead of manual iteration(build in function are faster). all(b-a==delta for a,b in idata) — Nicolae Dascalu, Aug 24 '11 at 20:21

Calculate difference between adjacent items in a python list

9 Answers9

Linked