CODEWITHSUNDEEP
pythonarraysperformancenumpy
Gabriel
Gabriel

Reputation: 42329

Find largest difference between adjacent floats in ordered array

Say I have an ordered array/list like this one:

a = [0.2, 0.35, 0.88, 1.2, 1.33, 1.87, 2.64, 2.71, 3.02]

I want to find the largest difference between adjacent elements efficiently. In this case it would be (2.64 - 1.87) = 0.77.

I could use a for loop but I wonder if there's a more elegant/efficient solution. Solutions using numpy are welcomed.

TEST

OK, I took all the answers and tested them (see code at the bottom). These are the results in seconds:

0.0867638587952 0.118239144757 mark
0.00386190414429 0.118239144757 Padraic
0.00108003616333 0.118239144757 mtrw
0.0790281295776 0.118239144757 yurib
0.000712156295776 0.118239144757 elyase

which means elyase is the winner by several orders of magnitude. Thank you all!

MWE:

import numpy as np
import time

a = np.sort(np.random.uniform(0., 1000., 100000))

tik = time.time()
val = max(y - x for x,y in zip(a, a[1:]))
print time.time() - tik, val, 'mark'

tik = time.time()
val = np.ediff1d(a).max()
print time.time() - tik, val, 'Padraic'

tik = time.time()
val = np.max(np.abs(np.diff(a)))
print time.time() - tik, val, 'mtrw'

tik = time.time()
val = max(a[i+1]-a[i] for i in range(len(a)-1))
print time.time() - tik, val, 'yurib'

tik = time.time()
val = np.diff(a).max()
print time.time() - tik, val, 'elyase'

Upvotes: 1

Views: 1430

Answers (5)

jme
jme

Reputation: 20695

If we want to get a little crazy about performance, we can use numba:

import numba

@autojit
def max_consecutive_diff(x):
    prev = x[0]
    diff_max = 0.0

    for i in range(1, len(x)):
        cur = x[i]
        diff = cur - prev

        if diff > diff_max:
            diff_max = diff

        prev = cur

    return diff_max

Here's a speed test. Generating data with

>>> x = np.sort(np.random.sample(1e7))

we get:

>>> %timeit max_consecutive_diff(x)
100 loops, best of 3: 11.9 ms per loop

>>> %timeit np.max(np.diff(x))
10 loops, best of 3: 33.9 ms per loop

Of course, these are milliseconds for ten-million long input array. I'd just stick with the np.diff solution, but it's always cool to see how well numba can do.

Upvotes: 2

Padraic Cunningham
Padraic Cunningham

Reputation: 180401

a = [0.2, 0.35, 0.88, 1.2, 1.33, 1.87, 2.64, 2.71, 3.02]

import numpy as np
print(np.ediff1d(a).max())
0.77

Difference between diff and ediff1d is ediff1d will flatten before comparing:

In [18]: y = [[1, 2, 4], [1, 6, 24]]

In [19]: print(np.ediff1d(y))
[ 1  2 -3  5 18]

In [20]: print(np.diff(y))
[[ 1  2]
 [ 5 18]]

Upvotes: 1

elyase
elyase

Reputation: 40963

A numpy solution:

np.diff(a).max()

Upvotes: 6

Mark Ransom
Mark Ransom

Reputation: 308148

I can't claim it's more efficient or more elegant, but it's different:

>>> max(y - x for x,y in zip(a, a[1:]))
0.77

Upvotes: 4

yurib
yurib

Reputation: 8147

max(a[i+1]-a[i] for i in range(len(a)-1))

Upvotes: 2

Related Questions