python - 在列表列表中按索引查找最小值/最大值

Question

给定大小为 2 的列表列表，我试图找到通过索引确定最小/最大值的最快方法。目标是确定一系列 XY 点的边界/范围。

子列表未排序(按一个索引排序并不能保证另一个索引已排序)。

目前我正在做以下事情:

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

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

如果没记错的话，每个操作都是O(n)，所以整体复杂度是O(n)。

对于任意大小的列表，是否有更快的方法？

Answer 1

这里有几个替代方法:

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)

以及它们各自的时间作为输入大小的函数:

这表明实际上直接循环对您的用例有益。

(提供完整基准 here )

---

参见 here对于处理 NumPy 数组输入的类似方法。