Эффективное назначение бина в numpy

У меня очень большой 1D массив Python x несколько повторяющихся чисел и вместе с этим некоторые данные d того же размера.

x = np.array([48531, 62312, 23345, 62312, 1567, ..., 23345, 23345])
d = np.array([0    , 1    , 2    , 3    , 4   , ..., 99998, 99999])

в моем контексте "очень большой" относится к 10k...100k записей. Некоторые из них повторяются, поэтому количество уникальных записей составляет около 5...15000.

Я хотел бы сгруппировать их в мусорные ведра. Это должно быть сделано путем создания двух объектов. Одним из них является матричный буфер, b элементов данных, взятых из d. Другой объект - вектор v уникальных значений х, к которым относится каждый из столбцов буфера. Вот пример:

v =  [48531, 62312, 23345, 1567, ...]
b = [[0    , 1    , 2    , 4   , ...]
     [X    , 3    , ....., ...., ...]
     [ ...., ....., ....., ...., ...]
     [X    , X    , 99998, X   , ...]
     [X    , X    , 99999, X   , ...] ]

Так как числа вхождений каждого уникального числа в х изменяются, некоторые значения в буфере b являются недопустимыми (обозначается заглавной Xт.е. "пофиг").

Это очень легко получить V в NumPy:

v, n = np.unique(x, return_counts=True)  # yay, just 5ms

и мы даже получаем n который является количеством действительных записей в каждом столбце в б. Более того, (np.max(n), v.shape[0]) возвращает форму матрицы b, которая должна быть выделена.

Но как эффективно сгенерировать б? Цикл for может помочь

b = np.zeros((np.max(n), v.shape[0]))
for i in range(v.shape[0]):
    idx = np.flatnonzero(x == v[i])
    b[0:n[i], i] = d[idx]

Этот цикл перебирает все столбцы b и извлекает индексы idxопределив все места, где x == v,

Однако мне не нравится решение из-за довольно медленного цикла for (занимающего примерно в 50 раз больше, чем уникальная команда). Я бы предпочел векторизацию операции.

Поэтому одним векторизованным подходом было бы создание матрицы индексов, где x == v а затем запустить nonzero() Команда на это вдоль колонн. тем не менее, для этой матрицы потребуется память в диапазоне 150k x 15k, то есть около 8 ГБ в 32-разрядной системе.

Для меня это звучит довольно глупо, что np.unique-операция может даже эффективно возвращать инвертированные индексы так, чтобы x = v[inv_indices] но нет никакого способа получить списки назначения v-to-x для каждого бина в v. Это должно происходить почти бесплатно, когда функция сканирует через x. Единственной проблемой, связанной с реализацией, будет неизвестный размер полученной индексной матрицы.

Другой способ сформулировать эту проблему, предполагая, что команда np.unique является методом, используемым для биннинга:

учитывая три массива x, v, inv_indices где v являются уникальными элементами в x а также x = v[inv_indices] Есть ли эффективный способ генерации индексных векторов v_to_x[i] такой, что all(v[i] == x[v_to_x[i]]) для всех бункеров i?

Мне не нужно было тратить больше времени, чем на саму команду np.unique. И я рад предоставить верхнюю границу для количества элементов в каждой корзине (скажем, например, 50).

Источник

2 ответа

Решение

Я получил ответ, который искал, перефразировав вопрос, см. Здесь: python: векторизованный кумулятивный подсчет

"совокупным подсчетом" inv_indices вернулся np.unique() мы получаем индексы массива разреженной матрицы, так что

c = cumcount(inv_indices)
b[inv_indices, c] = d

кумулятивный подсчет, как предложено в теме, связанной выше, очень эффективен. Время выполнения ниже 20 мс очень реалистично.

Источник

Основываясь на предложении @user202729 я написал этот код

x_sorted_args = np.argsort(x)
x_sorted = x[x_sorted_args]

i = 0
v = -np.ones(T)
b = np.zeros((K, T))

for k,g in groupby(enumerate(x_sorted), lambda tup: tup[1]):
    groups = np.array(list(g))[:,0]
    size = groups.shape[0]

    v[i] = k
    b[0:size, i] = d[x_sorted_args[groups]]
    i += 1

In работает примерно за ~100 мс, что приводит к значительному ускорению по сравнению с исходным кодом, размещенным выше.

Сначала перечисляются значения в x добавление соответствующей индексной информации. Затем перечисление группируется по фактическому x значение, которое на самом деле является вторым значением кортежа, сгенерированного enumerate(),

Цикл for выполняет итерации по всем группам, превращая эти итераторы кортежей g в groups матрица размера (size x 2) а затем выбрасывает второй столбец, то есть x значения сохраняют только индексы. Это ведет к groups будучи просто одномерным массивом.

groupby() работает только на отсортированных массивах.

Хорошая работа. Мне просто интересно, можем ли мы сделать еще лучше? По-прежнему происходит много необоснованного копирования данных. Создание списка кортежей, а затем превращение его в двумерную матрицу только для того, чтобы отбросить половину, все еще кажется немного неоптимальным.

Источник
Другие вопросы по тегам