Как эффективно суммировать для каждого отдельного значения c в массиве X все элементы Y [i], где X [i] = k?

Question

Учитывая массив 1D X длины n в Numpy с k различными значениями, я хочу подвести итог для каждого из этих отдельных значений c в другом 1D массиве Y с такой же длиной,все эти элементы Y[idx], где X[idx] == c наиболее эффективным способом.

Пример:

X = [1, 3, 2, 1, 2] и Y = [0.1, 0.2, 0.5, 2.0, 0.3].Длина n равна 5, и у нас есть k=3 различных значений в X.Это означает, что результатом нашей операции является вектор из k=3 различных элементов [1, 3, 2] в X и соответствующих сумм от элементов Y, равных [2.1, 0.2, 0.8].Также хорошо, если отдельные элементы упорядочены.Таким образом, [1, 2, 3] с [2.1, 0.8, 0.2] также будет решением.

Я уже искал различные функции в Numpy, и наиболее близким к тому, что я хочу, является np.unique(X, return_counts=True), но он возвращает количество, а не суммы вY.

Конечно, все можно решить с помощью неприятного цикла, например:

import numpy as np

X = np.array([1, 3, 2, 1, 2])
Y = np.array([0.1, 0.2, 0.5, 2.0, 0.3])

def unique_sums(x, y):
    distinct_x = np.unique(x)
    y_sums = np.empty(distinct_x.shape)
    for idx, val in enumerate(distinct_x):
        y_sums[idx] = np.sum(y[x == val])
    return distinct_x, y_sums

unique_sums(X, Y)

, приводящего к упорядоченному результату:

(array([1, 2, 3]), array([2.1, 0.8, 0.2]))

Есть ливекторизованная операция, подобная этой, в Numpy или любой другой обычной библиотеке Python?Если нет, то какая реализация будет наиболее эффективной в Cython?

Answer 1

Мы попытаемся использовать pandas.factorize для эффективного получения уникальных идентификаторов на основе int, а затем используем numpy.bincount для суммирования на основе идентификаторов.Таким образом, решение будет выглядеть примерно так -

import pandas as pd

def unique_sums_factorize_bincount(X, Y):
    ids,unq = pd.factorize(X)
    return unq, np.bincount(ids,Y)

Пробный прогон -

In [24]: X = np.array([ 1,   3,   2,   1,   2]).astype(float)
    ...: Y = np.array([0.1, 0.2, 0.5, 2.0, 0.3])

In [25]: unique_sums_factorize_bincount(X,Y)
Out[25]: (array([1., 3., 2.]), array([2.1, 0.2, 0.8]))

Answer 2

Вот, пожалуйста:

In [21]: u, inv = np.unique(X, return_inverse=True)                                                                                                            

In [22]: sums = np.zeros(len(u), dtype=Y.dtype)                                                                                                                               

In [23]: np.add.at(sums, inv, Y)                                                                                                                               

In [24]: sums                                                                                                                                                  
Out[24]: array([2.1, 0.8, 0.2])

Это заменит ваш for -петл изящным методом numpy.add.at.

Обратите внимание, что np.unique сортирует X, поэтому этот метод O (n * log (n)). Это не самая лучшая временная сложность для этой проблемы.

Answer 3

Мы можем использовать scipy.sparse.csr_matrix здесь для более эффективного решения

---

Настройка

X = np.array([1, 3, 2, 1, 2])
Y = np.array([0.1, 0.2, 0.5, 2.0, 0.3])

---

from scipy import sparse

res = sparse.csr_matrix(
    (Y, X, np.arange(Y.shape[0]+1)),
    (Y.shape[0], X.max()+1)
).sum(0).A1

array([0. , 2.1, 0.8, 0.2])

Это список сумм из 0 -> k, где k - максимальное значение вашего массива X. Любая запись, в которой ключ не существует в X, очевидно, будет 0. Чтобы получить лучшее сопоставление, вы можете использовать np.unique и некоторое индексирование:

u = np.unique(X)
np.column_stack((u, res[u]))

array([[1. , 2.1],
       [2. , 0.8],
       [3. , 0.2]])

---

Задержка

X = np.random.randint(0, 100, 100_000)
Y = np.random.rand(100_000)

In [11]: %%timeit
    ...: sparse.csr_matrix(
    ...:     (Y, X, np.arange(Y.shape[0]+1)),
    ...:     (Y.shape[0], X.max()+1)
    ...: ).sum(0).A1
    ...:
1.15 ms ± 17.3 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

In [13]: %%timeit
    ...: u, inv = np.unique(X, return_inverse=True)
    ...: sums = np.zeros(len(u), dtype=Y.dtype)
    ...: np.add.at(sums, inv, Y)
    ...:
16.5 ms ± 161 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [16]: %timeit unique_sums(X, Y)
16.6 ms ± 169 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Answer 4

Я думаю, вы хотите использовать хеш-таблицу.Дикт Python будет достаточно эффективным для небольших наборов данных.Вам, безусловно, придется использовать свой собственный алгоритм для этого.

def unique_sums(x, y):
    xd = {}
    for i, number in enumerate(y):
        xd[x[i]] = xd.get(x[i], 0) + number
    return xd.keys(), xd.values()

Я думаю, что ваше решение - O (n ^ 2) из-за np.sum(y[x == val]), но мое выше - O (n).