Numpy: правильный способ получить максимум из списка очков

Question

У меня есть список точек в 3d системе координат (X, Y, Z).Кроме того, каждому из них присвоено значение с плавающей точкой v , поэтому одну точку можно описать как ( x , y , z v ).Этот список представлен в виде пустого массива shape = (N, 4) .Для каждой 2-й позиции x , y мне нужно получить максимальное значение v .Простой, но дорогостоящий в вычислительном отношении способ может быть следующим:

for index in range(points.shape[0]):
    x = points[index, 0]
    y = points[index, 1]
    v = points[index, 3]

    maxes[x, y] = np.max(maxes[x, y], v)

Существует ли более "тупой" подход, который мог бы принести некоторый выигрыш с точки зрения производительности?

Answer 1

Извините, решение также не является чисто "тупым", но пакет numpy_indexed обеспечивает очень удобный (и быстрый) способ сделать это.

import numpy_indexed as npi
npi.group_by(points[:, 0:2]).max(points[:,3])

Сравнение с другими методами

%timeit npi.group_by(points[:, 0:2]).max(points[:,3])
58 µs ± 435 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)


%timeit pd.DataFrame(points, columns=['X', 'Y', 'Z', 'V']).groupby(by=['X', 'Y']).apply(lambda r: r['V'].max()).reset_index().values
3.15 ms ± 36.9 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

def max_xy_ver1(a):
    res = a[np.lexsort([a[:, 0], a[:, 1], a[:, 3]])[::-1]]
    vals, idx = np.unique(res[:, :2], 1, axis=0)
    maximums = res[idx]
    return maximums[:, [0,1,3]]

%timeit max_xy_ver1(points)
63.5 µs ± 1.03 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

def max_xy_ver2(a):
    res = a[np.lexsort([a[:, 3], a[:, 1], a[:, 0]])[::-1]]
    res = res[np.append([True], np.any(np.diff(res[:, :2],axis=0),1))]
    return res[:, [0,1,3]]

%timeit_max_xy_ver2(points) # current winner
31.7 µs ± 524 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

def findmaxes_simple(points):
    maxes = {}
    for index in range(points.shape[0]):
        x = points[index, 0]
        y = points[index, 1]
        v = points[index, 3]
        maxes[(x, y)] = v if (x,y) not in maxes else max(maxes[(x, y)],v)
    return maxes

%timeit findmaxes_simple(points)
82.6 µs ± 632 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

Установка numpy_indexed через Pip

pip install --user numpy_indexed

(Если вы работаете в Ubuntu и некоторых других дистрибутивах Linux, возможно, вам придется использовать pip3установить пакет для Python 3)

Данные, используемые для тестов

Pastebin здесь .

Answer 2

Настройка

points = np.array([[ 0,  0,  1,  1],
                   [ 0,  0,  2,  2],
                   [ 1,  0,  3,  0],
                   [ 1,  0,  4,  1],
                   [ 0,  1,  5, 10]])

---

Общая идея здесь - сортировка по первому, второму и четвертому столбцам и обратный результат, поэтомучто когда мы найдем наши уникальные значения, значение с максимальным значением в четвертом столбце будет выше других значений с аналогичными координатами x и y.Затем мы используем np.unique, чтобы найти уникальные значения в первом и втором столбцах и вернуть те результаты, которые будут иметь максимум v:

Используя lexsort и numpy.unique

def max_xy(a):
    res = a[np.lexsort([a[:, 3], a[:, 1], a[:, 0]])[::-1]]
    vals, idx = np.unique(res[:, :2], 1, axis=0)
    maximums = res[idx]
    return maximums[:, [0,1,3]]

array([[ 0,  0,  2],
       [ 0,  1, 10],
       [ 1,  0,  1]])

---

Как избежать unique для повышения производительности

def max_xy_v2(a):
    res = a[np.lexsort([a[:, 3], a[:, 1], a[:, 0]])[::-1]]
    res = res[np.append([True], np.any(np.diff(res[:, :2],axis=0),1))]
    return res[:, [0,1,3]]

max_xy_v2(points)

array([[ 1,  0,  1],
       [ 0,  1, 10],
       [ 0,  0,  2]])

Обратите внимание, что в то время как оба будут возвращать правильные результатыони не будут отсортированы, как исходные списки, вы можете просто добавить еще один lexsort в конце, чтобы исправить это, если хотите.

Answer 3

В чистом виде:

import numpy as np

points = np.array([(1,2,3,4),
                   (2,3,5,6),
                   (1,2,9,8)])  #an example,

def find_vmax(x, y) :
    xpoints = points[np.where( points[:,0] == x)[0]]
    xypoints = xpoints[np.where( xpoints[:,1] == y)[0]]
    return np.max(xypoints[:, 3])

print(find_vmax(1, 2))

Answer 4

Это не чисто numpy, и я использую преимущество pandas, которое, я думаю, сделает все возможное для векторизации:

a = [
    [0, 0, 1, 1],
    [0, 0, 2, 2],
    [1, 0, 3, 0],
    [1, 0, 4, 1],
    [0, 1, 5, 10],
]
pd.DataFrame(a, columns=['X', 'Y', 'Z', 'V']).groupby(by=['X', 'Y']).apply(lambda r: r['V'].max()).reset_index().values

Возвращая это:

array([[ 0,  0,  2],
       [ 0,  1, 10],
       [ 1,  0,  1]])