Find min/max by index in list of lists

Given a list of lists of size 2, I am trying to find the quickest way to determine the min/max value by index. The goal is to determine the bounds/extent of a series of XY points.

The sublists are unsorted (sorting on one index doesn't guarantee the other is sorted).

Currently I am doing the following:

xy = [(x1, y1), (x2, y2), ..., (xn, yn)]

xs, ys = zip(*xy)
xmax = max(xs)
xmin = min(xs)
ymax = max(ys)
ymin = min(ys)

If not mistaken, each operation is O(n), so overall complexity is O(n).

Is there a faster way for an list of arbitrary size?

Here a couple of alternate methods:

def extrema_zip(items):
split0, split1 = zip(*items)
return max(split0), min(split0), max(split1), min(split1)

def extrema_key(items):
return (
max(items, key=lambda x: x[0])[0],
min(items, key=lambda x: x[0])[0],
max(items, key=lambda x: x[1])[1],
min(items, key=lambda x: x[1])[1])

import numpy as np
def extrema_np(items):
arr = np.array(items)
return np.max(arr[:, 0]), np.min(arr[:, 0]), np.max(arr[:, 1]), np.min(arr[:, 1])

import numpy as np
def extrema_npt(items):
arr = np.array(items).transpose()
return np.max(arr[0, :]), np.min(arr[0, :]), np.max(arr[1, :]), np.min(arr[1, :])

def extrema_loop(items):
iter_items = iter(items)
first = next(iter_items)
x_min = x_max = first[0]
y_min = y_max = first[1]
for x, y in iter_items:
if x > x_max:
x_max = x
elif x < x_min:
x_min = x
if y > y_max:
y_max = y
elif y < y_min:
y_min = y
return x_max, x_min, y_max, y_min

import numpy as np
import numba as nb
@nb.jit(nopython=True)
def _extrema_loop_nb(arr):
n, m = arr.shape
x_min = x_max = arr[0, 0]
y_min = y_max = arr[0, 1]
for i in range(1, n):
x, y = arr[i, :]
if x > x_max:
x_max = x
elif x < x_min:
x_min = x
if y > y_max:
y_max = y
elif y < y_min:
y_min = y
return x_max, x_min, y_max, y_min
def extrema_loop_nb(items):    
arr = np.array(items)
return _extrema_loop_nb(arr)

and their respective timings as a function of input size:

which shows that actually direct looping is beneficial for your use-case.

(full benchmarks available here)

See here for similar approaches working on NumPy array inputs.

If you are willing to start from a NumPy array, you could adapt the solutions from here, omitting the senseless ones like those using zip() or the key parameter from min()/max()), and adding a couple more:

def extrema_py(arr):
return max(arr[:, 0]), min(arr[:, 0]), max(arr[:, 1]), min(arr[:, 1])

import numpy as np
def extrema_np(arr):
return np.max(arr[:, 0]), np.min(arr[:, 0]), np.max(arr[:, 1]), np.min(arr[:, 1])

import numpy as np
def extrema_npt(arr):
arr = arr.transpose()
return np.max(arr[0, :]), np.min(arr[0, :]), np.max(arr[1, :]), np.min(arr[1, :])

import numpy as np
def extrema_npa(arr):
x_max, y_max = np.max(arr, axis=0)
x_min, y_min = np.min(arr, axis=0)
return x_max, x_min, y_max, y_min

import numpy as np
def extrema_npat(arr):
arr = arr.transpose()
x_max, y_max = np.max(arr, axis=1)
x_min, y_min = np.min(arr, axis=1)
return x_max, x_min, y_max, y_min

def extrema_loop(arr):
n, m = arr.shape
x_min = x_max = arr[0, 0]
y_min = y_max = arr[0, 1]
for i in range(1, n):
x, y = arr[i, :]
if x > x_max:
x_max = x
elif x < x_min:
x_min = x
if y > y_max:
y_max = y
elif y < y_min:
y_min = y
return x_max, x_min, y_max, y_min

import numba as nb
@nb.jit(nopython=True)
def extrema_loop_nb(arr):
n, m = arr.shape
x_min = x_max = arr[0, 0]
y_min = y_max = arr[0, 1]
for i in range(1, n):
x = arr[i, 0]
y = arr[i, 1]
if x > x_max:
x_max = x
elif x < x_min:
x_min = x
if y > y_max:
y_max = y
elif y < y_min:
y_min = y
return x_max, x_min, y_max, y_min

%%cython -c-O3 -c-march=native -a
#cython: language_level=3, boundscheck=False, wraparound=False, initializedcheck=False, cdivision=True, infer_types=True
import numpy as np
import cython as cy
cdef void _extrema_loop_cy(
long[:, :] arr,
size_t n,
size_t m,
long[:, :] result):
cdef size_t i, j
cdef long x, y, x_max, x_min, y_max, y_min
x_min = x_max = arr[0, 0]
y_min = y_max = arr[0, 1]
for i in range(1, n):
x = arr[i, 0]
y = arr[i, 1]
if x > x_max:
x_max = x
elif x < x_min:
x_min = x
if y > y_max:
y_max = y
elif y < y_min:
y_min = y
result[0, 0] = x_max
result[0, 1] = x_min
result[1, 0] = y_max
result[1, 1] = y_min
def extrema_loop_cy(arr):
n, m = arr.shape
result = np.zeros((2, m), dtype=arr.dtype)
_extrema_loop_cy(arr, n, m, result)
return result[0, 0], result[0, 1], result[1, 0], result[1, 1]

and their respective timings as a function of input size:

So, for NumPy array inputs, one can gets much faster timings.
The Numba- and Cython- based solution seems to be the fastest, remarkably outperforming the fastest NumPy-only approaches.

(full benchmarks available here)

(EDITED to improve Numba-based solution)

For the list of ANY size, if you're trying to find min and max, you have to take a look at EVERY element, which is O(N), and there's absolutely nothing we can do about that.

Having said that, you may, obviously, split the list into the chunks and feed them to the different processes, which will make it faster, depending on the processor cores you have.